找回密码
 注册账号
img_loading
智能检测中
置顶:如何加入2024届新生微信群

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 Count Integers With Even Digit Sum】8 B4 g9 Y" w# u9 d' G8 @

* G0 Y/ f9 `* }5 c: @: m解题思路
! h* P3 G2 ^$ q$ H4 j, ^3 p7 g签到题,枚举计算即可。! v: o7 ^$ s7 h! c4 N
9 f) S8 x# q7 [0 H" y8 x5 ^, `0 e
代码展示
3 i, `6 J+ [0 g" M' p- z: s4 Q6 P9 V/ G0 C5 j" ~
class Solution {+ e# S4 f2 S+ e6 |5 U: V" C$ q+ Y
   public int countEven(int num) {; Y. T: e4 K- g0 I5 J0 |
       int res = 0;0 ]8 k2 C( ?' A2 @. N
       for (int i = 1; i <= num; i++) {3 W1 L% T& L# b# t4 S
           if (digitsSum(i) % 2 == 0) {
7 J8 g) H3 {5 S, N. I5 P               res++;
: q( ?2 X9 ?8 z3 X          }
) |  e4 \/ U* N2 F      }
9 p4 r6 b# \' [% _       return res;
* j  h/ O0 x0 N  }; |! y& X* `! |6 k. N

0 C! ~! M4 f1 @0 `; `0 F, P1 {   private int digitsSum(int num) {; Q3 a) i! o6 V& v& h$ T
       int res = 0;7 `3 c9 b  P( x& s/ I
       for (; num > 0; num /= 10) {
) G% R; ^+ |6 h" L7 s5 W           res += num % 10;
" s: ~; o* D8 E: i3 v      }
/ r  ]  d, P8 w% z' _6 s       return res;! D- a# f1 C6 T6 }$ @4 m8 K
  }8 ~. X5 j2 B2 K
}
& D# v( Z8 o1 O+ o+ J
' t4 Y* p' p& h, M: u' R$ H5 z  w: J. M  m; H+ ?3 {/ U% k
【 NO.2 Merge Nodes in Between Zeros】9 A1 r- d$ K  O. l7 E
* h3 u/ D) U2 ]
解题思路6 C: C& j4 P4 M2 |
遍历链表即可。
# t( @/ N4 b& Q) K# R
8 k5 e- y" k* C: [3 |0 w3 W* \代码展示5 O' }* l% o9 b1 {* j

- i! _: K( v/ r$ c% jclass Solution {
- `/ X8 e2 v3 Y. b2 i   public ListNode mergeNodes(ListNode head) {
2 p; @1 `; b' L2 v" w; ^       ListNode res = new ListNode(0);
, Y5 E. G$ W8 k$ G% _$ J3 Z       ListNode tail = res;+ o) k0 }- X1 R+ x: r+ W
       int sum = 0;9 `# [, n4 e* s: {. o4 l$ v/ ?# e
       for (ListNode cur = head.next; cur != null; cur = cur.next) {
6 e1 u3 ?$ _' v$ j           sum += cur.val;3 J! z  U5 w" \% g! v
           if (cur.val == 0) {
8 }: K/ A9 {4 T( @  {9 p               tail.next = new ListNode(sum);
( j1 Y  |# y: k% w               tail = tail.next;
% J7 ?* V  V3 Z& a* z3 b+ R               sum = 0;/ x2 \) p7 T! q, y& H: p
          }% ~/ Q( p* d8 y& P" h! U
      }
) s% x/ i$ N- J8 K/ _       return res.next;8 S" N4 M5 w- [' C' A) M. @
  }
+ d6 R5 ?" K) P3 ?2 e6 ^1 ?( \2 I9 T}; f+ t( i; I. |( m$ x9 R2 I3 y& @( A
4 a; H' e# r9 b# }( w
7 w/ D! [$ }4 Y% s0 G+ {* H) T9 R# G
【 NO.3 Merge Nodes in Between Zeros】0 P+ `( B6 z2 m9 _; I- A9 F& ?8 _
/ F) X& c4 o% D5 q. {' `3 z6 W1 ^
解题思路
" L) l# F+ G6 P注意题目描述:“不必用完所有的字符”。所以直接贪心即可,从最大字符开始,只要连续超过了 limit 就使用次大的字符分割一下。  f; _* B. Y# u

' _# y: J9 n: t" |. f! b代码展示8 H7 D6 t  M" l  S1 v
  O8 Z3 B/ x( F- f/ `
class Solution {/ E' r7 G4 c5 a9 P% f
   public String repeatLimitedString(String s, int repeatLimit) {  H# K) l* q7 W8 ~. Y" l
       int[] cnt = new int[26];
. q4 x( [- }+ J6 C8 g& ?" E       for (char c : s.toCharArray()) {6 z" u: y; A; q1 i- l5 T# e
           cnt[c - 'a']++;# d% {$ v" b% R) f1 ^0 d" C) B
      }9 o$ R, c% v% A% E$ P

+ p7 K$ G' X& @       StringBuilder sb = new StringBuilder();3 ~' ]8 |  d& K  G% L: m
       int repeat = 0;
- L6 y5 l6 [8 K, S5 o: y       char cur = 0;
$ o+ d& E9 W. t$ J4 J       for (int i = 0; i < s.length(); i++) {
, \1 T8 m( t: C           char c;
" B1 C0 b3 E# ]( x# @2 `           if (repeat == repeatLimit) {
: P! j4 |! L& `  G               repeat = 1;6 M$ C( j' M  }4 T# @8 D* ~
               c = poll(cnt, cur);' ?* c; o5 p1 L$ s
               cur = c;6 ]6 N  y; Y1 _/ f+ M- {7 m% W
          } else {
' K, n# u1 F4 j: b0 q3 t3 F               c = poll(cnt, (char) 0);) v4 s2 J) B4 j3 R' y2 s" o
               if (c == cur) {
( u: o; Q: c% \% q6 }8 Y2 ?# I                   repeat++;) e# p5 S) i7 l% f5 d1 \
              } else {
+ j# N% A$ i# v                   repeat = 1;( o& ]8 _& y8 h7 c% c- q- b
                   cur = c;9 [# s, j( L' B/ @2 Z! T" A1 G
              }
+ E. G; _  G3 r0 `          }
: B) j4 k: K9 ^           if (c == 0) {
/ \) I0 @  u( n               break;
$ [8 Z" m1 Y2 {5 T: M' R! r! d5 P; _+ Z8 A          }
  \% b6 j8 Q. z) {8 c           sb.append(c);
. P* R- V) U6 G" e* O      }
4 ]) [' [3 C4 g* G' z2 ]7 S0 g       return sb.toString();5 a% ~1 X+ X! y+ V! v' a, [
  }
1 K" N/ g$ X5 D% k+ {+ D
) t3 A4 Q$ H$ e2 s; @   private char poll(int[] cnt, char not) {
1 g* _" {+ _. y- ^0 R/ b+ _       for (int i = 25; i >= 0; i--) {
$ ?% z: W+ k3 f9 m) r1 p           if (cnt[i] > 0 && not != (char) (i + 'a')) {
9 y( d& D; F- b! \# G               cnt[i]--;8 s6 k) x* }+ V: q
               return (char) (i + 'a');
" N( c- N; U+ i$ L5 {- Q          }5 D' S0 B, O( U  h9 }
      }8 J. T2 C4 ?, C3 g/ p/ P
       return 0;7 G4 M& w; O7 U. n
  }
+ m- D3 C5 p: c: C7 I8 G) O}
  d7 t, D& ]6 X9 X2 q1 m% S3 k! r& r% v. }! }% J/ O
2 g+ h4 t' b. L" a' D' h
【 NO.4 Count Array Pairs Divisible by K】5 s/ t# t6 D, }

& u7 \- K9 L6 u1 [7 d0 Z解题思路: C* b# Z2 E( d4 E
预处理转换成最大公因数,详见注释。% ^% _0 P; R/ A3 b: ~0 m" m
$ D: C8 d7 a+ z$ H, F' Y* R
代码展示
& I- y3 N4 @4 \% }8 m8 b% l" C9 a" {* G1 i6 _! @/ ^. {# I5 v+ N
class Solution {
6 `1 u1 T- R$ k; m' x   public long coutPairs(int[] nums, int k) {
& K: S1 w/ }. w5 {       // 将 nums 转换成与 k 的最大公约数
4 N7 P/ u3 X1 i9 z. s. G       // 因为每个 num 中,k 的因数以外的部分没有意义 (即使做乘法这一部分也无法帮助结果成为 k 的倍数)* e6 Y. Q9 {! L2 b! [
       for (int i = 0; i < nums.length; i++) {% N% B) r0 n4 {
           nums[i] = gcd(nums[i], k);6 A/ g7 A% R, P6 }) ~5 e$ R) @1 |8 S
      }9 X9 Q- A/ I, |9 \' b* x
       long res = 0;4 A5 P9 c, |1 R4 b& y4 c( N
       int[] cnt = new int[k + 1]; // cnt[i] 表示因数 i 的出现次数
; T5 u+ w& {( {  y" B" ^0 N: v9 Q       for (int num : nums) {
; A0 }" u$ J" S; g2 v5 j* l, I" j           // 经过了最初的转换, 此时还需要因数 k / num 即可组成 k 的倍数* |( F, f% E+ ^6 E' K, \$ T6 Y  n
           res += cnt[k / num];7 R+ }6 A; A3 b$ f
8 _2 @, w$ c3 {! P3 m  ~& e4 W0 K
           // 使用 num 维护 cnt, 即 num 的每个因数 i 都对应一次 cnt[i]++& ~$ q5 \& d( h/ w  {5 F5 `4 O+ _- b* r3 v
           for (int j = 1; j * j <= num; j++) {
: _: ~2 ?1 R+ D0 G               if (num % j == 0) {
8 l9 @2 Z& ]9 Z                   cnt[j]++;  b  L' `8 O- t6 y$ V# V5 o. a
                   if (j * j != num) {/ a% w/ H# g- m: Q: _4 k; @6 R
                       cnt[num / j]++;
/ v! q/ i  x$ A. Q3 d                  }
4 c6 G- m+ p! `: s. e- Z- p              }1 r7 |, i$ ^7 X. _( C
          }
/ \" ^% ]! ?5 o! _: J# @' R0 O; p      }
+ Y. k# F& S; v' X, i& ?1 e. C6 J' R       return res;
2 s# f0 D; h6 N2 u3 X/ A0 C  }# Z  c9 R: E3 s
! x; J' ]( i+ s* I% p6 w5 d
   int gcd(int a, int b) {
; W" h. h( |6 [       return a % b == 0 ? b : gcd(b, a % b);
5 R% K  r) v) U3 L8 o, \! v+ z  }
& T- n# J$ W0 y) ]7 s9 f}
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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