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

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 Count Integers With Even Digit Sum】' i/ U# D; ?9 V) b

5 Z1 n, \% ~8 \, Z# o  E6 e' Q6 E解题思路
8 r+ U: @2 J0 `签到题,枚举计算即可。
( o; l" ~* S' T% u" I6 I5 \3 S% y
' J; d- @! Q- ?+ t0 }代码展示3 ~5 ]0 b; Z3 s: H( h. {

% d( W' t0 {% ?7 O1 [; D- Qclass Solution {# G2 B9 b# l/ ?% p5 T8 Y9 E
   public int countEven(int num) {$ O& F, }9 n6 m2 g
       int res = 0;( u! {( k+ R* F4 u
       for (int i = 1; i <= num; i++) {3 F% x# V8 r8 {3 Z& E2 X7 m
           if (digitsSum(i) % 2 == 0) {
% Y: R. c7 e# {9 E& k  v               res++;
5 g4 {6 f! x7 D1 b( u9 j9 V          }7 Z4 L  @3 M( h$ u: K
      }
9 ^& M  i0 b8 A# S5 q' c# |       return res;+ l+ E1 S9 \$ e
  }
  Y! t& d: L+ I6 g+ D2 i
. i- n, M& Z2 a9 Z   private int digitsSum(int num) {* O2 i8 W- C. U! Q
       int res = 0;& u: u. S7 _" G7 p0 l% v6 O
       for (; num > 0; num /= 10) {  a' K" l& l8 D& w" b
           res += num % 10;$ u8 d, l: l) T, ]' A9 b* W: {: l, i
      }
) d# S% S: M. x  O5 {       return res;! s( y! X+ G" j( V3 I$ t+ V
  }8 |1 m: R8 Z( g  _3 m1 M
}3 x$ E; b( h4 G& H1 E: ]9 |

: E* E; l1 g$ i1 i6 T- \; r/ _/ [& ]9 `. m. q/ U
【 NO.2 Merge Nodes in Between Zeros】3 }% U% ]8 |! p
0 f% d) j' j! r0 Q: U7 A
解题思路% i4 h- C/ e9 d" _  _
遍历链表即可。
- ?  ?& r9 [3 S& w4 P  N! t" q. d6 D2 O" ~, a5 a, ^
代码展示4 _, E/ e/ q0 z. D2 k6 s" @
/ `3 n" S* K: e/ f( G  y
class Solution {
' b; S( `) {$ E3 }5 Z0 i   public ListNode mergeNodes(ListNode head) {
* `) A2 K9 x; H5 a       ListNode res = new ListNode(0);' ?! @( j2 u' {" \! S
       ListNode tail = res;( h. R. R6 Y) {9 i
       int sum = 0;
' ^8 o: v8 v- S5 N; [       for (ListNode cur = head.next; cur != null; cur = cur.next) {+ f- X6 P, I" P6 f+ f* s6 ~
           sum += cur.val;3 v  i! S1 v  y0 I0 t5 x
           if (cur.val == 0) {
* X; t! W3 C# y  C' q               tail.next = new ListNode(sum);0 O  o5 v' \" F2 z- a4 S
               tail = tail.next;9 f2 U- n) z, E& ?2 m4 b: ~4 ?8 L
               sum = 0;8 |! r4 E, z/ T. r: p% g
          }. ^7 L. K! H& y; ]
      }
$ T5 z' V9 L% a" W3 V, p       return res.next;
6 d7 V$ l" x1 z8 L' i  }
7 @, Z, Z$ ^5 {' t$ R}
. g' t: D, c* G$ @& y* T; j2 q' z& N/ N: S: w) ^
, k! n' z- h0 w% S
【 NO.3 Merge Nodes in Between Zeros】) X% q( Z; |( v8 N8 U

( d  N4 k& `! {$ P" f$ P& [解题思路- p( o7 i% F- X& D: N2 B  g
注意题目描述:“不必用完所有的字符”。所以直接贪心即可,从最大字符开始,只要连续超过了 limit 就使用次大的字符分割一下。6 g& L7 R, L% {0 \( z9 v

1 Z# c& f0 d' q% a代码展示+ w8 g* v, M. p# X# s5 f8 S. d
0 `9 s  P% j6 ]; W, f
class Solution {3 r6 [( \! _% M" B
   public String repeatLimitedString(String s, int repeatLimit) {! n1 }5 w, O8 D. e, v5 [
       int[] cnt = new int[26];. P, g% F- X! ^% Q* r
       for (char c : s.toCharArray()) {
3 S$ K* \  D5 O1 J5 G           cnt[c - 'a']++;9 D+ T4 [* B. S+ R3 n
      }
* y/ P6 Q; p' c1 O
; d# x: i& E6 a+ ]- U8 `       StringBuilder sb = new StringBuilder();  r9 ]/ n+ ?" y; i" M: y3 s
       int repeat = 0;$ Q2 T, H- A4 y0 X
       char cur = 0;
3 R/ e% j9 p3 ~2 _       for (int i = 0; i < s.length(); i++) {  c. T. n5 C+ V( Y& b7 n- [% |
           char c;) g4 a5 R' y. f
           if (repeat == repeatLimit) {
: g, x6 |8 N5 z7 Y3 p0 ~! Z" f' M               repeat = 1;" G  e) r5 G2 `6 B8 a9 ^0 d
               c = poll(cnt, cur);' K& t: `! \+ ^# }( k( Q6 x( z
               cur = c;
, e; y9 j! `4 f" p) }          } else {
# t5 K" b# Z" A" M               c = poll(cnt, (char) 0);" n3 V1 Z$ u, z  I
               if (c == cur) {& I( |2 ]& v2 }' P
                   repeat++;) T% S8 H1 R6 Q" h, [; C
              } else {
5 ^% H4 q# T5 s+ {# ~                   repeat = 1;3 i0 C# k/ ~: `9 h$ @
                   cur = c;
$ V  L1 V( p  r; m- I% d8 q3 i              }& B/ t+ M3 a8 T' B" z
          }
7 Z. v% y( [8 {3 ?           if (c == 0) {( k$ Y! ^0 q( t9 F5 u& i+ w
               break;8 k& K& {5 \  E( i- P% W8 N! T% I. l% R
          }; g, _8 d* ]' d5 x" K
           sb.append(c);  f" E- ]- m4 ~; h; C: K
      }1 U5 Z, @. c5 W8 b' ?- C% c/ X) u
       return sb.toString();
; a" t$ x! \6 ?/ k/ I  }2 m$ L4 M9 ]+ l, D

: N7 j+ R. H$ _' W$ O/ K   private char poll(int[] cnt, char not) {) ~3 {" E( r& W) ]  }
       for (int i = 25; i >= 0; i--) {$ F2 }; [4 s+ b
           if (cnt[i] > 0 && not != (char) (i + 'a')) {, e+ v6 `& i- u8 n  c
               cnt[i]--;
  b' s6 c8 ?, s$ T; W7 f; B6 F2 y               return (char) (i + 'a');2 Z+ N+ D  b3 Y6 t& }
          }
# D  d4 [, O6 S6 `+ j5 R      }
  ]% T) h" w# g" Z7 j       return 0;
* M4 m. ]6 Z  j; p0 W+ h& H% v  }
+ X( x+ W% v% V: a  v}
) N) I$ q& W: J6 P7 U6 {  e, [& o" M4 z
$ F) |: r& z) q* ]1 `: q
【 NO.4 Count Array Pairs Divisible by K】- h# ^; k" o& w# W2 g

* F3 h. p4 l0 ^* I& q& o解题思路
3 E! M. n6 s  x% }& a预处理转换成最大公因数,详见注释。0 S- J* \% C1 ?! z' y
/ x/ k3 t2 ]. D* I8 t
代码展示0 i( {: y! I7 j. ?* l1 Z
1 F. {$ b( A8 F9 p- F. N& u" u
class Solution {
( u+ X; p' S7 Q: W   public long coutPairs(int[] nums, int k) {+ v: u* E$ U& }" E$ I. U
       // 将 nums 转换成与 k 的最大公约数+ S; ^9 s3 D5 \
       // 因为每个 num 中,k 的因数以外的部分没有意义 (即使做乘法这一部分也无法帮助结果成为 k 的倍数)( s, V7 r0 W& `2 m* g
       for (int i = 0; i < nums.length; i++) {
9 V! Q" _3 d' e           nums[i] = gcd(nums[i], k);( C: d6 M* b% T& u+ G
      }- B8 v% t: `1 |0 d  P
       long res = 0;
3 Q. Y3 G8 z6 J. V6 g4 P8 d* J. n       int[] cnt = new int[k + 1]; // cnt[i] 表示因数 i 的出现次数- p9 }0 O  |3 R7 f
       for (int num : nums) {# c$ j) g9 N0 v2 h% ^. J4 R
           // 经过了最初的转换, 此时还需要因数 k / num 即可组成 k 的倍数" i8 j5 P8 u$ V; Q7 Y
           res += cnt[k / num];. ~: }, v$ f( r" G( E
6 t; h) e* @6 C- E5 S* Y; U
           // 使用 num 维护 cnt, 即 num 的每个因数 i 都对应一次 cnt[i]++
5 w$ V0 E" o, ]+ I$ e' H( V0 e           for (int j = 1; j * j <= num; j++) {
9 z. ]* p" x$ G* Y               if (num % j == 0) {4 }5 U$ z$ V- o; B% U
                   cnt[j]++;
2 Z. A. z5 s) X+ s- j                   if (j * j != num) {
3 U  {5 N1 J/ ]  k0 A* _+ H                       cnt[num / j]++;0 w* h7 k/ D, g. n4 _- C$ I
                  }5 K9 N9 A5 y+ v1 M
              }$ k; S* Q4 ~9 c% w5 p
          }
, e# j5 {. k9 H0 H9 Y. A      }
# U' @$ ^0 L" N% Z) ^3 ^+ J6 _3 c       return res;3 e* n" _0 a& r, G
  }7 ^  ~' |" h+ ^1 l6 {  v; y
. b# x% \6 P6 _
   int gcd(int a, int b) {
9 N* G1 P8 q( |. v( }& Y( I/ Y  Y       return a % b == 0 ? b : gcd(b, a % b);
. i* q1 l% O+ I" O. j9 S1 h# t  }) v8 `, \5 L. u
}
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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