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

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

上岸算法 回复:0 | 查看:49 | 发表于 2022-1-3 21:30:37 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 检查是否所有 A 都在 B 之前】! Q+ Z' T. S+ e7 B! t

! p- G5 X% N; g' ^( O解题思路5 X1 j9 q) M$ x* l! Y3 i' o: o  _! \
签到题。2 q' N- K! R, }$ n( e9 R
) G# S" A9 v# ~' b. Y0 K- g' y8 b
代码展示
+ W  d. e2 q) B0 g0 ^* T1 Z  Y: o7 w) Z' D, I: q( C
class Solution {/ m& k+ o0 B# k; F/ q
   public boolean checkString(String s) {
" v( X5 M) p1 G  J$ B) n& p9 X       return !s.contains("a") || !s.contains("b") || s.lastIndexOf('a') < s.indexOf('b');' z- H) K- o( I1 N3 t2 p, O
  }
9 B8 L4 G1 D! p8 _$ W) Q# E1 E3 k}
4 T) ?  H. q5 r9 ^+ P( e9 L7 r- |$ x7 I  q2 K) o; i
【 NO.2 银行中的激光束数量】
4 Q( c2 r+ d' }( y
4 f; D7 q& p; x7 c. S# c: \解题思路
  X4 I; H# y1 ^( _4 ^4 c/ c统计每行 1 的数量即可,如果没有 1 则跳过。. H9 P9 k+ y% O" i
+ q; b/ D) s. r7 i( N, k
代码展示( Q+ r* V2 U$ m3 _0 {0 J, g! e
( Y' i6 h  ^% W" B
class Solution {* [# w2 X3 P3 ?) V' O! ?8 ~
   public int numberOfBeams(String[] bank) {
; o5 [* I# i+ L       int result = 0;/ z# S& c0 I- i: J' G" `: ^
       int last = 0;
8 x3 w; U8 t( \! a1 r1 {7 ]. j       for (var s : bank) {
( z/ @2 N5 N9 [3 m- v6 ~/ I           int count = count1(s);. `; ?6 P* S" z3 c& p5 R
           if (count > 0) {
* @. R+ d8 D6 e# ]' l$ v               result += count * last;
  _8 K7 n2 n/ \. N7 v               last = count;& `3 m0 q9 O9 C% s) q( \# x; ]! X! ^
          }
' e6 G6 Q. g, s1 r. S' Y' E$ K      }8 t. ^, w/ {! Z' x& n7 J2 V
       return result;- i3 Y. ?' A* [# M- c# z
  }1 H8 ]8 q4 X7 j! s

$ n) Y4 E1 w2 g$ E9 R   private int count1(String s) {
2 e2 P; s+ p& b1 Z       int r = 0;
' L. w1 E* q9 c/ c  ~       for (var c : s.toCharArray()) {
7 S$ H/ w) T, [           if (c == '1') {
& j1 v' n1 T. ]- A% N4 I, \               r++;, X/ b% G: g* B
          }
; _% ^% d" H! k) ~( t( E      }
6 n+ [+ |4 g' k6 ]3 H       return r;+ D7 i6 x' p$ E3 e$ M
  }; j. G+ b! ~, B3 m2 m8 @- @+ s
}. w$ y/ U5 d( X3 W( c: s% C/ b
4 k- B1 l8 f$ u2 [7 A+ A) ?6 H
【 NO.3 摧毁小行星】- R. q9 G' A1 h6 u- {
3 ]  `; F$ F9 `6 a
解题思路
) T" w  h2 b$ b% |( B  j. L/ B3 ~. o4 g+ u排序即可,注意使用 long。
1 Q' O9 T( X6 D4 u+ f4 ?# p
: i0 n$ e+ s5 ~& S( i代码展示! U3 Q0 J; \( C9 N( p6 p

: T& ]% a7 q7 Vclass Solution {
1 V$ m2 z* }" U  @, N0 E   public boolean asteroidsDestroyed(int mass, int[] asteroids) {
" L. R/ c# `8 u- b7 G5 F( S       Arrays.sort(asteroids);7 h. Q; |% \; F# _
       long m = mass;6 T8 c7 k$ g' ~
       for (int a : asteroids) {
8 q1 }$ J. A) V9 d3 Y& I3 `. @           if (m >= a) {, i) c$ w: K9 m3 H# Q4 u
               m += a;
! Y/ P/ P! M( ^8 h               continue;$ x$ M- x8 l/ b
          }
: E* h: f/ p' a; f4 S/ b           return false;$ x1 x; _( ]  s( Q
      }$ ?, I% o* K! S, P- t" m0 |
       return true;
0 Y+ k+ [: y/ m) O$ `& b# |  }3 i/ M, p! w# b+ f- l, U
}
6 L% d+ T; x/ Y; J1 U4 `9 E$ F
# N% x; m: F& ^& T' p" M7 g【 NO.4 参加会议的最多员工数】" q/ |4 G6 D9 _+ ^6 W6 o% g
& F4 F/ r  f8 G  W  a
解题思路
' B, _5 B% H  u  L6 L* U# G实际参加会议有两种情况:
% b  G& Q: S! Z0 i8 N0 ]) M* l* v2 S0 z! s- m' _( n. m0 {
刚好是一个环中的人参加会议,这样可以使得每个人都喜欢自己左侧的人。
5 Q5 {/ r# B; x' [6 P& J0 \! C
5 O3 B( w) o$ b2 {" X2 M有两个人相互喜欢,然后剩下的人形成一条链,比如 [1,0,0,2,1,4,7,8,9,6,7,10,8],这样不要求首尾相接,可以有多条链。" @" r5 Y1 n8 L. \; Y9 w
$ V2 T$ r* l. j0 p5 S

! N0 i1 y6 i6 b; l) M/ P, U: v0 c代码展示
0 g. Q' h2 C2 P- B2 K0 U* P
( ~' Q9 r6 N$ S; T/ u  l) Qclass Solution {, a9 |  M$ l( K
   public int maximumInvitations(int[] favorite) {
% L$ w; |/ o. H4 a# `       // 1 找一个完整的环
" D: l& p$ j5 D       // 2 找多条链
4 \& E8 ~! x% L5 P* C+ v       return Math.max(maxCircle(favorite), multipleLink(favorite));
7 s" b5 w5 z' ]+ W9 S  }. ?& l+ x3 l5 j" |

7 c; M' J' L3 }( B   private int multipleLink(int[] favorite) {! Y2 t* B" ~5 U+ v1 f0 G8 _3 L
       Map<Integer, List<Integer>> reverse = new HashMap<>();
/ D' D3 h+ C  S2 t* }7 f       for (int i = 0; i < favorite.length; i++) {8 ^6 l- v& K4 v2 d' F6 z
           int from = favorite[i];  x  {# s3 k. O* e! P
           int to = i;
! Q0 G: f  b3 U; i* [! i2 S& X' {           if (favorite[from] == to) {
  [  u/ s8 X% d6 y               continue;9 a# D" {  l6 D# }7 U. k
          }
' h: i4 C5 k  h# E5 f2 w: C           if (!reverse.containsKey(from)) {
* c% o' C2 T, B5 Z) `+ x* T               reverse.put(from, new ArrayList<>());9 i5 X9 I! [& [$ _5 F+ L' t( Z
          }
, D5 ]1 h# o8 G' _+ b+ g9 H           reverse.get(from).add(to);
; C' Z: w) k  k9 y  s      }, e- P, U  k* J- }1 ]% B
       int result = 0;% e; n0 Y8 J% p  r5 l3 ]
       for (int i = 0; i < favorite.length; i++) {8 q1 w5 v. z1 q
           if (i < favorite[i] && favorite[favorite[i]] == i) {
* m$ H3 f* r2 s: O% w' X4 R               result += maxLen(i, reverse) + maxLen(favorite[i], reverse);( b2 K8 P' p& ?2 @3 m8 q* e) {
          }4 C% \7 [/ c1 l. u. Y7 j9 ^% v( ~
      }
+ O7 v, E# T. I2 Y  M       return result;6 O) I" {9 `) g7 J; w
  }: }9 d9 N0 |' O- Z& }" ~+ y2 v
# Y7 R0 q: r& h1 }) ?- m) f
   private int maxLen(int start, Map<Integer, List<Integer>> reverse) {6 a; H* I! p0 ~9 a
       if (!reverse.containsKey(start)) {
' h: E1 B4 N+ I7 t. `# K           return 1;
7 O/ I9 Q$ ?8 g0 u      }0 n5 `9 G# y" X* G) U& t
       int max = 0;
8 L) v0 m$ N% m" s       for (int next : reverse.get(start)) {7 R) t1 J% O" F
           max = Math.max(max, maxLen(next, reverse));) v, `8 ~/ C: S/ Z" S! q* R
      }
, O3 Z5 l% ~- G6 b% @$ D  N" ~       return max + 1;
7 Z7 [: u/ ]0 B3 ~  }+ r* o$ o' _4 k$ n' i* o
4 t% u+ Z: Q) l7 N$ J' @. m
   private int maxCircle(int[] favorite) {
4 h& w6 ]) }9 o  w% G       Map<Integer, Integer> step = new HashMap<>();5 H( f* A, P" @0 _
       int[] max = new int[favorite.length];. P, ]' T0 T: h! Z' P( `6 w2 G* A6 Y
       int res = 0;
& D6 V4 w- Y! z. Q" }       for (int i = 0; i < favorite.length; i++) {
/ {- l$ I+ M- D           if (favorite[favorite[i]] == i) {1 w& Q' K7 B( c) P+ q& d; H
               max[i] = max[favorite[i]] = 2;
( H8 v4 _! C1 r( I' B7 @- j          }
: [7 q$ s+ J& w. x' D           if (max[i] == 0) {
1 o1 I. q& b9 [) D               step.clear();& y! P6 \5 p# c1 O  ^2 L
               getMaxCircle(0, i, step, max, favorite);
" Z) s5 m* l  h6 S: v          }9 v9 ?3 _% K8 U7 \/ a  Z5 X# i
           res = Math.max(res, max[i]);! |) S# s! \% I' ~$ Q) u
      }+ ], t. {, N: m0 n4 r1 t- H
       return res;( F3 g; |$ c' B# I) m& a
  }  C' Y! G+ n( I

  s, P) W  {$ p   private void getMaxCircle(int i, int cur, Map<Integer, Integer> step, int[] max, int[] favorite) {# G7 P7 k9 R' c
       if (step.containsKey(cur)) {2 l5 Z: L; t2 {2 f
           max[cur] = i - step.get(cur);
: H( l0 V! r, |' F7 L           return;
% }- }* j5 d6 }8 F" ]. D( e- n; G      }0 K" J. s' l6 K' y" Y
       step.put(cur, i);; k  ]. V  X! `' h; o
       int nxt = favorite[cur];
. s* `7 X- e; u3 A) n) f       if (max[nxt] > 0) {9 Y" @6 o0 f: \* h' y  Q
           max[cur] = max[nxt];
3 f( y) }0 O% Y           return;  p. Z& ^( S' B& e$ c
      }
0 ]" d3 G8 U. T- b/ ]* F       getMaxCircle(i + 1, nxt, step, max, favorite);4 s- D9 d' _6 a. |
       max[cur] = max[nxt];6 h  h% S$ Q2 ]3 }8 x
  }
: J# g# z. N) j! ^0 }( x0 v7 I}
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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