找回密码
 注册账号
置顶:如何加入2024届新生微信群

[吹水聊天] 上岸算法LeetCode Weekly Contest 281解题报告

上岸算法 回复:0 | 查看:1960 | 发表于 2022-2-20 16:59:15 |阅读模式 |复制链接

UWCSSA提醒您:

警惕网络诈骗与盗号,不要在他人发送的网站中输入密码,换汇或付款时请小心诈骗。

为了避免个人信息泄漏,建议在帖子中使用不常用的邮箱,或使用私信发送联系方式(点击对方的头像,然后“发送消息”)。

帖子通过审核只代表内容不违规,CSSA 不会验证内容的真实性。请谨防诈骗。

登录后可回复主题

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
【 NO.1 Count Integers With Even Digit Sum】- F" z/ ]2 I3 ^. ]( b4 F3 B
; d5 s# d+ S# C( K. H; M6 R
解题思路# F; P( N& s6 r+ @& Q* J* y
签到题,枚举计算即可。
6 ?3 O7 x. j9 _% z. {& d* U! v& t! T0 g& i0 Z- V
代码展示* _* M8 d* W1 c* f1 t% V$ x0 u

) b/ B6 j! \2 f- z4 sclass Solution {8 l$ j- s3 {7 E& _& e- `; Y
   public int countEven(int num) {
4 W* S0 l$ z# ^' d: X& J       int res = 0;- R" e1 ~% K8 G) w$ W& w
       for (int i = 1; i <= num; i++) {
6 J. Z- x9 _8 J+ Y% h           if (digitsSum(i) % 2 == 0) {
! O9 J1 m$ R9 `% `5 Z  Z- l               res++;# I. R& x' u3 B* m% z$ C' n: p  x
          }
6 F/ B$ x" B  y2 n3 o' Y7 o& E      }
9 i( h. L  k8 Q# U& M* q0 v       return res;
3 q1 ^& w, [9 C  }
- N/ P) @& o* S/ j
6 X" y# g" D* Y) L   private int digitsSum(int num) {' f: C, Y+ {0 x5 K* @) Z8 k/ t' t
       int res = 0;! y6 ~2 y2 c- I  N3 A4 F. C9 \
       for (; num > 0; num /= 10) {
' v; I3 D3 F) {- q% z4 O. M           res += num % 10;
' L) A# q: v$ `  \, Y- Y7 ^. O      }& W3 O$ z% n% t; [1 a" d2 c( S# I
       return res;( j. W9 _- q2 W
  }! v  R1 e- S6 U4 u
}
- q7 M# D6 {! \5 i; Q* n! x  h+ y* |, d1 q

% \( [0 e. K. e1 v) }1 k【 NO.2 Merge Nodes in Between Zeros】
6 `( L6 @$ p- @8 _$ W2 ]
1 q  r3 F  O( w3 W解题思路# J( @9 m$ W- Z* j' Y: G( y
遍历链表即可。  X, J0 m/ W9 F5 |
* I# a) t* f4 @" H
代码展示
! q8 `2 [6 t0 s# z) A# C. w' c& t& x/ o9 Z% v. P# ?
class Solution {
$ l* P8 S* k( J7 G   public ListNode mergeNodes(ListNode head) {
; q3 D& g( ^$ {! A       ListNode res = new ListNode(0);
. t! f% D# U" r- F6 ?       ListNode tail = res;
' @! {+ k! D. t$ |" D/ ^( |       int sum = 0;9 \( \2 D% |1 V% j4 Z, U$ c
       for (ListNode cur = head.next; cur != null; cur = cur.next) {3 ^5 Q3 Q! Q; d& ^
           sum += cur.val;' Y" w) R; }5 j3 f8 g4 |: Y. u
           if (cur.val == 0) {$ _( M  b" D8 ^; p! I
               tail.next = new ListNode(sum);
7 i' o9 {" A4 V( Q: Z, @               tail = tail.next;
1 n' Z; |* M  j, Z  a               sum = 0;/ I& c& \! A6 S. r4 |) Y( s/ d; g) i
          }# T( P* \: p0 B1 E; t
      }! S" w4 \! A$ Z3 s2 l9 P
       return res.next;4 f& \( q6 T( @4 M/ R
  }& r- K( P8 H, ^" e1 p$ T+ q" ~
}/ ~& A2 D% \. ?* |

2 }) l6 K% O$ `7 i2 A7 l+ G+ Y# S7 E& @: `- T4 K2 g! K
【 NO.3 Merge Nodes in Between Zeros】5 e0 @9 J0 u, O$ r5 z" \
5 {* g: ~7 O1 N0 a. a7 r! o3 @
解题思路
9 e0 ?: q; |3 x4 I2 J; v9 L' r9 x注意题目描述:“不必用完所有的字符”。所以直接贪心即可,从最大字符开始,只要连续超过了 limit 就使用次大的字符分割一下。
# o7 o- ]3 q% I, b$ n( y( g8 Y' z% o. {  x# V
代码展示! R0 h& @% V: Q8 F7 T

6 \+ S4 G& I/ {/ ]9 H1 C7 sclass Solution {; B* [% G3 |9 S. D& Q: Z
   public String repeatLimitedString(String s, int repeatLimit) {/ E2 W$ {7 b4 \
       int[] cnt = new int[26];1 z3 B( K* j/ E( n# U) I) }
       for (char c : s.toCharArray()) {
, m# W2 \9 a& l7 d           cnt[c - 'a']++;
& i' @) j/ l% P/ N9 h% @      }4 K1 m/ b' Q5 h0 O3 X

6 s# Y4 B, j4 b/ J1 r$ h$ t: h       StringBuilder sb = new StringBuilder();
1 M- E, ~$ }# T; M6 p       int repeat = 0;* d  Q, o. M1 u
       char cur = 0;
' l4 R( i! F! }+ ]4 u       for (int i = 0; i < s.length(); i++) {& R! k6 P: ]# B' d9 W; a
           char c;; G8 ~1 N) m, F7 J5 F  _4 N! |  Z/ g
           if (repeat == repeatLimit) {4 z+ E7 c; v7 X6 H
               repeat = 1;  H5 o+ [6 M  W1 G# W
               c = poll(cnt, cur);
0 J6 a/ X3 n, {1 ^               cur = c;
1 }. x/ c( C  J0 N+ a& E          } else {9 F( K, A5 y2 m! e. v  d0 Z. p
               c = poll(cnt, (char) 0);+ |+ u3 _' Y9 [0 F
               if (c == cur) {
* A7 q5 k; k3 K1 U                   repeat++;
4 }/ j" c. r& x              } else {- [- B/ B% ]% m: @3 ]5 F  x) Y
                   repeat = 1;
2 ~8 j2 w3 [+ r3 [5 b: ~                   cur = c;
6 n2 X' @2 z8 S0 {9 D' O  q              }0 W. p8 V8 ^8 D7 Z: G9 q: ^& m7 O3 O
          }4 v) M% v0 s* @, W! Y, J
           if (c == 0) {
/ S& l! D, j6 @  h( e1 j               break;
" ?$ b' o& u$ x3 U" i1 ^, X          }- W. w8 N) K/ F2 x$ @6 o
           sb.append(c);3 |; M0 r$ S! Y& ^! [% V, V
      }
: m" h4 h5 Y3 @  G       return sb.toString();
1 T( ?+ J8 g/ @) B  }4 t4 N8 |7 B7 r5 _' v6 t4 |5 x& C! j

% D4 ^. g3 `# O0 Z   private char poll(int[] cnt, char not) {
9 O- q/ A( J2 h6 i7 @, l% @5 q       for (int i = 25; i >= 0; i--) {
" K( X# ^' T6 R$ b! Q; i! S% w           if (cnt[i] > 0 && not != (char) (i + 'a')) {
! {6 q6 d! `" h; f               cnt[i]--;
" H5 i0 _/ K% B$ ~* V               return (char) (i + 'a');
- X+ g: X; P* @8 r- @) H* L          }
7 O* z" G: \5 [      }% o2 m  C: d: v
       return 0;
2 x1 O0 f0 E1 c) P" m5 K; ?  }9 b) [+ n, ?) F
}4 R4 M2 t, e, |
7 O( M+ C2 k" s% D# J

7 }4 o) L! O6 ^【 NO.4 Count Array Pairs Divisible by K】& J9 y$ W  s; u# \  E/ x( F
0 E% m% A7 S. _) ~0 U* ^
解题思路
0 V" s, i0 k* \! H& J0 ~预处理转换成最大公因数,详见注释。
" [# `" F' g) l9 x1 ]
  b. V7 c, |' U4 r# F# R代码展示( c  u2 F0 s4 i+ G, a" G
6 o8 o; y$ _9 |& I: t1 A0 u
class Solution {
  H1 l, e/ ]! P1 t6 }7 Q   public long coutPairs(int[] nums, int k) {+ W8 c7 }7 b& v3 Y
       // 将 nums 转换成与 k 的最大公约数
. y" w; z8 Y6 [- {+ u, x  y2 n       // 因为每个 num 中,k 的因数以外的部分没有意义 (即使做乘法这一部分也无法帮助结果成为 k 的倍数)% U- q% w# c5 q1 H
       for (int i = 0; i < nums.length; i++) {  }+ e1 _! h3 S
           nums[i] = gcd(nums[i], k);
& L+ i1 ^& X2 ?* R: Y$ F1 e      }; J* t0 f  |- R+ D3 @7 h
       long res = 0;
, x4 L+ ^0 e- o+ ^! p       int[] cnt = new int[k + 1]; // cnt[i] 表示因数 i 的出现次数2 Y7 u6 ~3 D' }0 u( }
       for (int num : nums) {
) I7 N* i' V- i           // 经过了最初的转换, 此时还需要因数 k / num 即可组成 k 的倍数
# `1 H7 r9 K( v) J9 \3 H7 f           res += cnt[k / num];. h' g# h$ O( k; R5 f! G

8 ]) I& p2 p4 n2 z           // 使用 num 维护 cnt, 即 num 的每个因数 i 都对应一次 cnt[i]++0 o0 j6 v# }) ^& J6 r
           for (int j = 1; j * j <= num; j++) {' {3 k; Q4 [! L. g" W
               if (num % j == 0) {% t9 U. a3 J8 B" J# H; U
                   cnt[j]++;
' q( O# v6 }/ H  z" h* E                   if (j * j != num) {
) m* O2 I2 {8 M                       cnt[num / j]++;7 n. E  s' b; w0 V8 q
                  }* |. p' N+ M4 [
              }
0 n6 D; x. Q2 t: C0 j          }, e6 \( |; u8 X0 [  p' e
      }5 i" Q- f- Q$ U$ C
       return res;3 W- O, i3 ~7 b) }) b
  }, U/ M2 q+ e2 s% |

$ i& k" B% j+ o7 Z  `! h8 g  H   int gcd(int a, int b) {
0 t1 R  S( g. X. I. C9 W       return a % b == 0 ? b : gcd(b, a % b);
2 _/ g6 P' v8 `$ e& b  }  a  {9 s" M+ v! z9 Z  g# U
}
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

登录 发布 快速回复 返回顶部 返回列表