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

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 Count Integers With Even Digit Sum】: U) b0 Y2 \9 x
" W- J' {# m" o$ s; c5 Y- n$ N
解题思路& Z7 V" \/ t9 m/ E7 t7 _6 H
签到题,枚举计算即可。
) t2 H! a! f/ S7 R' X( \8 C* K2 y9 y* K5 O' a6 K
代码展示; |; Z  X; b, Q. c+ [. [6 E7 u+ w
2 c2 a0 x+ E1 U& }* E, \0 x7 R
class Solution {
: ~- o# e% d4 J" e' ~! f. a   public int countEven(int num) {4 t  P. j' r5 @9 f
       int res = 0;
8 r$ ]# ?! R& r" M2 p       for (int i = 1; i <= num; i++) {1 f# J$ z1 s( R" Z' z. K& ]( F
           if (digitsSum(i) % 2 == 0) {& B7 j- y' ?" I+ G4 W  o
               res++;
% A5 z9 _/ M8 E7 j9 m          }" n, k; A1 \4 @: l+ P3 ^) Q
      }
# i& H6 X& M6 Z: c       return res;) W6 ?; F9 e' g
  }
' \: Y4 L7 o! M9 }+ P( l7 p$ d$ \% _2 |5 ?: I) l0 v0 E1 S1 z7 I
   private int digitsSum(int num) {9 w9 |5 c; Z8 w( S
       int res = 0;
; S+ N* B0 v; o& D2 F. n8 r: m       for (; num > 0; num /= 10) {
  W4 a& s5 C% v4 M' F+ |           res += num % 10;( e) y% k# F* x) B! [6 }
      }; W* b# r$ _6 [! w, W6 k# _2 K
       return res;
% m: J9 G1 r; U) C' b; H8 h1 Q  }/ P3 ~+ V& [( D' M
}& M$ K3 w/ p3 X! b( Y

. c1 N0 V8 v% C. I, }5 b" ~! s. a  A7 k3 x3 s. i
【 NO.2 Merge Nodes in Between Zeros】& x7 x* z* N& L1 [, v- s2 D3 X
+ D/ h* L( g. [7 x& e& v/ |
解题思路7 B- L! Y) R; w  [+ @. Y
遍历链表即可。* Q3 X+ s4 u. B+ m
7 Z' m8 Q: t; V0 C; l3 w
代码展示3 C! ]; A0 U4 \  `: x7 Z- l

0 w& b" p, D9 Qclass Solution {: o' f( ~; R, E( Z2 f# ^1 r( X
   public ListNode mergeNodes(ListNode head) {: {* `# v1 `9 Q7 e
       ListNode res = new ListNode(0);. K" Z# o: a: s
       ListNode tail = res;8 F1 [) G) ~0 {. r! e
       int sum = 0;
2 X2 N% K& }/ w. ^( Y$ D0 l$ u; S" h       for (ListNode cur = head.next; cur != null; cur = cur.next) {
4 I% I. Y5 o! l/ E- \4 q$ {" m. H           sum += cur.val;* m8 z* n4 |' ~! I+ v7 b
           if (cur.val == 0) {9 b# M6 A# k; @; i  \. r" Q+ W
               tail.next = new ListNode(sum);% @/ \3 N0 v1 c4 G
               tail = tail.next;
2 U1 B+ p) r8 F. O               sum = 0;) n8 p" [4 G5 M; }7 s% b6 D! d
          }
3 V! Q" j0 [, z      }
1 j  j  g3 @( t7 i- _& G       return res.next;
- T8 e6 L* [. b6 _& v+ y( @, U9 q  F  }
+ A( u" E3 T+ [3 C}
( K/ x2 [* a0 u
/ s& B$ O) d: L' d
! o7 \6 q- r$ o, D) E【 NO.3 Merge Nodes in Between Zeros】
) d: R9 t& p" B8 n- v# z! }
1 F! z% l- u. {( b: d) w0 P8 B' t5 O解题思路
. N% L) q  f7 y* |8 k注意题目描述:“不必用完所有的字符”。所以直接贪心即可,从最大字符开始,只要连续超过了 limit 就使用次大的字符分割一下。6 U+ M* V7 G1 r) K% k

! O! L4 @0 L- M4 d" [% e代码展示/ F9 j' r# X3 ^$ O' G9 n* p
& G. x9 `. I. V) q0 l9 b1 X6 U
class Solution {
* f5 L( W6 c  J& C/ n   public String repeatLimitedString(String s, int repeatLimit) {8 Z2 B, ?6 [1 l# g6 [
       int[] cnt = new int[26];
7 {% T6 v* w* Q9 c       for (char c : s.toCharArray()) {
5 w: \5 L0 K/ s* v/ [* ]           cnt[c - 'a']++;
2 \! t) H8 Y$ q0 }: k: @      }* r  B3 Q# E7 V" Q* x. s

6 ?$ r0 b) p$ A0 S       StringBuilder sb = new StringBuilder();( Y" W) _* P5 w
       int repeat = 0;
. G7 Y  k# u  J- z! \0 k7 V4 x" E) u       char cur = 0;' {- k) O# P% S' |& o* A9 L  @
       for (int i = 0; i < s.length(); i++) {* O. d* ~: l# q1 B
           char c;3 ^  X4 L, I& B) g8 i" N
           if (repeat == repeatLimit) {
6 f9 H: P. l' ]; J               repeat = 1;  |( ~, Y0 O- D" o# R
               c = poll(cnt, cur);
+ g6 j3 j  v, W: H- X+ m! K# y               cur = c;1 B3 A% v$ L8 c4 [& I0 q+ R2 b
          } else {
5 v* D  ~5 n, D+ T! ?               c = poll(cnt, (char) 0);1 N5 e% ?" N6 W+ j: y8 {
               if (c == cur) {
9 m+ M$ @( \/ N! Z) m  E  ]                   repeat++;. P& K* W4 w, i0 j6 w+ j4 D
              } else {1 e4 P& L6 r  e% t
                   repeat = 1;
& D. M4 t$ N: j: V3 a! \                   cur = c;
8 \- ]: z' h+ `' \5 P              }
" q, e3 C# t. G9 O$ {          }* d7 N- c# _, t/ e9 b' y5 o* i9 Q) T
           if (c == 0) {
5 w* o7 V7 U( g- K5 \. v! B               break;
- R4 S5 x1 Z* K, \* Q8 d          }
9 o; D/ d, A' W2 f6 m! F1 j           sb.append(c);8 `  y  U+ u) h6 l
      }# [' M+ K: j6 W  }- X
       return sb.toString();
: \9 |) T6 [0 ~) r  C  }" M  @2 t+ W/ W8 C

" R2 `5 G- F! ]2 P* I  t! g& h   private char poll(int[] cnt, char not) {2 W" c- l( Z# Q6 n  j
       for (int i = 25; i >= 0; i--) {: _6 ^! ?" I) M
           if (cnt[i] > 0 && not != (char) (i + 'a')) {9 j3 _  \# r7 ?7 R: m% V: l2 Z
               cnt[i]--;% u6 ?7 i8 G2 d  \/ r/ m( I% i8 s
               return (char) (i + 'a');4 F' O6 V7 u& U9 f5 K" M! R/ D
          }7 @7 h/ T) F9 D# |
      }3 [) m, i1 i5 k/ W7 v. Y# P! p& Y
       return 0;9 ~3 ?, k& t* p2 B; q
  }
: F4 G( P% h$ l8 Y) m& F0 L# i& w}7 ~% e" G3 v6 ]) A

5 K& }# z, l' E/ _8 {( |
1 t4 Q3 L1 U, c) l7 O: k【 NO.4 Count Array Pairs Divisible by K】) p/ m$ u# b6 U
& f. I$ h( }1 w1 u
解题思路: ^+ D2 h3 Y) v' J7 `
预处理转换成最大公因数,详见注释。: r" S$ J  R8 r- z# S: J7 m
% f! T5 ^' L0 U! G. \5 H: D2 V  w. O
代码展示% A5 Y* x* ]  w
" @5 x& x- d6 \1 p
class Solution {1 h/ s  U/ `" z! i% ^5 k
   public long coutPairs(int[] nums, int k) {# \' J' \, Q3 o+ g4 f7 Q
       // 将 nums 转换成与 k 的最大公约数3 |; ~+ t" g; n
       // 因为每个 num 中,k 的因数以外的部分没有意义 (即使做乘法这一部分也无法帮助结果成为 k 的倍数)
1 A& H& P/ N7 O& v. n3 M       for (int i = 0; i < nums.length; i++) {
+ p0 ]8 O8 r2 P9 ]2 j! t           nums[i] = gcd(nums[i], k);
& w# ^% s3 |. C, e4 d      }
. `" Y( Z# v& }       long res = 0;2 C/ u0 q) t) j* I9 `
       int[] cnt = new int[k + 1]; // cnt[i] 表示因数 i 的出现次数
& e! S0 v/ e+ U4 p, q7 @- @8 o- K! v       for (int num : nums) {
4 u( R( ~$ K4 H* [! a) O( C& e( q9 d           // 经过了最初的转换, 此时还需要因数 k / num 即可组成 k 的倍数7 j# K) E  n) J; y1 d) i, {/ Y. k- A7 G
           res += cnt[k / num];. v% ]4 `* g+ X: c+ T

% v% r0 F; V; Z7 K2 L$ O; j           // 使用 num 维护 cnt, 即 num 的每个因数 i 都对应一次 cnt[i]++
7 r: v0 U5 ?3 t. Y- h           for (int j = 1; j * j <= num; j++) {# o. j" l! O1 p. n6 z8 U
               if (num % j == 0) {0 M+ ]/ l! C# q
                   cnt[j]++;& q+ e  w/ V( ]
                   if (j * j != num) {' q7 ~! G$ q5 ^& J9 J
                       cnt[num / j]++;
9 o# I: \& @8 _7 w4 T                  }  H0 p+ `+ H" R+ u
              }: T8 s' y8 E$ Q& f6 u" h
          }2 A/ [5 H% @* N
      }
% ?- j9 X$ ]2 W( k& ~8 _* B       return res;* H6 U1 S. H% W4 V
  }( e0 x" P& ?( a

# B" j# n" S7 w/ u9 [   int gcd(int a, int b) {
- F1 R9 M; `* P2 d. h- E       return a % b == 0 ? b : gcd(b, a % b);! K* W( S* ?" \& y9 f' M
  }
$ o8 j0 p1 |' z- J6 a6 C4 g2 X& V}
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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