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

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

上岸算法 回复:0 | 查看:1526 | 发表于 2022-3-24 05:53:38 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 统计数组中峰和谷的数量】. z5 [3 P  P+ u0 n$ s1 @5 e

& h$ S, p% m0 U( v2 }4 }解题思路" ], s6 W  }! p% Q
先去重,再统计。
4 I% s* g% g$ |& S6 \6 R- o4 ]  m4 z+ L, s  P1 N  W- |
代码展示: m! J- [2 u# R7 u  N8 Z

" H/ Q* e' W$ Q  O8 o$ eclass Solution {
& L% k. V2 a. R   public int countHillValley(int[] nums) {/ W1 v7 ^% g9 l& I5 F) r
       int len = 1;3 S. k9 a3 u$ @7 b
       for (int i = 1; i < nums.length; i++) {
. G6 y9 g. C! S! T9 S           if (nums[i] != nums[len - 1]) {( U# |$ d; \7 D9 o' H, f/ q6 Q
               nums[len] = nums[i];- }, o( a  z1 T, G; }/ j- P$ L. y
               len++;
( @( I3 i8 P0 W$ t5 _6 z" W; P! _          }7 s3 i* u1 `. g- W5 z4 \2 M
      }( G4 l, p& ]! a6 I1 o
       int res = 0;/ G* O- P( o  l1 V" I: J( d* ?
       for (int i = 1; i < len - 1; i++) {
1 I; f) \2 P3 k           if (nums[i - 1] < nums[i] == nums[i + 1] < nums[i]) {
' [' J+ c: x8 V- j& C7 ]3 l7 o               res++;1 W/ Q3 h0 K; f4 q) P2 v9 n
          }
2 c# {0 |1 s( H( j$ f' Z/ n      }* A3 G3 J+ ], I( X1 U- |
       return res;
; t9 d' n. T+ l+ [0 @' m. w  }8 q* U0 H1 y) h7 o  i% b3 h
}
4 C& t# Q0 N1 u  b. T! n1 [: s$ H5 }6 v! }3 R- W
4 S# B+ l( k4 U7 E7 a
【 NO.2 统计道路上的碰撞次数】
$ s7 d% P2 Q/ I+ _3 d
5 y' J( B5 p( A解题思路
: e" i$ F% w- G) S从左到右遍历,维护左侧的车的状态,有两种:- M( d( b/ u$ q, g0 r, P
! L8 _7 _* ]) L: ?. {4 w
若干个向右行驶的6 t* a: x) b7 G1 B5 X1 y& ]

+ h, G3 T( K$ K# _5 l9 b2 K/ o停止
5 p6 o5 B! _- x4 C* b
# ]( d$ J! G8 _2 `代码展示
, B' Z9 P5 c, k# ?  X% W. x, J) ^
5 B0 n  m- X- c" ?/ Rclass Solution {9 ~) p7 g. A5 w
   public int countCollisions(String directions) {
" v9 @; i- k% e  }+ N1 U; ]       int res = 0;
# S+ j* B- V& q       int S = 0, R = 0;8 C7 O$ J& e6 c
       for (char c : directions.toCharArray()) {1 O2 H, A$ n: W1 G
           if (c == 'L') {
4 V& J% E6 L* t7 i               if (S + R == 0) {! p% N8 M1 K: J0 `* J
                   continue;- P0 k& P1 ~# H% d
              }! \5 C  X4 U" U, Y) e/ |9 X
               if (R > 0) {
  S, }) Q# `6 i. ]6 h" X7 Y                   res += R + 1;
2 d7 k/ P7 {& {# }, [              } else {
8 {1 l: U# X6 @9 @                   res += S;
3 w, {6 o  g+ w) {# m: V              }% P2 |7 y3 u, o  O: g) t$ k2 L
               S = 1;( u# E# ?8 P- I( v  n1 F
               R = 0;
3 C1 G3 D5 B" N6 J          }
9 ?! e  z; @& K9 z6 h0 E% e: D           if (c == 'R') {
5 `+ g- O- B9 u4 l               S = 0;# R2 W1 P1 }+ I; F" K
               R++;- `1 D! T4 u& K7 s- {# X3 E
          }/ B2 m. Y; y1 f- ~
           if (c == 'S') {
) ~  _; H, M9 I) T0 J               res += R;
$ e/ D! M6 v/ T0 e               S = 1;
2 C9 t+ c4 ?) c% d# G$ |6 d4 z- R               R = 0;: y& R* _0 J( C7 ~- u/ B3 m! \, p' ^
          }
7 p8 [5 w5 H' Q) B! }7 f$ E      }
5 {8 {+ a  n2 C: `- E       return res;- v# Z/ o5 L/ X! g, r% I
  }
; L. ?8 N" K  y* @}
. G2 n" G% H# E, `' v2 P! B  D
* S2 w3 m% U9 D4 s7 w! J( A
【 NO.3 射箭比赛中的最大得分】; g  m2 L1 @0 y; x0 c6 Z, J' A
- E' `; W" M- J- k# }% r% }+ S5 e( d
解题思路- Z, L; ~6 j6 D$ G! s5 v; F7 L
枚举所有的情况即可,实际一共有 11 个得分位置,枚举 Bob 要在哪些位置得分。) e$ f7 E, J: S! ]
! |( S" Q* G4 o
贪心地,当 Bob 要在位置 i 得分时,只需要花费 aliceArrows[i] + 1 支箭。
2 ~' I! q1 D5 X  W& D: k  U0 |$ o& u. a3 [6 s2 I  ]
最后多余的箭可以放到位置 0.
/ x0 U5 ^3 x( l* U
4 X; N7 k9 \) x# {代码展示
' u  \8 l0 x6 c7 n
- D2 q2 L& J# V( E" Xclass Solution {8 V; d2 a& u' ]! s8 s8 j
   public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
. Y& ?) P$ P; k# x! X       int max = 0;
/ a5 _. H$ {1 H) _, `) U       int[] res = new int[12];. s6 x3 H  T6 j& X. @+ X
       for (int i = 0; i < (1 << 11); i++) {
3 a- a' ]$ f* v           int num = 0;" ]7 y6 |; Z) ~
           int score = 0;0 g& C! \" [, q! z. J' R
           for (int j = 0; j < 11; j++) {' z6 Y0 Y! k+ T* q/ r. y; B& i) A
               if ((i & (1 << j)) > 0) {
' \$ G. [- C% e9 @- I8 J* y                   num += aliceArrows[j + 1] + 1;
1 b- o2 u4 ^. l3 ?% ?6 D) T: H                   score += j + 1;
, [# @6 ]# I. {4 s4 j, E              }+ o( Y6 s, L0 f4 E7 Y9 X9 p
          }
" C7 E: J5 p. P; M/ J           if (num > numArrows) {
4 G9 t. H6 d( O: w$ n; i               continue;/ n7 I; \' b! ^/ @6 i4 O: {9 p! p
          }
, y& p7 l8 N7 M0 h! `) K9 X& p           if (max < score) {
4 @* s7 G% f" v1 ^  _* @3 J7 H2 Y& n               max = score;
+ g% h- H, y4 X6 l4 P+ b               res[0] = numArrows - num; // 多余的箭& u& h$ g0 s' z* s8 ^" u
               for (int j = 0; j < 11; j++) {
; s& O8 o) j0 n! u  n                   if ((i & (1 << j)) > 0) {0 }! D# j4 y& N" m
                       res[j + 1] = aliceArrows[j + 1] + 1;
* R: I* ?+ {3 ]. a- F3 I% ^                  } else {
2 k" J( e2 r" w" z7 t4 |( M                       res[j + 1] = 0;
& C8 R3 Y: a; h6 D( O                  }
" S" P/ Y; [; e4 n& Z3 u              }) V8 I* x5 n/ g, d
          }# S9 v6 t6 F* t0 ^3 s4 W
      }
1 a/ P' w- U; b7 y; h3 g       return res;
; M5 V1 A$ I) G8 S9 ~; D  }  _. T* ]  ~/ ~$ ^
}
7 e5 K% {* z/ u5 ?; b, q* G! f: B; y% q+ Y4 g; J
, K8 X: s. V# p4 m8 w* J$ e/ ^. n
【 NO.4 由单个字符重复的最长子字符串】- `$ b1 Y: @: N5 K, x9 z: `0 y' J

6 b* B) Q6 z2 |) Y" D& W解题思路2 G1 S8 D2 T4 ?. u: ^0 s& m9 R
灵活运用 TreeSet 即可,详见注释。- n- T; C: t* A% T! y
8 p% k8 K8 H2 m7 |$ L# D
代码展示
& f: B: C# x3 n& e2 c) W$ @- h7 b; s$ B' F! d- B& ]' h
class Solution {8 u; v3 A. N$ ~% s: r

2 m3 }! F+ ?7 o) I/ P4 Y   // 一个 Interval 表示一段连续的字符
/ r, G3 Z6 s: q% [* v& U4 B   static class Interval implements Comparable<Interval> {7 |0 b  r7 s8 O$ W1 d* h
       int start;8 x( ]% q+ Q/ }7 a+ Y
       int len;
% C) b, r) v: n8 |' ]" u' p+ D       char c;
6 F' m; C" V5 {# i. y4 ^1 _* q
       public Interval(int start, int len, char c) {
- s! I/ q" i) H  i) w! P4 O           this.start = start;+ S/ e! b6 N. t; s/ R& |+ D
           this.len = len;
! {7 \3 c7 r; T7 V( C           this.c = c;6 {6 P9 x4 N+ Y
      }8 Z' l% Y" x  z& X

+ s4 A/ T$ N9 k9 f! S/ K       @Override3 u- ^" |2 N" O8 N) b7 c0 o; V
       public int compareTo(Interval o) {
& j; K" t$ V6 j3 T4 P3 e           if (len != o.len) {! M/ ^; h. h* k7 g% d
               return len - o.len;+ @- i  p" ^: _1 E# g
          }+ Z* H0 H+ M& l5 r$ H* l5 s, \. P: R# E0 W
           if (start != o.start) {
8 a5 Q3 [: m3 Q' c" z: w# P               return start - o.start;
* F7 d8 R% Y$ r          }
3 L# B0 J# c2 i. X# {' t           return c - o.c;/ T7 O4 K( @" s3 K4 |
      }, t, v. V  S) Z9 o4 y! X
  }
, X$ w9 u) @+ w. @1 W- [6 J  C4 m5 N$ I2 A4 @
   public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {/ A6 Y# G( n0 ~. P3 l) c
       // 首尾新增两个其他字符,这样相当于 queryIndices 不会修改字符串首尾,便于后续的处理
! X; ^5 q# `  G* Y       s = "_" + s + "_";
( l5 h; h: J% Z" |5 `! a' U       // allIntervals 按照 len 排序全部的区间" M% i. J& {. B, ~4 @8 K9 \
       TreeSet<Interval> allIntervals = new TreeSet<>();5 ?; l5 S: Q& g  H% B) J
       // intervals 按照字符聚合区间,即 intervals.get('a') 表示字符 a 的全部区间,并且按照起始位置排序! w% r- u" p' }% A( r6 \: J) W
       Map<Character, TreeSet<Interval>> intervals = new HashMap<>();+ N/ R6 n& K* o% r1 r! a& C
       for (char c = 'a'; c <= 'z'; c++) {
2 m5 z3 W: q$ ^4 b           intervals.put(c, new TreeSet<>(Comparator.comparingInt(o -> o.start)));
  ?# Y0 Z5 F- }      }& i/ v3 o' w" y& Z
       intervals.put('_', new TreeSet<>());3 e8 ^; Y4 T2 u2 a2 D, e1 @* `

6 I  s4 [& [' f: G, d       // 遍历 s 维护 intervals 和 allIntervals
4 {6 t' F  T& _       int last = 0;
% h0 n. m7 O1 k( l! t0 W' t8 |       for (int i = 1; i < s.length(); i++) {, T" v; m& U. b$ z, K4 k' K
           if (s.charAt(i) == s.charAt(last)) {/ \1 V$ G! M* @
               continue;
  h8 E) Y' E4 K0 `0 F          }" ?2 L; J2 l' @6 s+ Y6 H' S- O
           Interval interval = new Interval(last, i - last, s.charAt(last));2 H; k# K* g" c' `1 w
           allIntervals.add(interval);
1 B* g2 @/ B  m! ~! e           intervals.get(s.charAt(last)).add(interval);
/ b; D5 x$ j8 a% O- [- d; _           last = i;
& z, f1 z% X6 S2 X4 p      }
, C6 R9 Q8 _2 x" P       Interval interval = new Interval(last, s.length() - last, s.charAt(last));
4 ~3 O8 H# ^$ v3 L. O; ^       allIntervals.add(interval);8 c6 t7 U$ ^/ r5 |. p
       intervals.get(s.charAt(last)).add(interval);6 P8 W! ~# p7 W, M  k
" a. q8 J, {! T- \' z
       // 每次 query 调用 maintain 维护 intervals 和 allIntervals$ i. g5 k- o% D6 U7 }
       int[] res = new int[queryIndices.length];7 o- ?# i$ T2 g$ r7 E; L
       char[] arr = s.toCharArray();
3 v1 [! C) @+ }/ s; M3 `6 W       for (int i = 0; i < queryIndices.length; i++) {
1 y2 \8 I+ m4 c& h4 A7 _. g! b           res[i] = maintain(arr, allIntervals, intervals, queryIndices[i] + 1, queryCharacters.charAt(i));
" U( G4 h; u% Y" A6 c2 z' E      }: B7 t0 {6 M+ ~
       return res;9 u, [- f. u8 R, i
  }
9 ?( Q; @9 _5 o7 _# r6 Q; m4 f$ k8 g# E; X
   // 将 arr[idx] 替换为 c
- w' f: B! a1 O2 }+ ^( J* ~   // 维护 allIntervals 和 intervals
/ u7 S$ P- T$ M# r/ x) q$ R   // 返回单个字符的最长的子字符串长度1 K2 _$ q' X: g& Z3 m5 A8 B  y' C
   private int maintain(char[] arr, TreeSet<Interval> allIntervals, Map<Character, TreeSet<Interval>> intervals, int idx, char c) {
/ z2 [+ Y! U$ c: G       if (arr[idx] == c) {
) B8 s  J8 I- j5 a           return allIntervals.last().len;) D9 @! @+ v0 g* t, h
      }6 u& I$ o3 e0 G. c

* T9 ]0 v9 M$ U! P7 L/ r       // 维护原字符 arr[idx] 的 interval
$ n1 v1 B9 ?0 t$ d% o  H       var treeSet = intervals.get(arr[idx]);7 F3 H+ o1 k1 f* B  b
       Interval origin = treeSet.floor(new Interval(idx, 0, arr[idx])); // 调用 treeSet.floor/ceiling 时,只需要 start 即可$ r! j; d8 @5 V* X8 F+ H/ _. e* _
       treeSet.remove(origin);
) A% D  j! u( d6 D9 Z) y; P       allIntervals.remove(origin);
( i5 w, Y% e  D5 u. i       if (origin.start < idx) {4 c7 `6 M2 G( B4 o' D9 D" p2 o. O' R/ d
           Interval interval = new Interval(origin.start, idx - origin.start, arr[idx]);
4 u2 K! q& H' [5 |' P2 A           treeSet.add(interval);: o7 K0 \2 \- b5 s, e' K
           allIntervals.add(interval);
- ?; ^. \. _3 {' U0 h      }
; ^2 S  q! [" V* J. o       if (idx + 1 < origin.start + origin.len) {
/ c: c" z- N: w9 U( N           Interval interval = new Interval(idx + 1, origin.start + origin.len - idx - 1, arr[idx]);, E6 F1 E  o* Z( S
           treeSet.add(interval);
" X2 |$ U6 W# i. m           allIntervals.add(interval);
' B( f$ X% G) F4 I+ s4 K      }, R  j( n; ~7 r  ?" t5 P) |0 O

- h8 y- @/ `5 |+ N2 D5 R9 N       // 维护新字符 c 的 interval
7 V: v0 J3 s( e0 N( m5 y: a       treeSet = intervals.get(c);
- x; W$ ]; ~- X: e# K/ d5 C5 S       if (arr[idx - 1] == c && arr[idx + 1] == c) { // 左右连接
+ t4 X5 Q8 f  ~, h6 D           Interval left = treeSet.floor(new Interval(idx - 1, 0, c));
& q3 d2 n# ^0 ^0 n           Interval right = treeSet.ceiling(new Interval(idx + 1, 0, c));7 k( R: V  \. Q4 ^
           treeSet.remove(left);) e2 o$ K* l# ]- g8 F2 o: I
           treeSet.remove(right);
8 ~9 `( x1 Y/ d. A0 e6 J           allIntervals.remove(left);
6 ~; F6 z. G4 o; X           allIntervals.remove(right);
  [' @, i) \* K4 I( _           Interval interval = new Interval(left.start, left.len + right.len + 1, c);7 I! P3 _- l0 i. p: U
           treeSet.add(interval);: x6 Q. N5 }# R
           allIntervals.add(interval);
: w6 l$ ^& h/ k, Z      } else if (arr[idx - 1] == c && arr[idx + 1] != c) { // 左连接6 e: k; e! S0 B* U0 R
           Interval left = treeSet.floor(new Interval(idx - 1, 0, c));: s6 ]' h6 T9 X4 c2 L# I0 k" n! q
           treeSet.remove(left);
6 |2 l9 l* Q9 o" v+ t: U) v: V0 ~* [           allIntervals.remove(left);8 r4 u+ E, K" J+ P  G3 b
           Interval interval = new Interval(left.start, left.len + 1, c);8 h% Q6 `* S& ^* V6 `' @7 _
           treeSet.add(interval);
7 w  ?- n) i( U           allIntervals.add(interval);6 p1 [1 A* ]0 L- U" U
      } else if (arr[idx - 1] != c && arr[idx + 1] == c) { // 右连接
( z; W2 `" n! M- N' n/ h# j: |5 R1 f           Interval right = treeSet.ceiling(new Interval(idx + 1, 0, c));& T9 _8 E7 T0 x# s
           treeSet.remove(right);: F) L9 I  W, A6 Z( s) q3 [
           allIntervals.remove(right);4 i# {: q; }* v8 m, v9 i/ r: g
           Interval interval = new Interval(idx, right.len + 1, c);
( g# N/ T( W8 V' a           treeSet.add(interval);
, k- D8 {5 I& J           allIntervals.add(interval);; V8 S$ E6 w& k% B' ?4 j5 F  ^% R
      } else { // 单独一个- h; T1 N" }1 }& T" H! J
           Interval interval = new Interval(idx, 1, c);
$ H; H" [, z- H' C$ M' J7 q7 w           treeSet.add(interval);
. v0 Y2 }" Q/ F4 M" g: s9 t           allIntervals.add(interval);% d; x, m8 M$ N7 X
      }+ K! l; E* m0 r: k& \
2 e9 {& k) S9 W, g3 A8 C
       arr[idx] = c;
; E' z' o/ w5 q+ V- M  a/ G       return allIntervals.last().len;
9 c2 P3 p+ l' B1 {' f4 h6 u  }7 M, o; i% k, ~/ P
}
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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