登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 找出数组中的所有 K 近邻下标】
' a, j& E$ R- o6 u$ o6 S* p, ~9 g0 w; p7 O [, `
解题思路: ?2 X) s, O( I p
遍历 nums 找到所有 key 的下标,然后将其左右 k 范围内的下标加到答案数组中即可。) ~% j* o3 a8 k. W
8 ^8 [% q; m8 s: @
代码展示
% e! [8 v' R4 C* Q. T; `
3 s' @% \# |4 [, Rclass Solution {- Z6 {0 ]0 M! z
public List<Integer> findKDistantIndices(int[] nums, int key, int k) {4 S( `2 q$ `. g8 b( X4 U) f4 V% ^7 q" z
List<Integer> res = new ArrayList<>();- ~; i* j: E, R& u3 x; f4 C
int last = -1;3 x l2 O2 [5 S0 I, ^6 R* l' b0 L
for (int i = 0; i < nums.length; i++) {: d. _$ w) i" k# e) g) s2 Z% ^
if (nums[i] == key) { \* `' u; {: Y, W/ z
for (int j = Math.max(last + 1, i - k); j <= i + k && j < nums.length; j++) {0 ?# @* l1 `) ^5 F* k$ J- ?
res.add(j);
7 ]3 Q. @, {) F; u+ {' r4 X/ q last = j;
" H& u4 S, | S6 r# y# S% f5 P }0 _8 I- p" m6 k* m# H9 u% n- n$ w
}
+ p$ U4 M x% d+ _ }3 I( o/ T. |* r* b% z. h: r3 H3 l
return res;
6 V# K0 Y4 p9 A7 f }! ~0 F7 `9 U- x
}
% Z3 s2 ~3 ^- f& T2 t f, ^4 [3 \1 s J2 {- {' Q3 X
. f0 [( Q3 q) H2 J( R【 NO.2 统计可以提取的工件】8 U% c# {7 T& n z% v0 t
+ Q& c. L! G- r1 m! }8 H! M9 `& G解题思路' ~ z9 B6 @/ U" ^5 Z# j. F1 \' Z
二维前缀和的典型应用场景。
0 @* i5 B8 d; R& z y7 R+ O
* H% E) i1 t6 D, s( ^! a7 [( b代码展示. _ }9 h0 s# Y' b5 ?' w: Y0 s
0 F3 s# h8 d: o
class Solution {+ f! U$ b' H) ?6 ^3 o, a/ i: W: x) a, Q
public int digArtifacts(int n, int[][] artifacts, int[][] dig) {
/ Q$ `% ?2 E' O( w, o9 L/ Z int[][] map = new int[n][n];
" H$ N2 s. G0 s! `2 k3 o for (var p : dig) {" _3 t% a% r+ C J% k5 c& J/ W% B1 f
map[p[0]][p[1]] = 1;
( l2 P! I8 l) {6 E V }
2 U4 j; r# [; z2 D% g0 a' L
+ L- |$ t& f% K. h' v" ^ // preSum[i][j] = (0, 0) ~ (i-1, j-1) square
9 K* _8 d5 c8 H0 x7 o( J( S% G& Y int[][] preSum = new int[n + 1][n + 1];
! j2 ? R2 E: J/ | for (int i = 1; i <= n; i++) {1 X% m$ h0 h0 ^8 a a
for (int j = 1; j <= n; j++) {
; M/ `3 ]5 u7 I preSum[i][j] = map[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];. B" h$ a8 Z7 q4 l+ a4 N0 G. X
}7 z) m3 a' B/ w
}
) a! b4 Z( z0 j3 c9 M( e% X7 M( L% S4 `; ?4 h5 V
int res = 0;
2 ~. ]7 I" B8 e for (var p : artifacts) {
+ q0 v" m2 o! z' c 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]];
: } r; S$ d: i% D& Y int real = (p[3] - p[1] + 1) * (p[2] - p[0] + 1);( f' t! ~/ E# g9 J$ d% p7 G. v6 T3 w
if (sum == real) {
( w C8 C- y; ~; m& y9 g res++;; t5 q$ W( c7 ^0 p( V, S% \7 z
}. E- q* \$ o& y1 P, y& ~
}
1 A- g- W4 h% s2 f
1 E7 \' }; [, \# S: T- x" G5 o return res;- m# a" f5 k! i f
}
5 O$ x% w5 a; {}
4 J$ ^: ?+ R; f$ {# X; ]( F
- S q; _# m- s0 b9 A( A; o9 G+ E& E6 A0 h8 u
【 NO.3 K 次操作后最大化顶端元素】" V8 m, d; X- {' ]$ L* Q" w8 [
( t% n: h r7 T# x
解题思路; l. \. @" S8 K7 B( e6 L) G
枚举每个位置,判断这个位置经过 k 次操作后能否变成栈顶。详见注释。
- q. S, f7 Y* e& m m2 W9 e9 B' p
代码展示
, V, r+ R1 _0 [0 U* F/ M8 d+ p0 @ }7 `+ L1 u
class Solution {, S$ ^6 {' x1 z8 }3 R9 m1 i
public int maximumTop(int[] nums, int k) {
0 C; b" x" u# v6 c. O9 V9 f int res = -1;& w v% ]/ r6 w8 N
for (int i = 0; i < nums.length; i++) {( X- m, a0 l1 ^% G0 Q
if (verify(i, k, nums.length)) {
7 c1 |7 I" J- n res = Math.max(res, nums[i]);; l" s n# d X7 v
}
5 S) G/ d$ l; r4 I8 T }
# V% K% _5 m4 _$ O9 r return res;# i! Z( L" y3 O6 r/ K
}6 {' |$ \3 P$ |) |2 Y) a
1 [0 s: q- q" Z
// 判断 k 次操作后能否使得 idx 位置的元素变成栈顶. t* y2 N! R( s' ` z1 ^' J
private boolean verify(int idx, int k, int length) {
* Y; j7 ~2 N0 V. P; U* C! q if (k <= idx) {& i9 s& C/ r! \' k7 i7 q! b1 F
return k == idx; // k < idx 时说明一直弹出也无法使得 idx 达到栈顶;k == idx 时恰好达到栈顶。
3 S/ N9 {7 N. Z8 E* f }) b- \' s8 h3 B
if (length == 1) {
% O- o" ?; d; Y, {5 Z return k % 2 == 0; // 只有一个元素,此时只能弹出、放回、弹出、放回6 @: h5 v1 ~0 E {5 i
}
) u5 a! U" Y. [* q% e7 p return k != idx + 1; // 有多个元素,且 k > idx,此时只有在 k == idx + 1 的时候无法做到,因为这时相当于 k == 1 && idx == 0& Z, V4 S. D/ ]& c& e: F I
}
' ]/ T8 N$ V' Z0 ?1 n2 w2 f! V}
. K6 H i3 U, Y( ?! X: T
* N8 d. s$ d$ f# s2 j) }) g! [3 C1 x6 `3 Z ^$ I) ~! x* M
【 NO.4 得到要求路径的最小带权子图】
) b% L7 t1 B6 Z% \2 u) {' n4 E3 s
O6 W4 l5 i* n. K0 ?解题思路
- v& R* L& H0 L2 O( j* P求出 src1 到其他所有节点的最短路,然后枚举 src2 到 dest 的所有路径,每找到一条路径 X,枚举 src1 到这个路径上每一个点的最短路 Y, 此时 X 和 Y 的长度和就可以作为备选答案。
3 k& o( Y/ z, u% \4 B: G9 ~0 Y( @3 C C/ L& E" a. O% z
代码展示
9 P- [+ L; @% A0 a# F0 W& e
Q4 c, P8 a7 Z4 z0 | f$ C2 w _class Solution {
7 [# _5 e. U6 V! S7 w) u long res;
* H6 t( L& |0 H: h
5 d m5 U5 b: f9 f* o public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
6 j+ Y2 r# X* q1 y: Y' O Dijkstra dijkstra = new Dijkstra(n);) X2 ?; D5 F& S7 M
for (int[] edge : edges) {
+ h7 ~! i( P7 p4 W# r5 O dijkstra.addEdge(edge[0], edge[1], edge[2]);
+ ~& w2 }9 g% N; c2 r L. I }! B; [" W0 z Q$ N5 E3 J2 e! s
long[] src1MinPath = dijkstra.dijkstra(src1);. M# a0 `; G3 Q4 N
res = Long.MAX_VALUE;
! J$ B5 Y0 H( \; t8 Y Q/ s
+ R; v t# y0 J+ f* I/ Y. V9 ~ boolean[] vis = new boolean[n];3 _6 p2 \) L( e0 _
int[] path = new int[n];
3 A6 N9 H7 `0 H; x0 Z- X vis[src2] = true;
* ]- i9 M8 T; n) U( x( I, q path[0] = src2;- X8 l; J: }8 v. I8 I$ s/ T
dfs(src2, dest, dijkstra.graph, src1MinPath, vis, path, 1, 0);/ v F% Y% Y8 _$ R' J% O' P
return res == Long.MAX_VALUE ? -1 : res;# n" O" }7 H- M% H6 F/ o! ^5 y
}, n; p( d# K$ D! P4 o! E, A
3 x |- x+ N! n4 I, Z' |& H private void dfs(int cur, int dest, List<List<Dijkstra.Node>> graph, long[] src1MinPath, boolean[] vis, int[] path, int pathLen, long len) {9 L& r( [" F! K' O! F& _4 E
if (cur == dest) {" k' U8 @ F' R9 u) H1 ^
for (int i = 0; i < pathLen; i++) {
5 j2 _0 k, t2 y# J( J8 Z9 M9 F if (src1MinPath[path[i]] < Long.MAX_VALUE) {: ?* m+ y8 X& o; y- z6 l/ A p
res = Math.min(res, len + src1MinPath[path[i]]);1 R0 J6 l8 ]: I" h3 A: u
}
% g8 L- s8 x# y }. ~! l! _: v( s' U; V
return;7 b/ z5 y6 \) |
}* v' r& o$ F) c, G- s
for (var nxt : graph.get(cur)) {: k" Y( A2 M( {% c; W
if (vis[nxt.to]) {& J( b! F. u( e4 y
continue;
; x5 k3 Z9 t: P }
, z B% h4 _4 u" G% X vis[nxt.to] = true;+ b3 X! Y% Z7 N3 O- k: F1 c- {
path[pathLen] = nxt.to;" W7 ]- |5 R3 Y. I$ Y
dfs(nxt.to, dest, graph, src1MinPath, vis, path, pathLen + 1, len + nxt.len);
0 a3 u, G2 ~' Y& ^ vis[nxt.to] = false;
2 `3 g# ^: k0 n% j; |! ^+ d* E }
& @! r1 H7 u2 Z, F }. {7 R \( J5 j. I: n: W
}
1 `6 W% j: W4 W6 S1 [
, ~% I. C, D* V$ ^7 uclass Dijkstra {
4 O8 ~2 D- ^: O% _ static class Node {, |& v; c6 J9 O( A5 @% t
int to;
, m5 ]8 v. K! J* Q) N% | long len;
) P5 @7 f( U9 ], e6 P1 W+ L8 j" }( A5 O. L6 @" b" q8 a
Node(int to, long len) {4 C, @5 A! z+ l& Y$ A4 I* ^( U0 e
this.to = to;
1 l+ [" ~ e7 J this.len = len;& ?* y8 k7 {( f# ?) |1 B
}! I! ~3 Z4 C! E8 Y
}6 O5 W: w' g; s9 m5 T
! h: Q# v6 C$ t. j0 O0 F
List<List<Node>> graph;
$ y2 G9 t9 D1 i$ o+ X/ d6 n5 i& x0 r f# K0 r& r
public Dijkstra(int size) {
! D5 n: X* F( j graph = new ArrayList<>(size);
- @0 x* m# \( C* x1 Z1 B for (int i = 0; i < size; i++) {
5 y: ~# N6 u1 \, e$ G graph.add(new ArrayList<>());
4 @3 m+ P7 d& q6 Q3 h: p }# ^6 A* |, \; A$ R0 u$ C
}% N) |9 p4 x- W2 k2 o
+ Z! z0 K; c4 H: x3 p1 f
public void addEdge(int from, int to, long len) {9 P" q4 k- S2 }! |% Q7 C
graph.get(from).add(new Node(to, len));
0 D* g* a( f$ a* G: ~ }
( K5 D+ J0 j! I
1 p# j7 s- Y' y, l* Q! h# `8 [ public long[] dijkstra(int start) {
# C) P4 _$ S+ h0 T S long[] res = new long[graph.size()];2 o5 v I" u- g$ Q& a
Arrays.fill(res, Long.MAX_VALUE);+ Q e& h+ v2 w0 |3 X- Q
res[start] = 0;
+ p4 j4 x& Y* D8 ^ PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> (int) (o1.len - o2.len));0 H5 P4 S0 n% h/ f% c4 I
heap.add(new Node(start, 0));
* n" f8 l0 N: v8 E" G# S6 [ boolean[] visited = new boolean[graph.size()];
. {8 B C0 M1 E$ `2 s while (!heap.isEmpty()) {" a# |7 p8 a: _! t9 @
Node node = heap.poll();/ }' E; R9 K; p; j8 u% q
if (visited[node.to]) {
: g7 f% m" ~" Y% W7 D continue;
+ Y- b; m) e+ `, c4 Q }
& Y+ g' T* H4 s" c' O8 r- }7 I5 O visited[node.to] = true;
4 i/ {6 a( k/ b for (Node next : graph.get(node.to)) {
8 w3 l: v) M" O0 W: o$ | if (res[next.to] > node.len + next.len) {0 T) q7 [1 c1 S9 |* G' {. V9 V5 _
res[next.to] = node.len + next.len;$ Y% X7 y" W2 s) P
heap.add(new Node(next.to, node.len + next.len));( k S8 ~4 A( x) n$ s( d
}
7 m% [ P. f$ r/ ?9 K8 \ }
% \9 D7 M5 @. h% L9 I }
( \/ u0 Y3 q- Y4 [+ ` return res;
- s) W0 }3 E1 }# M% T W }5 N1 V2 x: G" m, d& s
} |