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

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 找出数组排序后的目标下标】
3 o0 k) d& J& E' k7 A5 ?  H% I解题思路
) C7 [2 W1 m$ m7 [: _7 K9 r- `签到题,循环判断即可。! e4 V) E& M( A, M
. x9 c3 d) I, z- q4 I1 V
代码展示
' t: s/ K1 w9 i- ^2 v3 x) @8 a( n
class Solution {$ f& T: o8 e' ^  J* e6 f9 G
   public List<Integer> targetIndices(int[] nums, int target) {3 i6 M5 u, I' h
       Arrays.sort(nums);
3 c" w) i$ _# o2 \8 F" K       List<Integer> res = new ArrayList<>();
+ q4 @, c' \0 X* s. O' \       for (int i = 0; i < nums.length; i++) {5 E# T# Y8 ~3 D/ U* v
           if (nums[i] == target) {
3 n8 _% T9 ~( I2 `- O               res.add(i);) I4 Z2 F. w1 @+ _0 W/ [0 C
          }) F7 T+ j+ m" |( b7 U4 c, F
      }& L" r' t+ P2 }
       return res;
& c9 a( e8 |: x- z! t1 h8 }  }' A5 N( ~' }3 i( P, f
}
; c$ c6 [& Z' `, `1 Q2 g2 u: n2 t+ t( u# S5 u
【 NO.2 半径为 k 的子数组平均值】; L2 V" k, w8 z( |
解题思路
; o) n: }: E+ E- G% I使用前缀和计算区间和。注意使用 long 类型以避免溢出。  K# e$ q( ?7 f3 i) `3 k. e$ C

: N- {/ B1 n4 a; t8 u& k2 @$ P" i代码展示8 A0 q8 w0 m  I+ Q) l
, I5 g3 U0 M4 `3 G+ F
class Solution {
8 f% X; Q4 {* w. l$ v) F1 o! V! L& q   public int[] getAverages(int[] nums, int k) {
3 T( P  P* |4 Y: U+ i( O0 S       if (k == 0) {
$ X' V4 c* Z! v; E' Q           return nums;* c% f/ i- U/ Z. X' r+ ]
      }$ A" m5 F3 ?6 a# N
       long[] preSum = new long[nums.length];
* |* D# }3 K4 P2 M+ P: {       preSum[0] = nums[0];) v& F- y7 n, ~* @" ]- I
       for (int i = 1; i < nums.length; i++) {
- k/ x7 }. c+ {1 a4 \9 A           preSum[i] = preSum[i - 1] + nums[i];
- l6 i: ]) I- k0 J2 |' \      }/ x  O% \8 `( ^9 f# D2 j
       int[] res = new int[nums.length];- b7 [) n1 [" |6 P- g: P/ O/ r! U
       Arrays.fill(res, -1);
& I; \) Q, H' a- Q$ e) u       for (int i = k; i + k < nums.length; i++) {4 |; o2 r- `# O+ @8 R% P! M* M
           long sum = 0;7 I, K0 s& t) e: N
           if (i - k == 0) {* l) T: @0 P0 z& E
               sum = preSum[i + k];
7 F$ y2 B" M$ H/ \4 |          } else {
& W: _0 }: x) d7 \/ j* H, c               sum = preSum[i + k] - preSum[i - k - 1];
% |( [6 S9 T2 F9 z: m$ D' l          }) z! N2 ?5 ]) o) w3 H2 J
           res[i] = (int) (sum / (long) (k * 2 + 1));* x9 @; }, K  G2 X" Y- A
      }
8 C4 a! P, y8 K0 ^6 H       return res;9 I; _  F) C- N% ^6 T
  }
9 t) a% }& p: h3 a4 [- v}
$ Q" U2 u+ ^8 j" |4 L7 D& ~+ [5 j+ `+ ^8 N# W
【 NO.3 从数组中移除最大值和最小值】( n4 B5 b& Y5 f1 M" g2 Q
) [" p8 |/ q" n/ V
解题思路7 ?7 e7 E% a; t, a: d! n, k; R& s6 M& c
贪心,按照最小的花费移除即可。详见注释。
% D0 ?* n/ |" s  g% Z
/ a$ ?, b8 m7 S2 Y8 m# _3 h代码展示+ y8 y9 `- N2 C$ b) t' B

) K2 a+ |1 h/ f. ~, gclass Solution {
# [, E, r( Q$ U+ E4 E8 B   public int minimumDeletions(int[] nums) {
/ g7 N7 M+ I0 W( d9 D       if (nums.length <= 2) {
4 f9 m) j! B# a" B$ C0 n           return nums.length;
+ e6 V: e9 L1 G0 q. B      }
+ c6 ]) V; o, k, s       // 找出最大值和最小值的下标,由于 len > 2 且元素互不相同,所以最终 max 一定不等于 min
5 U9 X- |+ d8 Q, M       int min = 0, max = 0;
% K+ }* o& L6 z* d( j+ F; v       for (int i = 1; i < nums.length; i++) {" M2 y, r) G! D0 F, W
           if (nums[i] < nums[min]) {
& N/ ?$ Q9 A% P( H! k! l( [, p               min = i;& S8 N$ a  Y/ o* M
          }
: v" x% {6 T/ }/ _+ G- g" l           if (nums[i] > nums[max]) {9 Q2 ~; X* _& \, S* i) p
               max = i;4 r; T$ ?, T: h# @3 |6 m
          }2 \, s+ u# i% R5 ^+ ]1 N
      }
8 I, t0 v: p# C+ ^  R, v       // 要移除的元素下标为 max 和 min" a+ _. D6 P& U
       // 此时我们只关心下标,谁是最大值谁是最小值不重要4 g  D% [+ E' [: L
       // 为了方便处理,令 min 为较小的下标& |* L8 L7 `: w( X
       if (min > max) {
7 m$ J7 ~" W; T( i           int t = min;
  d2 |! M1 A5 r  U           min = max;0 u7 C/ A- G: W: ?; d! a; {9 n! H. }
           max = t;9 l: R  t: A4 b9 _& l
      }5 Y- [/ e5 C5 A: {& ?
       int res = 0;
0 H% H' ]5 x1 r- E       int left = 0, right = nums.length - 1;
& v4 e' D1 Z! Q! A% R7 a       if (min - left + 1 < right - max + 1) {
+ M: _0 ~! Q$ }2 \4 ~- o           res += min - left + 1; // 贪心,移除 min 需要更少的操作,先移除 min+ r4 e# k) E$ [4 m) W% w
           left = min + 1;
. ~' y' B5 V+ J8 l           res += Math.min(max - left + 1, right - max + 1); // 然后再移除 max2 G" W& m" w+ e0 s1 w& p  |+ ~. i
      } else {: f5 {6 T0 f9 c
           res += right - max + 1;
8 @$ _$ A6 O* t+ m8 n& U           right = max - 1;1 d! N) s( [3 @" h$ d
           res += Math.min(min - left + 1, right - min + 1);2 x% |, p' V# @) F7 m  ?8 U

3 B8 _1 T$ V9 Z% E( Q) ]9 |      }$ S% M7 A7 `& B5 z5 _. h4 ?9 {9 B
       return res;
  ?! {' i" s; g& i7 P' v! |4 f) O  }; ?1 h' T+ S% B
}/ s2 R' d* Q6 A# k5 }& N! p
% {. n" o4 l9 \; t) b
【 NO.4 找出知晓秘密的所有专家】
9 v0 f+ Z3 o4 J* T8 D" o6 P. I, w0 A- a  w& W) M# L% r% b
解题思路
$ z: l/ b$ Z) ~6 @1 Q$ I并查集,详见注释。
+ Q, t) v4 q0 D7 |* B( W4 d: s  Y+ Q5 F: f% }7 u
代码展示9 J7 y6 d% B& c0 ~2 K/ k
8 f6 W5 `5 \8 M; i
class Solution {9 O0 N( A/ P- @9 S
   public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
: z6 \3 M5 D, [4 p3 Y       // 按照时间点将会议分组
- T$ A9 \/ \3 F  l3 c4 m8 C: ^2 {' a       TreeMap<Integer, List<int[]>> orderedMeetings = new TreeMap<>();$ W6 c0 _3 {0 I0 ?; n' o! C
       for (var m : meetings) {
! K6 F' X7 q" t- f( |           if (!orderedMeetings.containsKey(m[2])) {
& i- z" G) L2 Y& \, ]! |0 a. x2 F               orderedMeetings.put(m[2], new ArrayList<>());3 z) {1 P8 S# `! H
          }
' \3 [- b" x6 l& ^. E" u$ o           orderedMeetings.get(m[2]).add(m);; g% P* {* _8 @" X6 f
      }) J. h' {% L5 T" u8 n: N
       boolean[] known = new boolean[n];
8 \" y# E, v% ^6 C       known[0] = known[firstPerson] = true;8 n: M7 {4 s+ ]7 B( p& S# Z: q8 N
       while (!orderedMeetings.isEmpty()) {) I6 V, t- j% v% \
           // 按照时间顺序处理每一波会议
& E# b$ c) d) u4 d; M" Y9 C           var entry = orderedMeetings.pollFirstEntry();
  V/ d% k# G- M6 p4 L           var curMeetings = entry.getValue();
4 a, \3 h6 E' ?  D* t$ r           // 使用并查集维护当前时间点发生的所有会议中,有关联的人/ H9 `/ @% v" \
           UnionFind uf = new UnionFind(n);" r: J6 V( y* J! b( E" k  H. t  Q
           for (var m : curMeetings) {7 ^( ]# o, n3 l5 B3 P! y5 B9 A6 f3 y3 V
               uf.merge(m[0], m[1]);* \8 B; E+ ?- ~4 d/ l) U$ ]1 T
          }3 g8 C. x/ W4 P* S7 u
           // 枚举所有会议
8 L" c" N1 U% {( v           // 若会议参加人 m[0] 或 m[1] 知晓秘密, f8 O$ H1 P8 ], r
           // 则把他们所在的根节点也标记为知晓秘密
& l( b1 m4 o$ V) K( i4 j# e; v           for (var m : curMeetings) {
" m; E+ S% ~6 M% }. ~( A, C               if (known[m[0]] || known[m[1]]) {  d; `1 Q: d1 r* |+ B) l: S
                   known[uf.find(m[0])] = true;
; [& k( g( `. q                   known[uf.find(m[1])] = true;, ~6 [+ b) ~# C7 A; i* d
              }8 h: T4 q. R3 W/ U: a  W
          }
4 {7 r7 @  u4 r7 y           // 枚举所有的参会人,若他们所在的根节点知晓秘密,则把他们也标记为知晓秘密3 S$ U4 J2 |) v; d9 e" d
           for (var m : curMeetings) {
' f4 h5 p. e4 t. ]3 a  c/ @               if (known[uf.find(m[0])] || known[uf.find(m[1])]) {
0 a& m! Y) k; U  ^% D                   known[m[0]] = true;) e0 U& @2 K2 s
                   known[m[1]] = true;: w( t  [& L9 I1 i. T
              }4 x# G4 c5 p# E' d
          }/ D; ], C$ H# P
      }' W/ r' Y3 c( N2 c1 N+ D/ y6 _) ~
       List<Integer> res = new ArrayList<>();
+ V% }4 c9 \7 }& {$ I2 `9 l       for (int i = 0; i < n; i++) {
/ }5 q$ |: L2 G           if (known[i]) {
( V4 e7 }* ^$ x* |  T! Y               res.add(i);: J! s$ G1 h5 y3 [1 J
          }) X8 a: Y) _! t3 T
      }
$ Z2 i7 Y6 j4 L3 q& K) y       return res;
- {8 d; Q6 u. x. }6 o% Y. e  }9 Z5 r$ ]# a4 ]6 U& C
}
( j5 R$ z4 c( j6 h3 b/ ~5 W! C: e) l4 f% T
class UnionFind {
/ b. W0 e. I6 J! [7 J: t% c   public UnionFind(int size) {4 B) \2 Y( v6 v$ e9 r+ j* a' G/ l
       f = new int[size];8 f7 c8 P( V; i* V* G& T
       Arrays.fill(f, -1);
) o' {; j6 C) t3 S  }* e4 V9 w; \7 t# @
% _/ ?$ X0 [) G2 q0 e7 Q2 v. x4 g
   public int find(int x) {* C) g) t, K4 Q& ~# A$ i6 h
       if (f[x] < 0)
( \: d0 C4 A1 |3 N2 u2 `2 n/ P) A           return x;( Z8 g7 w" [1 e; T% L2 [
       return f[x] = find(f[x]);* ~  k, L( a/ q8 {2 Y. ^
  }. H$ C2 K0 A0 D! y, x
; z( Z3 l& g' A4 S6 `8 `. J. E' F
   public boolean merge(int a, int b) {
, t' Q/ B9 q  s$ u       int fa = find(a);. p, C. w$ h+ S" u' z
       int fb = find(b);( ~8 g" S0 P6 u
       if (fa == fb)! j- Q4 J& A( u2 r- Q+ ?$ E; e
           return false;
; n7 C" o& |2 ~0 _6 S( y       f[fa] = fb;9 B! r0 y2 b. w. j
       return true;
3 F  I. j8 |. w. }& r  U+ O  }
! \) p( L$ o9 V* W* n/ T3 v# b
+ {5 A2 d+ R5 h+ m6 P0 x   public Map<Integer, List<Integer>> sets() {
& t3 K# f: ]- ]0 r       Map<Integer, List<Integer>> res = new HashMap<>();
  A5 `6 U# h& ?       for (int i = 0; i < f.length; i++) {! E! j4 [2 Z! _, A
           int fi = find(i);
5 e$ U2 r3 w- b! A% Y6 J% v           if (!res.containsKey(fi)) {
# h! X2 I, _2 V5 z" `. S               res.put(fi, new ArrayList<>());# B8 V8 x% I2 i# b6 c8 [" Q& T
          }" n3 W9 {9 F% b  G3 I3 _+ G) N
           res.get(fi).add(i);" E! m! k/ H$ D+ g1 _7 L& f; Q
      }
1 `/ n: u1 ?. k1 i3 v) ^       return res;
4 s& w& ]% u7 y  }
( c. h7 ]* R# A2 M$ H. {
% x% `) U; D" p6 O. D   private int[] f;  O# w- f* K+ ?" \4 h/ j. g! A
}& f" q( O" x, f# K% v
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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