登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
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
|