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

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 Count Integers With Even Digit Sum】" E0 V+ y; S8 t: E/ n

$ H+ \% Z, o4 r+ L6 U/ H7 c  w解题思路7 P2 w% }4 D& ?3 n6 d3 [; X" T
签到题,枚举计算即可。
0 c7 ]% h- }- P0 d
% K" [3 [) x* u/ ^/ f' f/ E$ P代码展示
- x# X7 B0 }  a- l1 G, t
0 v8 d3 k. R' @, {/ l0 }  _# Qclass Solution {
4 R4 I3 s3 |. ^* e- l   public int countEven(int num) {
; A5 _4 w' U; ?: ^       int res = 0;; E; s. t" o) z4 m
       for (int i = 1; i <= num; i++) {
& F. {$ u' X4 K+ B# I           if (digitsSum(i) % 2 == 0) {
3 @/ G3 k0 X) U5 o% U" {7 z: H# o               res++;& v9 G2 b. V8 R6 k6 B! g+ S/ z: U
          }3 N$ O+ F5 Z0 m# q
      }
/ F5 O2 i" U, K) Q# f2 s5 P       return res;1 u; \9 B/ q$ y$ Z7 y# b0 m
  }
0 D( `" p0 }. r# @1 B0 @! r! x- k- _& `3 g
   private int digitsSum(int num) {
! Z5 W0 Q' r4 w0 r       int res = 0;" b$ A; ^  Y& l8 H, ?) \- c
       for (; num > 0; num /= 10) {
6 J6 G( N/ `9 o3 D2 G           res += num % 10;$ p; v+ y$ t" b! j
      }, A7 }4 ~1 K: K4 I3 o+ d5 H" T
       return res;
& A9 U9 ^" y5 T  T& k7 e  }1 T- g, ]3 `. M7 G
}1 P7 j4 _/ j5 |2 E1 F
% X1 U; f3 t+ m) c4 k$ y+ Y* m+ ~
' ?/ S3 O. D. ]. A6 {. l
【 NO.2 Merge Nodes in Between Zeros】
& i* r! \+ w. n$ O+ D9 B0 v8 w6 p: J) k  W# D" n& h/ E8 Y
解题思路5 B/ X2 B0 A! I7 \# Q/ C7 \
遍历链表即可。4 i' z  D/ Q$ f. E# U, o

0 X3 q  A! C8 v: y! C/ x代码展示# ~) v9 C( V/ I% R6 ]( T3 m# `
. o2 H+ s, I$ k7 ?7 `
class Solution {! i7 K$ p, |; U* c  C7 n9 m% v1 M
   public ListNode mergeNodes(ListNode head) {9 V$ q% k1 T, T0 n2 [
       ListNode res = new ListNode(0);
" k. q- i9 ]3 s4 K" J9 }5 }, m       ListNode tail = res;
  k1 g+ e8 D" A) Z' Z       int sum = 0;; @2 i% v7 z8 d! n- V& x0 ]; `
       for (ListNode cur = head.next; cur != null; cur = cur.next) {
8 N/ M. I1 |! _2 P8 U           sum += cur.val;' d* u  W/ H3 H' o6 s
           if (cur.val == 0) {* M' d  R) |- J% P' a2 T4 L& \
               tail.next = new ListNode(sum);
. b! @+ |3 ]: m$ }2 l/ u               tail = tail.next;
* F$ J) w' e* }  ^# K# x               sum = 0;, \- t( t$ n6 |- u! l7 \
          }  k3 |6 {/ e8 y- J( G: Z- @  m
      }
4 y0 o/ \  R( j+ `9 C+ c, F1 w5 {       return res.next;: u& ^$ _* {0 B  ~1 G3 `
  }
$ h" t5 a- l+ h0 }1 o, T# @}
2 z' k. T, r! e+ j( c: H
4 H! o; F5 L1 i! I0 s9 A/ X0 E. ?0 ]
  s+ O' d' e' P2 T4 \- U【 NO.3 Merge Nodes in Between Zeros】
# n: Z$ X& }5 V2 S  j* [! i
7 S$ S. y7 G7 U- l# c解题思路& s1 v( T: g9 m/ @
注意题目描述:“不必用完所有的字符”。所以直接贪心即可,从最大字符开始,只要连续超过了 limit 就使用次大的字符分割一下。$ C4 E. N, Q4 a4 O  U

1 s! _) P4 J6 z: x1 ^) J, }代码展示, M* N2 j7 b5 U9 a3 c; a! c. _
" A- W! B4 T% j
class Solution {
9 v6 a  ?6 m0 h9 H3 u   public String repeatLimitedString(String s, int repeatLimit) {$ U( m: U3 O7 W( R: `
       int[] cnt = new int[26];7 Y/ z- {8 ?; i6 I0 G- b, K
       for (char c : s.toCharArray()) {0 x& N( U$ V/ t, \; s
           cnt[c - 'a']++;
0 B, Y4 y! P# y7 }' M  a( x, x      }! ?& z9 R( C; \: G

  n4 i$ L! M0 g5 i2 X       StringBuilder sb = new StringBuilder();& l0 f/ I3 c. L' B
       int repeat = 0;
0 Z0 {# m5 d2 I6 K/ U* u' K, s       char cur = 0;2 k+ Y1 A9 H" @, q( v& w0 z+ J
       for (int i = 0; i < s.length(); i++) {' Y$ w; P7 [4 @5 E
           char c;9 C2 M( C& u5 C! O( L8 j1 F
           if (repeat == repeatLimit) {
" D# q& [& n7 }               repeat = 1;
# P: m" j. p) V6 j3 z3 T               c = poll(cnt, cur);% `# N) S3 f  {$ _- s% |; O+ ?7 j6 t
               cur = c;
; C7 e2 K$ J5 J" G          } else {
1 P% ^& a9 k0 L! K( K6 T+ N               c = poll(cnt, (char) 0);
5 L, C. Y; x) T2 l, @# n               if (c == cur) {, U- ^% s9 N9 y5 ]* Q1 M, n
                   repeat++;/ `- P9 x; @! O& f9 d3 L  T" y
              } else {/ J0 H) y, i% F" J& U- s8 {( @8 G5 S! m
                   repeat = 1;) z7 x* Q8 M; p5 v+ q$ i
                   cur = c;
6 l& D: d/ g" d- Y6 W7 q( r; e              }+ U9 q9 p$ x8 ]' z
          }
3 H# T) s% p8 I2 A7 X           if (c == 0) {
0 I- b" K! g. Y. m- g2 m& z) B               break;
4 H  w. i! n; K$ q) i5 Q          }
, M. s2 p8 \9 J; j  ?0 k           sb.append(c);
1 ]% b( ]5 o4 t      }. ~( {' J; ^* A3 B$ y* O& _$ D& W
       return sb.toString();& ?3 V# N* b) @+ c6 y
  }
+ G4 G3 W$ d& @! r5 R: R! ?8 G8 [
" n1 H, J  A8 `4 O+ o$ r% |" _   private char poll(int[] cnt, char not) {
6 Y$ P$ v! g  ~  Y       for (int i = 25; i >= 0; i--) {/ p4 p$ S: \$ ]; Z. Z, |6 Z; A/ [" v
           if (cnt[i] > 0 && not != (char) (i + 'a')) {- C0 o4 E1 b3 r5 X# S
               cnt[i]--;
* O6 @1 E* m# A+ o! }' z               return (char) (i + 'a');' R7 g4 F. J( a  S( z9 V
          }4 k  M7 Q; a2 d$ ?4 n
      }% A: ?* a+ H% G
       return 0;4 h; G+ M* H( J, ?) V
  }
1 ^5 Z* \7 j# F, G}( ]* t/ q. m% z- j4 K6 C8 U, ?
" o5 K& Y. @* Q8 r
% f* n8 W. X" a3 ~1 [2 W8 F* o7 A5 r
【 NO.4 Count Array Pairs Divisible by K】
/ K( f0 K4 M% E) ]! T  {% X" P. g& |0 P3 Z! [$ A0 q  ~3 s
解题思路
+ l+ @" A: {* `' m8 H预处理转换成最大公因数,详见注释。' k2 {& t* f, V% X( k( p6 f
4 n; V/ \6 D6 I+ u! b
代码展示
5 _  C. w- r6 X/ w% D" j# f) l
$ p% A1 E8 J: |3 v% e1 S2 }class Solution {
  ?" F% c6 u$ O% _+ C" h! H) l! E   public long coutPairs(int[] nums, int k) {$ I- V& S% s+ _, z: }' u' \* }
       // 将 nums 转换成与 k 的最大公约数( p% q/ E# a- M; \
       // 因为每个 num 中,k 的因数以外的部分没有意义 (即使做乘法这一部分也无法帮助结果成为 k 的倍数)1 V, K  @  d! E' M8 ~6 C
       for (int i = 0; i < nums.length; i++) {( C* v! F4 @: o0 S. H) {
           nums[i] = gcd(nums[i], k);, N0 j6 P) c9 e3 }0 D( M: a! i
      }
7 r: j. z# ^' m% \9 k       long res = 0;
) f2 [4 d2 W7 ~       int[] cnt = new int[k + 1]; // cnt[i] 表示因数 i 的出现次数
* B& [8 i, d. A9 l       for (int num : nums) {& e0 x4 |" m8 U3 f
           // 经过了最初的转换, 此时还需要因数 k / num 即可组成 k 的倍数. F4 m; K( N0 Q8 e  V
           res += cnt[k / num];
" p8 w; Z1 @) b; e' u
; T, A, \4 U% L, w% q: V           // 使用 num 维护 cnt, 即 num 的每个因数 i 都对应一次 cnt[i]++
9 z* R% k4 b  I8 w0 x           for (int j = 1; j * j <= num; j++) {
; [7 l* a, O3 o, c               if (num % j == 0) {
3 j+ u, a& O7 x) @6 ]                   cnt[j]++;
) c: P% p) s2 K& C                   if (j * j != num) {* X! I) D; _$ J
                       cnt[num / j]++;
1 c0 W- b4 U8 M9 M9 R% e- n9 z5 ?; t                  }& _* X, |, N; C/ k( S5 d
              }4 K  X7 y9 J5 H& M
          }+ e2 ^' N- D6 R* W% e3 `+ O0 P8 k
      }  w. @$ o# U3 G0 g
       return res;, ~; w2 R2 h% G3 I
  }) [' v+ {9 A: o# K" l
, T6 y! C! F6 L6 K& w/ ?
   int gcd(int a, int b) {
$ ]/ O1 Y) u- _+ q* A5 T* b) k       return a % b == 0 ? b : gcd(b, a % b);8 p% {8 r) l4 H8 u4 I
  }' u: R. ]5 U& ^  E- e9 Y% P
}
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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