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

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 检查是否所有 A 都在 B 之前】
# {) k( n) i* j. k0 x. N. Y/ L1 }1 E% z# b; G+ v
解题思路3 F4 V5 k% w6 @9 c; G' Q
签到题。3 a3 h3 Y! G% L: @7 w9 \
( L% M: ~6 [5 d0 e+ U0 E) K
代码展示4 t: V* T6 s5 I+ g# _0 g' Z' I& U

8 Q( ~$ e0 Y  S* f4 Rclass Solution {
7 j5 s9 L5 i( K7 [3 M9 @' s) b/ F$ \   public boolean checkString(String s) {9 B2 E" P+ j/ \7 g% i: }7 c
       return !s.contains("a") || !s.contains("b") || s.lastIndexOf('a') < s.indexOf('b');4 `( ^$ A2 A2 P* [
  }, l' E1 S; p3 Z9 n+ O
}# e5 c* I6 C! ]0 S
& S# {' |, ~- j4 v  Z: S% C
【 NO.2 银行中的激光束数量】
9 c( D% I0 h5 H4 W, s" M- m! U4 S2 D# t2 ^1 }: T+ I$ Q9 I* R' Z- q
解题思路
, V: z2 d2 x' y统计每行 1 的数量即可,如果没有 1 则跳过。
" g2 P7 F, X8 N4 R8 T# ~6 Z2 t! I8 B+ C! m
代码展示; t! _' }- ~& i+ M
& E1 ?4 V  B+ o8 u- H1 j- A2 F
class Solution {5 w% ]- H4 L7 l1 s" b+ r, z
   public int numberOfBeams(String[] bank) {) a$ y% G7 b9 Z4 m* [, B- T
       int result = 0;
% Q4 b- |! }# N" u% ~       int last = 0;
9 @' [" M0 n8 r       for (var s : bank) {9 z9 }6 [8 _2 c! q2 J" q
           int count = count1(s);
) [& }+ K" Q( B7 G9 k           if (count > 0) {
1 F3 e* u+ X2 i. Y$ E% o               result += count * last;0 D7 @1 J  e+ U* o
               last = count;
' K: J9 H+ T* h0 F4 m( f          }5 w4 ^& M4 b8 D( N: P; s1 v$ J) U0 `
      }. |% X8 K+ Z) b+ ]
       return result;! i# {% C9 v. i: P
  }, P$ e$ X3 ]) C0 Y9 C# a
2 q' g* Z" H$ C/ C9 u' [
   private int count1(String s) {) n) \2 {7 |* T' L
       int r = 0;
1 \) v# h  T- [5 H1 W4 |, a" H+ I       for (var c : s.toCharArray()) {+ h8 z  R7 D% k- w
           if (c == '1') {5 x; F3 z% J$ X8 r
               r++;
" `1 H( l, ?" ^, {! Q& Q2 Y+ D' k9 E9 ?          }. l: I4 [+ ?0 S4 k5 L* Q
      }) y' p5 N" A- n6 q  f  h  e9 v
       return r;
/ V$ ?( `3 Z# o2 ]5 A8 }( ~  }
' P: Q( p" b# E  }}
, b. x$ D3 K) P3 F+ J9 A# j7 D
4 c0 B9 v5 {+ u【 NO.3 摧毁小行星】
- h7 k; ]) f3 l
- F2 D: r2 [/ J* b9 i# D6 K" _  i+ Y解题思路( _  `0 x7 V  H, p
排序即可,注意使用 long。
3 z4 M2 @7 C% u4 G2 b% p
' K: |. o/ X# Z% k代码展示# D8 C+ I' ~" J- d: y/ W
. x5 ^( @* Q5 i: m4 Z# t) J
class Solution {
$ H/ B1 O& i6 v: g6 U# `% n+ _; C# [   public boolean asteroidsDestroyed(int mass, int[] asteroids) {
$ Y2 I) Y4 j0 a3 \       Arrays.sort(asteroids);
& \, p8 _6 y  x8 Y4 s0 q       long m = mass;
4 B  O/ e* I3 Y. J% n: k       for (int a : asteroids) {
4 H$ y" W' E' c( Q) O- y$ h           if (m >= a) {2 b7 Z: i' U# C0 H1 E0 v0 I
               m += a;
; A* m! N9 x5 g1 [               continue;
% |) g. ?- m8 r/ O4 H- ?: x; R          }
4 |0 Z5 N% v0 S1 h, L* O           return false;
- Q/ w3 E, S: `" J. i! I+ O      }
5 Q" |- w$ t8 ^9 l6 F0 E       return true;
# y4 F4 e* d8 O3 ?' x, U  }8 e8 R, v; Q+ @# Y- x: q) w
}+ b8 o% X, R3 Q2 ~- d3 b

( X  d' [7 C% ?【 NO.4 参加会议的最多员工数】
; b- {* P  Y3 X
8 \4 t! R& }4 ~+ y" M6 w% z# K) G解题思路
! [$ \( }# c0 d4 [; @2 H实际参加会议有两种情况:9 g# G& ?* [/ u$ q; C+ ?" A" M

7 ^' n" n. X' q; R: z8 h. Z/ E刚好是一个环中的人参加会议,这样可以使得每个人都喜欢自己左侧的人。7 q, Y; H' c; D. z
0 `8 q3 Q- O1 L$ ~4 X: R: J
有两个人相互喜欢,然后剩下的人形成一条链,比如 [1,0,0,2,1,4,7,8,9,6,7,10,8],这样不要求首尾相接,可以有多条链。
0 m0 @, Y. N5 r, F
  |  L: X$ n7 S% I" e
0 l, q' x* Y* x0 V' e代码展示
5 C1 Y! s" X6 N, r3 h. x2 U7 M
# b% O+ U  j8 m* E' [5 C6 M' D) pclass Solution {) ]6 ~' p9 Q, U" Q1 t0 r
   public int maximumInvitations(int[] favorite) {& _8 s! E* S; f8 U: j) @
       // 1 找一个完整的环
0 h0 J; v3 P2 |% l       // 2 找多条链
% _% p( P2 V% L+ T1 ^) C; c  O       return Math.max(maxCircle(favorite), multipleLink(favorite));
3 L$ S$ }2 i# Z$ u6 G  }3 n9 e: H6 {+ H9 p; B+ G
; g; ?& I$ c, D
   private int multipleLink(int[] favorite) {: ^% h) L% H! A2 `7 l& ?6 O
       Map<Integer, List<Integer>> reverse = new HashMap<>();
: ^. m8 u* \- |% ?       for (int i = 0; i < favorite.length; i++) {$ v0 n1 S7 x) o! k2 m. X
           int from = favorite[i];
8 v5 r( o' J  \           int to = i;. s0 c* f! N6 J) m
           if (favorite[from] == to) {  `3 K3 J% a3 w: p: ?/ v1 S4 x
               continue;% G  z" r# x+ j! u+ ~4 Q
          }' U5 ^1 F& O. w8 @4 ?
           if (!reverse.containsKey(from)) {% M1 k( X) k* w: ^, L. L* U
               reverse.put(from, new ArrayList<>());
  {/ u/ x& v0 ?$ a          }
2 h6 ~! q, j5 W3 W( d1 Y3 \           reverse.get(from).add(to);' Z# \9 Y! U4 B5 h9 L7 t
      }& y1 G2 k# I: V0 y0 ^
       int result = 0;
9 c8 t, f; L' i: [7 ?: q       for (int i = 0; i < favorite.length; i++) {3 I* w+ ~+ {. c; H2 g! u, y- o
           if (i < favorite[i] && favorite[favorite[i]] == i) {  b2 D1 X4 Z" [4 N6 B" ?0 ]$ g/ J0 y/ |
               result += maxLen(i, reverse) + maxLen(favorite[i], reverse);
3 z* u+ J" t5 }8 ^6 ]" I          }! }# H& n$ t/ X3 e
      }
) p8 i" A0 [1 U( G; ]% {       return result;
  \6 K; h+ E: H6 F. M4 j# M0 c  }
- z1 f# U. \) P- g& I: }  p) q: N5 R, f+ j$ k2 b: }
   private int maxLen(int start, Map<Integer, List<Integer>> reverse) {
- W# T- Q, _$ U% S5 N       if (!reverse.containsKey(start)) {
* _1 t9 `$ a$ U. C7 B           return 1;
$ m! c( p8 |, @2 B' p      }
8 N2 s; G5 b' ~       int max = 0;
8 P" Q7 x8 J- y! D; E       for (int next : reverse.get(start)) {
: o7 U$ `- ?3 v% p1 W, O           max = Math.max(max, maxLen(next, reverse));
& B& P5 k# X5 h; H6 @" G# p      }7 q1 T/ r6 O6 k8 g4 G
       return max + 1;
8 p' N' ]6 b) y# P  }
9 r6 V2 B, n! G3 N7 ?* |1 c
) h6 `6 q; f, s8 x! H$ s! k" y8 l- `   private int maxCircle(int[] favorite) {
+ P. {% p8 j& Y2 q/ r  \: n       Map<Integer, Integer> step = new HashMap<>();, [' y9 ?) D3 ~$ Y) x% |) f
       int[] max = new int[favorite.length];: H  `& G7 }" W" ^& c% `
       int res = 0;1 @$ I$ X8 }1 |# V/ L
       for (int i = 0; i < favorite.length; i++) {
9 H+ T# t4 W6 A& h6 m2 G7 L           if (favorite[favorite[i]] == i) {" P3 s7 g( R' }- K) ~
               max[i] = max[favorite[i]] = 2;- H& ~! N2 F" Q6 E
          }
4 @2 X4 T/ y% @, z           if (max[i] == 0) {
! c, C& `% J6 K  }$ M8 _' F* s               step.clear();+ S0 f. g( B& t% F
               getMaxCircle(0, i, step, max, favorite);
4 ]* K. t& B! c6 u! S          }
0 c  U1 K5 [9 L( {0 P           res = Math.max(res, max[i]);
) w0 Y2 V1 C+ w  i4 X/ A# j" _' ]: \      }4 f6 ~  I; R- G: e4 b
       return res;( u- j( l0 x+ q% _& S6 P0 ^  @, l
  }
0 \! w6 d0 W! R4 x  g3 F# h, t9 x: o( a% u3 u" B
   private void getMaxCircle(int i, int cur, Map<Integer, Integer> step, int[] max, int[] favorite) {
3 s4 q$ E; w: J" N) }# X& y9 S! u       if (step.containsKey(cur)) {! ~. h8 H/ l8 L2 O2 c3 J  c6 _! D$ R
           max[cur] = i - step.get(cur);
) Y, I% U1 N( x           return;
9 x7 D, Z; L8 A: @) m2 o      }" Z, \) b& Y- ]1 ~3 M. l# p
       step.put(cur, i);& `+ T) G( ]! _6 }
       int nxt = favorite[cur];
! ?7 o- ^$ |/ f       if (max[nxt] > 0) {' R0 Z8 r6 A+ D1 P
           max[cur] = max[nxt];
& E5 O* D% i( ~! [0 G! p           return;
' b! V0 C  D4 _( t$ U      }7 k! @+ ~* r3 J0 [- j1 N+ |& d0 q) E
       getMaxCircle(i + 1, nxt, step, max, favorite);
9 b& h" H& G; A$ c% T; U       max[cur] = max[nxt];
& E& k' P0 i0 M: p! m. u6 F  }
& \+ F: h; ~4 M# |/ E}
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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