登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 找出数组中的所有 K 近邻下标】5 A% F( Z7 w" J2 O
' H$ Y( u# Y( t) }
解题思路, W B: N( E' W; f/ P
遍历 nums 找到所有 key 的下标,然后将其左右 k 范围内的下标加到答案数组中即可。% |; P$ b N3 O# z9 G
7 [7 s1 Q! |6 `
代码展示
) i: m) Q# ~9 |) k+ b9 [7 Y+ c8 N; K& _, o/ g5 u
class Solution {
O; b/ R; r8 d& l8 \ public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
$ k3 {% @( V( q, t* ]4 |; X List<Integer> res = new ArrayList<>();
7 O5 H9 Y# M( Z* D* D int last = -1;- J1 i) u: e" X' B
for (int i = 0; i < nums.length; i++) {0 p* Q6 X1 J& O4 V& s. N
if (nums[i] == key) {+ J! A. S( c; n0 c* Y3 q
for (int j = Math.max(last + 1, i - k); j <= i + k && j < nums.length; j++) {. o+ A. u" W" ^) b+ {/ o& r
res.add(j);
! F# M6 b7 {8 m _9 p# n3 i; Q last = j;6 T' S) q2 {. H2 E9 j, B
}
7 M* v* Y6 x/ @+ M* X Q' S z2 b }
; s+ t: k6 J a6 V }" {/ I# i( N6 f. p5 h* Y
return res;0 s: N2 Y+ j/ A8 z3 P8 Z
}" U( Q7 c( N& J, a* q
}
0 h% z" [5 W5 C( O: T0 f. Q3 ^# L, G" u( L( y
0 k+ x. ^! n1 }9 E% V4 \
【 NO.2 统计可以提取的工件】
0 d% b7 I6 ]! h6 Q6 k! k! N
' I5 Z; b) ~8 ^( {9 d! [解题思路7 r2 W6 A7 h3 v* V( U8 T
二维前缀和的典型应用场景。
1 b/ e! |1 O; a( _: {; q* \
2 q' O# y" W4 k6 I8 a. l" `2 ~代码展示0 d0 A& v1 j& `( C( C" L/ Y
6 d) w1 E% I5 } F3 p
class Solution {2 S& V; s& P. m# M4 _3 |5 o
public int digArtifacts(int n, int[][] artifacts, int[][] dig) {
& A+ C6 h- i, y2 ]. H( g d- m; x int[][] map = new int[n][n];$ Y1 y' x0 h# r- k0 V) e# M g7 h2 \
for (var p : dig) {
3 S* N9 W' T! \2 y6 }+ ^7 Y( @ map[p[0]][p[1]] = 1;. W# ~. ~% G5 C; x
}
5 U4 p% t$ K- m! v& k1 _1 c, t
, ]& w2 {; x! q- L0 X // preSum[i][j] = (0, 0) ~ (i-1, j-1) square3 y) o% U5 X3 _% K, ~. }) r6 x
int[][] preSum = new int[n + 1][n + 1];
7 \3 H# q0 g" ?, i) n2 N6 T& t for (int i = 1; i <= n; i++) {
" f0 t' `+ t1 I, [1 { for (int j = 1; j <= n; j++) {- W2 |. Z# u/ `2 q. D$ t
preSum[i][j] = map[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
9 o, U' Y4 p# v3 v3 ^1 s! R5 N }% Q f, R* H4 t# {
}* H0 [# t/ c3 X r- q' {. V7 @
2 g4 ?1 [* t) S8 q2 l
int res = 0;9 L) |* v, b( w. S3 f* p# A# {
for (var p : artifacts) {
7 S) k3 k3 C, {4 V e2 j int sum = preSum[p[2] + 1][p[3] + 1] - preSum[p[2] + 1][p[1]] - preSum[p[0]][p[3] + 1] + preSum[p[0]][p[1]];' z( x& d5 e+ e
int real = (p[3] - p[1] + 1) * (p[2] - p[0] + 1);% B4 l# ^1 o9 `3 y' y
if (sum == real) {
6 Q- O$ G" E3 @: z8 D$ p1 |9 q res++;0 J! v* g' q& s/ i
}4 V$ Y9 D; Z+ ]0 F2 I3 a8 V
}
! \' F/ l9 m1 c. o" j: Y- `6 g9 R' f' w J5 k6 q1 |% m
return res;
7 b W0 P9 k8 F" f }' E% j; [8 z M+ l; ^9 S
}9 n% |$ ], [! a* P$ O
+ K& I c/ S6 f! Y
& O" X$ F! B$ }5 o
【 NO.3 K 次操作后最大化顶端元素】
" e' m3 g2 T' }% }* k
0 h" V. [2 v K解题思路
. W- ~0 K5 U6 [7 }0 N$ y: u枚举每个位置,判断这个位置经过 k 次操作后能否变成栈顶。详见注释。
9 @! w5 ~' ^- K4 _9 E, l# q
6 q0 q4 t1 M# o$ ]6 q6 V. ]代码展示0 d1 t+ O: p: _; ?
% T. ~# `! E2 y5 r5 A. ?class Solution {4 R4 M: F$ s% w+ x* l' ], {
public int maximumTop(int[] nums, int k) {' `+ ~+ Z; T# k1 d: h
int res = -1;6 z2 G9 A3 M3 J6 t5 n% ?& p2 Z
for (int i = 0; i < nums.length; i++) {
* e" `# |; F* X8 u if (verify(i, k, nums.length)) {" x2 s* v! _1 @0 ~# W# X1 c( ]2 h
res = Math.max(res, nums[i]);, n! ~# I ]2 S: R! q! p% |
}) m: Z& |5 m2 v
}
" u' S" t# y7 ?7 w$ u) B return res;' B9 d! S! W1 e9 r3 @0 [
}
D g' m5 f* t* _4 N8 `) `8 A" V+ |# g# z& q& ~! ]' E2 v
// 判断 k 次操作后能否使得 idx 位置的元素变成栈顶
5 \; g! ~, M% C1 e( h7 L private boolean verify(int idx, int k, int length) {& w: Q: B4 Q# o T- m
if (k <= idx) {' H, J5 u; O8 B* K g
return k == idx; // k < idx 时说明一直弹出也无法使得 idx 达到栈顶;k == idx 时恰好达到栈顶。
9 O) Y) ~1 u% g* G( h: w6 q }
- F( U$ q, ~' F# ]0 r1 R6 h if (length == 1) {
$ b: B2 I/ W2 q9 b6 _ return k % 2 == 0; // 只有一个元素,此时只能弹出、放回、弹出、放回3 e" L5 w' n9 k, d5 o$ d
}
9 C- c/ d; _$ a% B& ] return k != idx + 1; // 有多个元素,且 k > idx,此时只有在 k == idx + 1 的时候无法做到,因为这时相当于 k == 1 && idx == 08 C% j- U; U: C3 q4 C) ]" z! Z- [8 b
}
Z" U) O5 T4 c) O}
9 X7 u) B4 p1 s% b7 V* A% |7 C* z n5 T% M9 i0 M* X
2 I+ f% y) J4 t( O: I. C# [9 P
【 NO.4 得到要求路径的最小带权子图】/ R3 q. e$ \" v, y; c# x# z
7 t' H! g/ b# L3 l j" @
解题思路/ ]) e0 E4 l: X; f
求出 src1 到其他所有节点的最短路,然后枚举 src2 到 dest 的所有路径,每找到一条路径 X,枚举 src1 到这个路径上每一个点的最短路 Y, 此时 X 和 Y 的长度和就可以作为备选答案。$ ]3 f$ c$ m' D- \2 Q3 _
& q" l! l4 j% k0 V
代码展示8 k1 G5 w4 ^) e* `8 z; v1 g# s# \' x
& y e. h0 ?3 d& z2 g/ rclass Solution {! ~9 w1 t+ b5 I' l: i
long res;
9 X1 `: v. @# E8 g3 k; n, o7 L$ O
& V) l9 Z4 o7 w* K' m: c* O public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {" f5 w) v+ m. N, [) [( E
Dijkstra dijkstra = new Dijkstra(n);' P7 j6 m6 G/ r0 J
for (int[] edge : edges) {0 F/ u! i0 t; v' h
dijkstra.addEdge(edge[0], edge[1], edge[2]);
/ J! J+ M4 r1 ?% {( h }; Y0 D0 ]' ^5 Y
long[] src1MinPath = dijkstra.dijkstra(src1);
+ X3 V! n! {# |& L res = Long.MAX_VALUE;- j. U3 w6 Y4 _0 c) q, I
- I6 \* D2 y4 G( r+ E$ G2 P
boolean[] vis = new boolean[n];
, i4 A+ `& I9 K: M6 l. j int[] path = new int[n];1 b7 c; W% `+ r. X# ]6 \
vis[src2] = true;
I& f% z' s+ U( b path[0] = src2;
5 C4 V% K+ s" X$ @7 [ dfs(src2, dest, dijkstra.graph, src1MinPath, vis, path, 1, 0);& U" C" P8 O i% ?( T9 ?( s6 @
return res == Long.MAX_VALUE ? -1 : res;
' w8 i3 B. T) M, i1 W0 n( K; d7 O }
/ T0 c" _+ A( Z. N |, d% ^7 {
" \3 o2 B# g f9 K0 w( Z: _ private void dfs(int cur, int dest, List<List<Dijkstra.Node>> graph, long[] src1MinPath, boolean[] vis, int[] path, int pathLen, long len) {
: j+ ?6 _, J0 U: P! q: e if (cur == dest) {
+ M# m0 s7 V8 r- H6 j0 f2 q, u/ g for (int i = 0; i < pathLen; i++) {* T6 M- b) R; E' ]% m) l! n. N
if (src1MinPath[path[i]] < Long.MAX_VALUE) {* |8 F: c' z! E, O% \
res = Math.min(res, len + src1MinPath[path[i]]);, ^" |+ `; L! U% u: C$ K
}8 G- Z0 w# {- G9 e. j0 J& O8 ^
}
8 d8 O7 i& e: V; o4 L& j return;
, _7 ?9 D/ j; Q ]. V }
" |' z1 F: a: U for (var nxt : graph.get(cur)) {
; ?! @* o: C% j* Y* \ if (vis[nxt.to]) {
8 H8 \; g s* W' L$ \, ]/ V continue;
6 y; s. n3 ]% A }
1 j, T5 f+ P. l; L2 ?9 h vis[nxt.to] = true;
* k' |8 V8 K" H+ o$ e$ R+ a+ @2 a" { path[pathLen] = nxt.to;* t' s2 T, u; G5 u
dfs(nxt.to, dest, graph, src1MinPath, vis, path, pathLen + 1, len + nxt.len);6 L0 ^0 x4 k3 G5 q k% u1 k
vis[nxt.to] = false;3 o/ X7 F5 f0 B; ], z- r; @
}
3 w2 i- n) n% V/ D, n0 s+ h" g }
4 U+ M$ f0 B3 g) n" n5 L0 J}
7 i3 @1 a6 ]$ Z- @/ m8 g2 l. i8 e" J; K/ U: u3 D( K& K
class Dijkstra {2 n- x6 P+ y3 a- [+ t/ | I
static class Node {. n3 Q3 t) j- d! ?3 f% W: L1 p
int to;' I: J0 g: y1 Y) c4 S. ~' W: X
long len;
$ O* o/ S8 S S7 l3 ^1 P% s2 m6 A. B. V; D5 h
Node(int to, long len) {: C6 Q4 o% W9 S
this.to = to;5 `* [$ K1 h$ i: G
this.len = len;6 }" b+ U, g/ Y; U, q
}
3 p9 R! Q5 Y4 O2 k9 Y! ~! I }
- a; z# T% m% b% ~7 l! ^8 u9 b8 g
% r, t' C& r; g# J* I; i List<List<Node>> graph;
6 x2 `3 z1 H$ w8 X# o1 [ f+ ~; p
7 B* H7 j" t r2 C7 I public Dijkstra(int size) {; i+ p, f3 Y- v3 L @$ k6 w4 O
graph = new ArrayList<>(size);
4 }. n) c* q- C" ]% V' C! t/ v# T for (int i = 0; i < size; i++) {
0 Y. W+ H# K- v7 x$ ]! l graph.add(new ArrayList<>());; B' u5 K1 ?! u
}
/ c3 C4 [% L( a; c, W }
, G4 T) r9 g( ~. @/ a4 [
- ?; v4 j- J+ K& i; ~1 M; n public void addEdge(int from, int to, long len) {/ A3 P9 f" y8 n% R
graph.get(from).add(new Node(to, len));
0 w8 H- j3 u# A }
) j; K2 c/ F! a2 S3 v" |
: x1 {; N% {' M0 n4 X public long[] dijkstra(int start) {8 Z# L7 k1 }3 ?2 L* E4 G0 }% G
long[] res = new long[graph.size()];- L( s& {! ?6 F- R; I, L* Y
Arrays.fill(res, Long.MAX_VALUE); S* k, y9 v6 j6 u0 V: w' W, Y
res[start] = 0;; U( X7 v" _% R; q; D
PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> (int) (o1.len - o2.len));# R8 A; q( | b& ~7 I0 b
heap.add(new Node(start, 0));% X5 X. p! K6 G; o* ] d3 K* | M
boolean[] visited = new boolean[graph.size()];
4 s7 ]$ a! Z2 e, E: @6 W; n while (!heap.isEmpty()) {
/ H% E: j8 r w/ N7 | Node node = heap.poll();
+ u3 G- z$ M) ]2 l- x& [8 M: k( l if (visited[node.to]) {/ v7 m) ?- n* p) `: b
continue;) F$ p- ?6 e: N$ r8 Z
}8 ?% T' w) L( k
visited[node.to] = true;
$ a B8 H6 K a X- | for (Node next : graph.get(node.to)) {$ b; _) v8 W) g
if (res[next.to] > node.len + next.len) {
1 P4 Q- ], R" f' o. ?5 ]- J res[next.to] = node.len + next.len;" `( z, A1 }+ g" @( t/ m
heap.add(new Node(next.to, node.len + next.len));) J4 n# \+ a m. N2 i
}
# P. y$ n4 e5 `, n+ o) G3 w }- C! g7 C/ D' F7 Q! O
}
: ~( ]: e9 ?, F# ] return res;, O$ x% s/ s, f3 Y
}
8 I2 E5 X& p3 l! U. d9 X6 }; l} |