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

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

上岸算法 回复:0 | 查看:1828 | 发表于 2021-11-28 19:33:10 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 找出数组排序后的目标下标】! _, m0 P, `7 B6 |" h! X9 w4 }7 n
解题思路
- j6 g6 s& b% f% {/ |6 g! F# J签到题,循环判断即可。
: }( N# d; ^5 ?1 O. S4 Y* l5 v# y/ Q8 `9 C3 `3 Q$ U
代码展示$ s+ i% U, i4 m9 Z  r2 w/ t: P* u! V
4 w; |2 o' _9 d% F$ L6 x* R& _
class Solution {- m' o* {' Z. y' Y# z7 v
   public List<Integer> targetIndices(int[] nums, int target) {8 q$ Q6 ^6 |' }( B, z
       Arrays.sort(nums);. _+ R8 e. D$ _1 H+ k7 h: i
       List<Integer> res = new ArrayList<>();
) j6 W. e  T2 E: D8 p. U       for (int i = 0; i < nums.length; i++) {. o' I' X1 F" m6 M
           if (nums[i] == target) {
  b# S5 F7 E/ Z1 o! g6 y0 O7 e# a               res.add(i);
2 v$ c6 Z) t- L' n* ^4 w+ X          }
5 M! |  K! h$ a! `      }
/ Y+ {5 H' [& ~9 P       return res;
% c+ P' s, I" U8 m8 Q  }3 R& m/ a, h& Y
}: I- v* u. p9 Q* F

8 P- y2 R" I1 g6 O* X  y【 NO.2 半径为 k 的子数组平均值】7 O  r+ `! h, w6 k
解题思路3 x4 D. P% n2 A# d0 p3 |
使用前缀和计算区间和。注意使用 long 类型以避免溢出。, U4 @1 n. S) n0 G* F$ R
$ y4 A1 ?4 w, O4 \( w" }& A
代码展示
. V2 E2 n  p6 f+ s# X
' b% I( v: q( y0 P* Qclass Solution {$ V! z5 Q4 S; V8 j# o
   public int[] getAverages(int[] nums, int k) {7 p& ^0 ^1 p5 t1 _( a
       if (k == 0) {
5 y, i8 [5 _: Z0 k) u: E" f8 {0 J           return nums;) w- s. l* ?; \7 o: D, r
      }
% E- L+ ]+ {/ N) `# W2 I6 ?       long[] preSum = new long[nums.length];
+ f3 ]* f) a5 g/ d) x- u' H/ f       preSum[0] = nums[0];8 Z' P  w- _  {# O
       for (int i = 1; i < nums.length; i++) {
$ y* h$ q- |7 i. D: r! S% B  h           preSum[i] = preSum[i - 1] + nums[i];
% v* k, E/ h1 M! ^      }) Y+ d$ s3 \' s" n5 O
       int[] res = new int[nums.length];
) [# X4 p9 ~% U. `& e; ~( {: M8 C, I       Arrays.fill(res, -1);) m1 R! C& T. T  u) X' U7 ^8 Y
       for (int i = k; i + k < nums.length; i++) {( K/ v4 q" J  {
           long sum = 0;" [+ N7 f  C) x% b: o
           if (i - k == 0) {
+ f$ c& @$ T% X& X               sum = preSum[i + k];3 p  G9 M/ Q: M. I
          } else {3 z* W* c/ c, r, F" n1 d. f" I
               sum = preSum[i + k] - preSum[i - k - 1];& F# l" O  c) F- ~
          }3 N) G* t4 P/ r# r+ @. S2 {& Q$ c
           res[i] = (int) (sum / (long) (k * 2 + 1));
! Q6 L8 n9 ^$ \" V8 B      }- `; ^% v2 s; C4 }6 }0 c; o
       return res;
- R7 k$ |; ~% e  }& ?0 m+ }7 U) _# u. B
}+ B) A; t) E0 ?8 t- O" R
! H, A- d& s2 @! |
【 NO.3 从数组中移除最大值和最小值】6 A( `0 b8 Q9 v: w
, h& X5 {# w+ Z
解题思路
+ C1 Y$ u' r7 R* V+ u贪心,按照最小的花费移除即可。详见注释。# g. U* @0 Q  V; @3 s. _* v% p

  B0 s8 W) p; Y! b代码展示
" V$ y$ n/ L5 u& u) K
" O5 G% q. Z' o/ u6 g! T$ k5 Jclass Solution {
+ G3 z( M2 s0 e+ ~$ C9 M! d1 M7 Y   public int minimumDeletions(int[] nums) {6 D" i; F6 J" G9 L
       if (nums.length <= 2) {; R* s& Z$ H; v$ X0 x
           return nums.length;
6 C3 d  |  q# k/ q+ F      }  i0 r, c# Y8 R0 ^7 I3 a
       // 找出最大值和最小值的下标,由于 len > 2 且元素互不相同,所以最终 max 一定不等于 min
: l$ h9 g8 W5 o) Q& v2 _       int min = 0, max = 0;1 I; }5 j; _/ R3 D
       for (int i = 1; i < nums.length; i++) {9 K: d! }: E! K2 B1 [2 E5 T
           if (nums[i] < nums[min]) {6 j- i# P+ L" b
               min = i;5 c- ~, r1 i' U" ]
          }( R4 u; j4 P6 x7 I0 K. O* r7 [( T4 {" L
           if (nums[i] > nums[max]) {
' u, J- U9 r! Z               max = i;7 D  o$ P! W% J6 G4 [8 J! |( B
          }
+ D& y% J8 T! b. A      }
# p- T; X$ Y; q) P+ `8 n) d       // 要移除的元素下标为 max 和 min
& Q+ n* S" p/ y$ {+ |       // 此时我们只关心下标,谁是最大值谁是最小值不重要; q* o/ m( h! \# X3 b
       // 为了方便处理,令 min 为较小的下标8 F' ]0 J. P0 e; V" x% @; N# R
       if (min > max) {; E4 }) B* K. H# z! W0 A
           int t = min;
$ J, u  \  A% W4 l           min = max;3 z4 J# D( q& [
           max = t;
% X) t1 `' v2 q1 n      }
& ~: q! e% Z4 i+ @  x       int res = 0;
1 S' N0 S/ p; X/ o% V2 g. V       int left = 0, right = nums.length - 1;
5 S- y% M" v8 J: x1 d       if (min - left + 1 < right - max + 1) {" ^& t2 B; T: f
           res += min - left + 1; // 贪心,移除 min 需要更少的操作,先移除 min
  ^! Z1 B: X: _& u) l) x: v, [           left = min + 1;
- A. _* _1 I! S. C" S3 B7 P           res += Math.min(max - left + 1, right - max + 1); // 然后再移除 max4 t4 `8 a; R: g. P5 S; G4 o  |
      } else {8 _4 P0 e, o6 d+ H0 n; r+ D( G
           res += right - max + 1;7 F9 C( u5 Y) j5 m7 }2 n
           right = max - 1;% d( f! Z, r  R' U. s: H
           res += Math.min(min - left + 1, right - min + 1);! B. p5 Y+ C$ K2 o2 k) p# \
, V1 g$ m; f" k0 z% L, _! h
      }
8 d* B& J* N5 N# D7 I3 _8 V       return res;- W+ }* n( t8 `* P( i7 `; M) ~6 `  H
  }) y. V0 e3 E4 b8 U* ~. q
}
: y' c) \" O; R' d1 [  }# c* f3 \& t& \7 v3 x) L
【 NO.4 找出知晓秘密的所有专家】
  U. S* k8 g2 W) q1 [7 T
. q5 Q- e& [% Q$ r解题思路
; S0 c& B4 `$ D并查集,详见注释。& G% v. X; J' M* {9 A' q/ ?9 H" i

5 ^2 n" P1 Z" h' ?' Z9 L2 ^代码展示
  ?( b- v% o5 C" z; M; s9 r) q& \2 \6 o& `
class Solution {) Z( H2 a/ V( Z5 S: l3 U
   public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {: N( e% d9 B8 j8 [
       // 按照时间点将会议分组! d/ v9 A1 m" G
       TreeMap<Integer, List<int[]>> orderedMeetings = new TreeMap<>();
2 ^/ \& `3 F) O       for (var m : meetings) {
5 t3 x" c# L2 y! G: U- Y           if (!orderedMeetings.containsKey(m[2])) {% v0 S- ]3 T# i- \- N
               orderedMeetings.put(m[2], new ArrayList<>());6 g! J8 Y8 |; p2 ~" ?+ m/ l7 k
          }+ q/ n) B. i, }& m* r- t
           orderedMeetings.get(m[2]).add(m);$ K, b# x1 h+ s/ Q  K8 e( B. h) k
      }
3 a7 i1 ^0 l, G       boolean[] known = new boolean[n];1 ~+ U2 i: M4 H- M5 v' \) g- Z
       known[0] = known[firstPerson] = true;7 s: i( |: G1 O8 Z6 v+ ^
       while (!orderedMeetings.isEmpty()) {3 w8 c/ @  b2 o- a/ u
           // 按照时间顺序处理每一波会议
0 l& x2 r& h" k2 I5 L           var entry = orderedMeetings.pollFirstEntry();! I" @/ r6 E2 a
           var curMeetings = entry.getValue();
' C6 C4 a. E4 B. e           // 使用并查集维护当前时间点发生的所有会议中,有关联的人) y* r5 M' @! d( L+ g% |
           UnionFind uf = new UnionFind(n);
5 b5 t+ P  N) m( s: `           for (var m : curMeetings) {' d* B8 P3 V) M( s
               uf.merge(m[0], m[1]);! n" y& k6 O2 o( G
          }5 _, M# r3 ~2 Z& d0 T; \0 y
           // 枚举所有会议& f/ `: X$ r& \4 `& y
           // 若会议参加人 m[0] 或 m[1] 知晓秘密
' }' P/ x6 U) v           // 则把他们所在的根节点也标记为知晓秘密! w/ @7 \' T9 D; N0 ^% _) o
           for (var m : curMeetings) {
) T$ _/ G4 }  b* v* r8 F& [7 h, ^               if (known[m[0]] || known[m[1]]) {) x! X! D5 M. H1 W$ G  ?! n
                   known[uf.find(m[0])] = true;5 w  A5 S! u: d+ f) O
                   known[uf.find(m[1])] = true;( H% }" {0 c* }8 T- U
              }
9 d- S# Y! M! {: q- U          }- s( ]1 t" _" M/ B
           // 枚举所有的参会人,若他们所在的根节点知晓秘密,则把他们也标记为知晓秘密5 G0 r4 s8 W$ b* v# B
           for (var m : curMeetings) {
# [& T+ m4 Y% N# X0 v9 q               if (known[uf.find(m[0])] || known[uf.find(m[1])]) {5 ^7 b* @* ]) Z4 K0 r( }
                   known[m[0]] = true;+ G) k$ A2 U! Z0 [& k6 k
                   known[m[1]] = true;1 b! {# K" W$ ?
              }
. C' p- ^) |0 M: R/ h/ Z+ X          }
. i* J. l" w+ A2 L8 K4 ]3 z      }6 ]9 t9 K+ a2 d! I; n/ e! v& S- l% a, |1 e
       List<Integer> res = new ArrayList<>();) _2 n* R4 E% J  C3 }* m3 P, M# ?& L
       for (int i = 0; i < n; i++) {
3 k& W# b5 k3 s  p           if (known[i]) {
( s2 H$ x- p+ Q! A! R9 W               res.add(i);- S/ B4 r% \! ~* F% r
          }* q, W5 f$ q3 P$ P* j" I
      }
7 J3 i) H+ I" d6 d% A' y) g       return res;
1 J1 O3 V3 N  j  }
" b0 ~% i7 y, k5 h}  Q6 i3 V" ]9 Y: t8 ~
0 G8 Y2 C2 e0 J$ S
class UnionFind {
% y0 T" e8 S* W) @& F% X2 f   public UnionFind(int size) {* c8 y2 r2 m3 @' w* L9 z
       f = new int[size];
- U( C% s# t! u+ f+ @' P( O2 w       Arrays.fill(f, -1);
$ Y! n; L" m) N( M) H" z  }
# l- A# U0 Q% M$ D
7 T& p5 J. m* x* Q, u   public int find(int x) {
9 n/ o: M/ u1 k/ U- c$ q       if (f[x] < 0)
% F* z. X* ^* R; D# I/ C% D1 ?           return x;' }( b) x8 V  G
       return f[x] = find(f[x]);! x5 d* D6 w6 E" k; @! `5 G5 y9 u& k- y
  }% Z  y2 ~6 E; K% x  _' B9 K

5 i& W. a; @( ]3 p/ {& Y1 a; m   public boolean merge(int a, int b) {
& s" h% [# a; r8 g       int fa = find(a);
  H: i3 r4 ]) d3 M2 J3 G; A$ @       int fb = find(b);
' H8 v& k* p8 y0 ?  G8 v# c1 B/ T       if (fa == fb)
4 C" q. f; M$ K+ w' q( E           return false;
! [3 R* w) p) R+ b+ {- n3 L$ U       f[fa] = fb;  |% L1 W! N- H1 r3 |
       return true;
0 j- e2 d7 P8 O+ G, p) W+ ~  }& Y! o# i5 \) d; \  y( h

+ t$ h5 V2 J# G$ Y2 h" y: q   public Map<Integer, List<Integer>> sets() {
" l( J: t+ c, I( j: }       Map<Integer, List<Integer>> res = new HashMap<>();
1 p# r' ?# X" [7 ]       for (int i = 0; i < f.length; i++) {
5 N8 U- a- R2 X* t* }! N/ Q           int fi = find(i);
/ L% \1 y# I! |           if (!res.containsKey(fi)) {
, Z' A8 s3 v  l               res.put(fi, new ArrayList<>());
  P. d. t4 x2 s          }
9 n  {' ^. [) G: e/ X+ q( v           res.get(fi).add(i);
+ j& P7 l' d' s1 R      }
$ \- G- Y) t. w0 C( v" \' n       return res;
6 Z0 v2 ]$ m+ `0 _' l: N  }" v8 Z* y, f; K

/ R% _* F. {$ X5 P8 Z1 F   private int[] f;' K) [* W0 c1 R
}, W8 b/ Q; o0 q8 N4 `& |* |
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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