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

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 检查是否所有 A 都在 B 之前】
* {; d9 j6 Z! O' g+ b3 X6 ^; Q3 v6 ], e2 K  D' Y2 {
解题思路
0 g0 E* o0 c3 C( F+ w9 [( r7 \% f& T签到题。/ k8 @) N9 `# O1 a: v( y( [+ [
/ G3 M! ~0 L; f2 z1 i/ Q
代码展示
3 Q) ~, ?  a1 O' D' l( d( l; V+ c, h; H# X  q+ G
class Solution {7 E6 [0 j" `+ M. y+ k% V' g
   public boolean checkString(String s) {$ Z! ?8 d- |# l
       return !s.contains("a") || !s.contains("b") || s.lastIndexOf('a') < s.indexOf('b');
. X6 `0 p2 F* v! q: O! I& p7 a  }
* p! `" w; d( c/ u! w}
$ y2 J1 G/ {1 K7 u6 e, C0 @3 \" Q/ S  Q5 L
【 NO.2 银行中的激光束数量】
- h; f6 W! c4 c9 Z* l( G( v8 M6 }/ a* Y9 t* a" k
解题思路8 K8 H0 g' g. R9 Y
统计每行 1 的数量即可,如果没有 1 则跳过。7 o. a2 |) o4 o* j

. r2 z- Z, t5 ?& |2 C- v$ u2 `0 d" F代码展示
: G0 ~8 ^. f, ~
$ v9 v  e+ Q$ l' N* M. dclass Solution {7 l( E9 [  ^! j" j6 R" S
   public int numberOfBeams(String[] bank) {
7 y. o* {1 ?& v' G$ N6 P       int result = 0;
/ }  y9 k7 f2 Q. F+ v' Y' H! X       int last = 0;% c& @5 t, G+ L5 g
       for (var s : bank) {  d8 L" u/ o6 {& B5 o
           int count = count1(s);% p! i# B% _7 J7 S
           if (count > 0) {
1 B* C; K) m! ]) K               result += count * last;* W% [: [; {/ L9 Q" P
               last = count;
; x4 L8 E  w. w; N: I  j: v  @" X9 D          }5 V! v; S  h0 `6 a! j
      }
& R- r1 R5 H8 {       return result;
" N% T8 V  R: t% J5 H/ X  }: L5 u- I/ u; W* Q8 y$ V
1 [0 G3 V/ l0 \" n& k
   private int count1(String s) {
: H: j  V" L0 n0 Y) S" m% O. r       int r = 0;1 C1 E1 O; I! {
       for (var c : s.toCharArray()) {
$ g+ y$ F$ v! F; ?           if (c == '1') {0 X( e( D2 u4 q9 z& M5 E0 ~# U6 l
               r++;, e- @4 h1 J6 Y7 U) @
          }; s/ R& G9 l/ }4 P4 J
      }
. ^" `4 }: x$ o6 G6 D; Q. K       return r;3 N( Z1 r/ G4 f* b9 d6 O; M* F; V
  }
" i: q) R* C4 n8 n}8 v; j, x) w% F7 O
( w5 N( s( C4 u9 s
【 NO.3 摧毁小行星】2 h6 N0 v  L- K4 t. T

6 S+ W) a% k6 Q! T解题思路
& }' I4 M& F: F( B$ w排序即可,注意使用 long。
( L! @, ^- E" H- Z: \+ x  F2 n
4 k$ `8 S1 s9 U$ _4 u4 F$ W代码展示
4 p* {1 K9 t0 S0 _  v% o6 f# I: m$ Z! ]" ~$ Y2 S
class Solution {) Z- Z1 `, `7 Q4 Q3 W
   public boolean asteroidsDestroyed(int mass, int[] asteroids) {: D2 a: x1 e& M1 v9 a2 S/ Y
       Arrays.sort(asteroids);
8 u0 b" F7 ~: ^; C4 o+ o       long m = mass;
# R/ u+ g* d6 N: m/ x$ `4 w       for (int a : asteroids) {- C! H/ f0 v( I$ {' e$ U
           if (m >= a) {
# w8 o+ T' o4 |               m += a;
4 G' F% Z# S. N9 u5 {* A, A( S               continue;
" D) x, i" V# c  q. M4 i+ J3 s# ]/ W- c          }  F: S( r# X7 F; E. `  u& y  T, Z
           return false;
1 H/ N4 y! \* M- {( V5 v4 q" J$ b      }  I* _2 c7 F: L! r: S+ a
       return true;
3 F- g7 @. i& F7 Q  }3 I5 I* {5 k: a. P' x2 `% H
}. V: b. {' {+ f, P0 e( {
7 d3 b7 }5 g  L" C: a6 S: L
【 NO.4 参加会议的最多员工数】4 l& [  {. V* ^  L3 G

" ^5 t: T% d( U: y4 Q4 {( h7 _解题思路  T. s- f/ X1 x# A$ R6 A
实际参加会议有两种情况:
3 R0 W$ @: Y4 x) H: n9 \, m. Y3 ]7 J2 I% F( J/ C& G
刚好是一个环中的人参加会议,这样可以使得每个人都喜欢自己左侧的人。
+ s* S4 M! l8 s& E6 |
/ E2 E2 p# J1 y* v有两个人相互喜欢,然后剩下的人形成一条链,比如 [1,0,0,2,1,4,7,8,9,6,7,10,8],这样不要求首尾相接,可以有多条链。
. Z, v  R, f8 H; R$ K. u$ R
3 T' a3 b9 [# h- o/ r
" w5 P: v0 o4 E. ^代码展示) U, z# f6 X$ d8 z  d* G, |
+ `$ P% P& J. v
class Solution {  L1 w+ p- I: g. r5 a3 x
   public int maximumInvitations(int[] favorite) {) P% }4 u( D+ [$ m$ m0 ^% L% v/ o6 J
       // 1 找一个完整的环
- [# g9 N7 K9 J; V9 u       // 2 找多条链1 l% F) y0 I$ r: o
       return Math.max(maxCircle(favorite), multipleLink(favorite));) H3 `; U. Z$ y3 t( h
  }
- R6 D! B, f! w% X# f$ s9 ~# T  J  t9 U. @0 x# Y
   private int multipleLink(int[] favorite) {) V' N2 c* S  E7 y- g, T
       Map<Integer, List<Integer>> reverse = new HashMap<>();
6 @5 `8 H: ?+ b3 r* L       for (int i = 0; i < favorite.length; i++) {
* _' K5 a8 u/ z2 C# B" r! A           int from = favorite[i];
$ N; M: B" o2 ^. C: \% S( m6 v           int to = i;) p/ g$ {# l; a: F5 Q. d0 {
           if (favorite[from] == to) {$ Y3 U6 S7 c; b1 b. Z9 h0 O& O
               continue;" ]9 ?0 B, e; M/ T. e
          }- a6 J% G0 x$ H2 |
           if (!reverse.containsKey(from)) {
' H1 `) M9 I7 _5 u! P: @' Y! _               reverse.put(from, new ArrayList<>());
4 Q1 U, S7 }: U$ h' k          }7 U$ m  _6 k# J  I* k
           reverse.get(from).add(to);
- R! l. g7 p1 |) q$ }2 D      }( `0 L, R  J5 \' h# u: j4 u) N
       int result = 0;
1 d' @' U7 {9 a& ]       for (int i = 0; i < favorite.length; i++) {$ H# A. k4 a. v' }; {/ a
           if (i < favorite[i] && favorite[favorite[i]] == i) {
: C2 E$ ~4 d8 T               result += maxLen(i, reverse) + maxLen(favorite[i], reverse);
$ m9 J& p2 j0 D5 I8 q          }
) s: a  E; c7 q7 T+ ?" u      }& t! q7 [. ~( `! Z
       return result;  j6 M, r" O* C$ ?
  }
  H: A2 t9 R) k: H3 L5 X
) r, D: K) Y# k5 u8 a- p   private int maxLen(int start, Map<Integer, List<Integer>> reverse) {! u0 w8 _% |+ a. n6 j7 @0 w
       if (!reverse.containsKey(start)) {5 W( z* C4 Z% x
           return 1;
1 p, P9 G6 l: j  O* M' x$ w      }" J" v% A  q5 z7 U) _
       int max = 0;
0 u# T' I2 H8 C       for (int next : reverse.get(start)) {4 n( a- P# T  Q( B% E
           max = Math.max(max, maxLen(next, reverse));
: m! z% K# I, o7 o2 K- q      }
- R2 \' v' e4 a; y       return max + 1;8 g: T5 m  A0 Z) H+ B
  }% [. E- T" ~& \9 w+ E6 Z" l
8 c- r. @! I9 i
   private int maxCircle(int[] favorite) {
9 [" c( L! d+ G% m) a       Map<Integer, Integer> step = new HashMap<>();
- w( g  A5 E( Y9 C       int[] max = new int[favorite.length];
% @6 L2 B8 Y" T& t       int res = 0;
. q7 H$ T0 X( D8 Y       for (int i = 0; i < favorite.length; i++) {
* X: ?) K/ g8 I4 t' d           if (favorite[favorite[i]] == i) {/ H& L# L1 H; ], F) c- B
               max[i] = max[favorite[i]] = 2;
5 F  w1 P1 S( r, J* S# J9 ]          }- _4 R4 g  o/ Z7 q
           if (max[i] == 0) {
, I7 \$ h; ^7 p               step.clear();
/ Y3 D, k1 b6 U& O) i               getMaxCircle(0, i, step, max, favorite);
! ~; ^3 y, `+ I9 c2 _. D' F2 i' D          }4 ]4 [6 N4 v8 b
           res = Math.max(res, max[i]);
0 d$ R+ [' z; b( U5 X      }/ V7 w+ l4 l- p  Q) j2 m3 \
       return res;  n. L; ~0 e/ [' u
  }" G5 X& K2 y0 [: \2 z
2 t. X5 _7 b: [. N. M* v
   private void getMaxCircle(int i, int cur, Map<Integer, Integer> step, int[] max, int[] favorite) {
. {5 w! n9 H$ y1 U# L2 q3 f1 Z       if (step.containsKey(cur)) {
/ t" o. U; c0 Q7 y           max[cur] = i - step.get(cur);! a% ~- c& B0 z# f# o
           return;
" G  i. F0 Z! h) D7 r9 m  T      }4 Q6 C8 b% M: x) ^
       step.put(cur, i);( S# i2 Y: R; I' v  X% K$ ]' E9 F
       int nxt = favorite[cur];! w" u6 H) J9 g6 i9 {
       if (max[nxt] > 0) {
! x+ f2 b  r8 l% ^& O           max[cur] = max[nxt];' s; l( [9 l6 _7 U- B. [
           return;4 Q% J- k# t! ^2 n
      }7 B0 c" f- b3 n  F
       getMaxCircle(i + 1, nxt, step, max, favorite);7 g9 _/ b  g8 a& E$ G: v' E
       max[cur] = max[nxt];
: q, r: z1 x( w3 P8 N' E0 E8 K  }
2 U# x7 Q$ M. b) I4 ^}
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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