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

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

上岸算法 回复:0 | 查看:1470 | 发表于 2022-3-14 16:43:15 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 找出数组中的所有 K 近邻下标】; Q% I" k  J9 I5 s7 Z8 J& {

$ h0 n3 ~9 ?5 ?) m解题思路
( b- O6 n( X6 J8 c! L! k: j遍历 nums 找到所有 key 的下标,然后将其左右 k 范围内的下标加到答案数组中即可。
# n/ x$ d0 W) a/ L
. X; P; ^1 [& |5 E% c代码展示% P/ M- e! O- N4 `
0 t5 q9 L; w+ z' k; ~5 w  A" A2 o
class Solution {
# R3 f# i4 \1 h" u2 z   public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
0 r" h/ Z2 ~& O# o) s% I. {       List<Integer> res = new ArrayList<>();( P2 j! Z2 i4 G. N
       int last = -1;, M/ M$ x  f- s% V7 B. I2 {
       for (int i = 0; i < nums.length; i++) {
. T( l& R- R  C. D7 a5 a           if (nums[i] == key) {# r0 a& }# i3 T+ L
               for (int j = Math.max(last + 1, i - k); j <= i + k && j < nums.length; j++) {
2 o8 W, k/ M$ w: E                   res.add(j);' S$ i; g# b* o" F
                   last = j;
2 j! i$ m% V  W& [& }              }9 z1 a7 E/ K* ]: f8 }& {, t) i3 k. t
          }" R4 e- Y3 |0 T
      }
( s0 X3 O7 s) F6 {5 g  c2 o       return res;
: L0 o8 e2 j3 c4 s- \5 U! r  }
3 C3 o. c' L5 i6 j}! r/ t! A9 Z/ ]0 R

# `) M) y; J9 `% j: {. L
. }6 R7 u, E. F5 k+ V' t* \【 NO.2 统计可以提取的工件】: E3 g: g: P* x

6 ]2 V- A1 T' c3 ]解题思路( I7 R8 O2 B0 k( f3 i
二维前缀和的典型应用场景。
# W8 N" [/ a$ r6 r6 k* Q8 I! S8 y. y1 ]& g+ a
代码展示7 t9 M3 X) v3 G
9 `7 l/ q( n' H
class Solution {
$ R/ Y  J" ~0 g! ~6 f  O7 M   public int digArtifacts(int n, int[][] artifacts, int[][] dig) {
) I3 d6 W/ S9 b0 `# b6 I; {. B. s       int[][] map = new int[n][n];" v  i7 z+ @/ c4 z3 P
       for (var p : dig) {
2 T% q- i; _8 I( k" [           map[p[0]][p[1]] = 1;
" o7 m# _$ I0 O" L( U1 B      }
+ _$ V9 w5 Q# F" B% _& e
& J) d" j, J4 H! L4 z: @( O       // preSum[i][j] = (0, 0) ~ (i-1, j-1) square
7 Q3 F  E( Z2 A3 |: c* n' d3 Y8 w       int[][] preSum = new int[n + 1][n + 1];  j6 O8 t# ]) \( c1 \
       for (int i = 1; i <= n; i++) {2 b4 @4 D) V) q! @" I/ _
           for (int j = 1; j <= n; j++) {/ q  s9 S3 a8 [+ \, T0 C9 w
               preSum[i][j] = map[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
% [' j; V  c5 w9 B9 Y          }
; s) X8 p" @8 K$ e      }$ y1 O. H' g8 A$ B

6 J: N$ ]9 ]/ j! l0 p9 o; H       int res = 0;
' i' W3 o# A8 j+ z' r! ]       for (var p : artifacts) {% Q1 N& l# c; j" H5 V8 _
           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]];
* n7 @; z" \  B           int real = (p[3] - p[1] + 1) * (p[2] - p[0] + 1);9 j- @* }* z* j5 n& ]
           if (sum == real) {
8 [3 L$ a/ ?& Z/ D               res++;
" ~3 p# I% Z/ s2 y          }# {& s  Q1 c* I
      }
9 [+ ?9 Q! p, v3 e+ z- C! B; C. Z# j' \
       return res;4 T$ f! ?8 @: J' _  E2 z( j
  }
/ P* C5 E: S: D* e}
  T! t( ?; }& u1 C: T  U( o/ h2 @- I0 f5 S( J9 S! I
9 s7 t7 {1 U8 q* \
【 NO.3 K 次操作后最大化顶端元素】% C3 z- Q! \6 K  n* s7 m

$ `! e7 E7 |1 N+ }  w; H解题思路7 E2 d' k& v3 d/ A
枚举每个位置,判断这个位置经过 k 次操作后能否变成栈顶。详见注释。) X* v1 z- @5 ]  `5 h
- Y, ^4 a) \7 N
代码展示
% Q6 v7 h3 {/ `) s7 a( M, N0 A3 _. B: B. R& V6 j5 c; j; s+ r7 D/ x' e" l
class Solution {
3 \) B2 J; R. F. q3 J   public int maximumTop(int[] nums, int k) {
2 }: H/ O4 J* Z, T' L9 V       int res = -1;" v* O" k* e* y' t+ }9 S- j' q
       for (int i = 0; i < nums.length; i++) {3 C+ @& b* a  d3 L' _  m% b" m
           if (verify(i, k, nums.length)) {' l* I( K+ N+ @
               res = Math.max(res, nums[i]);. s9 V: m3 l' j$ v# f
          }
6 ]0 B% r7 `4 ^& \- e( Z      }
  u/ }  b; U  Q5 G, s. O       return res;9 P0 r! W7 [1 P' m- ]+ y& G$ i
  }' I. F1 b/ b$ _& v
3 Q+ W1 a! w, L/ F# ~/ I+ ^2 y+ B
   // 判断 k 次操作后能否使得 idx 位置的元素变成栈顶
8 B& b2 @7 F/ C) p4 y   private boolean verify(int idx, int k, int length) {
9 F  D* ]1 u, V       if (k <= idx) {
7 r  ^% N6 J, F1 i3 O8 c           return k == idx; // k < idx 时说明一直弹出也无法使得 idx 达到栈顶;k == idx 时恰好达到栈顶。
( ?$ n8 U1 e  m! a      }
% b# I  X- r' g       if (length == 1) {
: r2 C, [5 Q9 E2 O- C: z$ |           return k % 2 == 0; // 只有一个元素,此时只能弹出、放回、弹出、放回; Q* K7 Z& u+ l2 ]* G  V
      }
' _0 v9 y) T$ ?* M5 K1 n       return k != idx + 1; // 有多个元素,且 k > idx,此时只有在 k == idx + 1 的时候无法做到,因为这时相当于 k == 1 && idx == 0
. C# Y8 ^" W% r) q& ]( p8 q' @  }
5 M0 c% X% I) Z: N. |, }& E}
; s' l0 O$ B1 N( V$ E3 @3 R! F8 E# G# q. B4 i  R9 R7 n; n

$ `. i7 N" R0 Q0 r+ U# E/ d  L  i- [【 NO.4 得到要求路径的最小带权子图】& h+ [) {- u# R0 C% p2 l4 n# ~

% o! z5 {4 O* }$ r) L) t解题思路% T$ t4 i0 M+ |
求出 src1 到其他所有节点的最短路,然后枚举 src2 到 dest 的所有路径,每找到一条路径 X,枚举 src1 到这个路径上每一个点的最短路 Y, 此时 X 和 Y 的长度和就可以作为备选答案。( b' N9 U5 ]! g: N( k7 M8 c5 ^; C+ `

$ {1 F6 s# o  x7 v代码展示
" F' }# D. ~, ?5 E* e1 z. P+ Z. j* e, a7 P% G* _# ~- E
class Solution {4 P: R! U8 S; j' j4 V2 j2 Q
   long res;
7 d$ L6 H  q6 _  y" Z$ a  `( Z/ g! G( s/ u
   public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
6 a+ _4 t/ R# P; ^4 }       Dijkstra dijkstra = new Dijkstra(n);
, `; j+ h$ ], y- A" [       for (int[] edge : edges) {
1 w: e  h& E! t9 l7 R% F           dijkstra.addEdge(edge[0], edge[1], edge[2]);
& a/ g- D+ v# S# c      }4 {" _$ \) m$ @  `3 t
       long[] src1MinPath = dijkstra.dijkstra(src1);
" r9 c6 s* H- w       res = Long.MAX_VALUE;) B( b6 t) ?7 R# w, n
! Y& o; d  z  y
       boolean[] vis = new boolean[n];
& w; W  Q5 @% L2 D: f# V& V       int[] path = new int[n];
. R+ _8 _1 G" B$ P       vis[src2] = true;
8 }( o9 P5 f! v, o; C# [1 Q       path[0] = src2;
+ P8 m) f) @' S* I# a       dfs(src2, dest, dijkstra.graph, src1MinPath, vis, path, 1, 0);
9 A2 j$ K6 H# I: Z5 R8 u       return res == Long.MAX_VALUE ? -1 : res;8 w, S( i: Z  ]5 D' C7 `; V( x- ^
  }
  s0 w5 k: S: M; s7 D* m' \9 X+ S. _( x; `+ V3 p' y
   private void dfs(int cur, int dest, List<List<Dijkstra.Node>> graph, long[] src1MinPath, boolean[] vis, int[] path, int pathLen, long len) {2 y- [/ s- s, G7 Q  W7 V0 D, D, H1 ]
       if (cur == dest) {
" b. {4 D  p3 U' P9 [+ K" r" g           for (int i = 0; i < pathLen; i++) {, V9 v* G; [, m
               if (src1MinPath[path[i]] < Long.MAX_VALUE) {& Q# K0 O: z3 T9 l
                   res = Math.min(res, len + src1MinPath[path[i]]);/ |% S4 }! V) @& [% A; J+ p/ {, T; O
              }
$ b1 V7 Q( ^* D          }5 ]$ t- j" S1 P) e# l8 `
           return;
7 J6 C6 o( Y8 Z      }
: z# O+ h5 B: s. ~8 A3 |0 v) v8 H       for (var nxt : graph.get(cur)) {
) u8 h9 M$ x( F( r) X3 R2 Z! ^           if (vis[nxt.to]) {' j6 T7 I1 O9 C% f% a4 j
               continue;/ j3 H0 r- X* ^% s9 W
          }+ [! ^8 K& ?  A* S. }4 T
           vis[nxt.to] = true;
- l3 h! j" e2 C9 s5 E% `& }+ ~           path[pathLen] = nxt.to;0 y& w; ~5 G7 ?$ W, c
           dfs(nxt.to, dest, graph, src1MinPath, vis, path, pathLen + 1, len + nxt.len);6 G6 I0 q) N) L) _( v! F( \
           vis[nxt.to] = false;' c: T( m! q2 j2 Y' Z
      }
2 Y8 R  P7 H" v- ?  }
& R7 X9 D* r3 G/ ?}: y0 _! A9 ]+ F% g5 g
3 b& U1 f9 \/ X" w9 d7 H. c, K
class Dijkstra {
3 H/ K  K& B5 S' p# Y0 N9 H* B& H$ D3 V   static class Node {5 U! J* h# P- t- Q. s8 N" ]& L
       int to;
; `# H. S1 u% b8 a# G       long len;; y& @8 j. G" O; ^: L/ X" s2 Z
8 @% A0 O5 L0 Q) h  T' D
       Node(int to, long len) {
1 J4 x# t/ h0 ~  Q9 K           this.to = to;  ?' i# I5 d7 |( b2 W
           this.len = len;
, `4 j! |  V  i$ ^; O  J& X+ e      }6 D2 s- {( w- \# J
  }7 U- ]; ~# d' j8 I% P
- G4 ?& h1 O1 s4 m/ P( B+ }
   List<List<Node>> graph;
) U( t5 N( ~1 v& H& q1 f2 ]6 k3 t' o2 M6 z8 \4 I- j
   public Dijkstra(int size) {
% l/ s+ Y3 G2 \' K8 t       graph = new ArrayList<>(size);
/ p  T' l- |2 w       for (int i = 0; i < size; i++) {
  `$ d1 T) i7 u$ S           graph.add(new ArrayList<>());: r$ C) v8 c$ \/ V
      }
: [  ]) i% A. [: z: w  }# r% D/ o) j( p: R! f7 v$ r( Z6 @
6 h2 K: U; W5 N& r% X( Z
   public void addEdge(int from, int to, long len) {
# o6 w5 |9 Q7 F7 t0 L  ]# c       graph.get(from).add(new Node(to, len));
9 A, F( g2 s- c" u) |  }3 ~1 a$ F$ F$ f* I/ T+ @- Y
0 G/ P# ]9 S% t1 g
   public long[] dijkstra(int start) {
6 C4 u% f4 T. @% k' w- u! ]5 J4 U* h       long[] res = new long[graph.size()];3 e. {0 ]( t8 X) {! T
       Arrays.fill(res, Long.MAX_VALUE);
; O$ C/ h! r. u+ J" B6 r& d# \) w* o- u       res[start] = 0;
0 B7 E8 I/ Y4 ]. N) ~& q       PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> (int) (o1.len - o2.len));
; `% K) q1 k& {7 H       heap.add(new Node(start, 0));
( Y: i4 N3 `6 K# U       boolean[] visited = new boolean[graph.size()];4 }. i: H: k; i& Z$ E  q
       while (!heap.isEmpty()) {2 O9 J' n/ V! ?  h3 c
           Node node = heap.poll();& d! R7 k1 ^* r, R, w, Z
           if (visited[node.to]) {
" r$ u; |# L7 Z. k; ]9 H               continue;: I  M# f  T# x4 X$ f5 X! J6 m
          }) o0 J, u+ i6 v( P. b# [1 C
           visited[node.to] = true;
, h4 O) O4 l$ P8 A2 a           for (Node next : graph.get(node.to)) {0 |! R' F4 ]1 q+ Y
               if (res[next.to] > node.len + next.len) {
& b, X7 ?5 Q% R% A                   res[next.to] = node.len + next.len;
: e/ {, o0 c+ p) e/ u- W                   heap.add(new Node(next.to, node.len + next.len));
3 ^- y3 u( b/ d9 n              }
2 _6 C& z9 J0 b2 }5 p" M          }% v/ G4 a9 p9 g# ]' G7 ]! g  E
      }
/ h. j* t2 j& f( A# j8 l       return res;. s0 b' [0 c0 _. I2 E. e
  }
. }* \* g. H9 k% p& p( N}
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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