上岸算法 I LeetCode Weekly Contest 231解题报告

No.1 检查二进制字符串字段
; [' J4 `4 s6 }% B3 ^7 J3 I5 c
  V* Q7 I$ \: u% u! \解题思路

符合要求的字符串即前缀全是 1，后缀全是 0 的字符串。
2 Z5 ]1 L- E% B" O& x0 T
代码展示
0 {7 _+ J/ n1 m+ e+ r( m1 S
( n. [1 @% L0 Z

1. class Solution {
     x; B9 q( M' T- [! M
2.     public boolean checkOnesSegment(String s) {
   1 L& R  v9 T$ p) Q5 {6 |
3.         if (!s.contains("0")) {
   
4.             return true;
   
5.         }
   
6.         if (s.substring(s.indexOf("0")).contains("1")) {
   4 d5 L; |* ?/ V* {9 c
7.             return false;
   # V" ?3 m5 t1 K  r% J7 P
8.         }
   
9.         return true;
   0 L- L. g( B  |( i+ S
10.     }
    ( J4 |# m( H2 }
11. }

复制代码

9 |* ~  o+ p6 K8 L3 i- iNo.2 构成特定和需要添加的最少元素
5 C; x+ u/ D! J0 D
5 g) p: I* u+ y1 _解题思路
$ I& P& w8 C/ F2 _4 Z; |
! u0 j3 V. P/ `9 \2 o+ K0 C贪心即可，每次都添加绝对值尽可能大的。注意总和可能溢出 int，所以中间运算要使用 long。

7 f+ }5 x( w1 [4 P6 K代码展示
1 `# i0 D2 z% _% r/ o; l- z
8 ?3 \' p2 N# M' P% N

1. class Solution {
   
2.     public int minElements(int[] nums, int limit, int goal) {
   
3.         long sum = 0;
   
4.         for (int num : nums) {
   
5.             sum += num;
   1 W* V& {, X8 N" f) \, g
6.         }
   1 T! n' q( E0 \! B* x% X2 s$ E7 Y5 T
7.         sum = Math.abs(goal - sum);
   5 C5 G. f$ ?0 e- n' o; K  s. W
8.         int count = (int) (sum / limit);
   : v$ y8 e( C8 F0 ?9 i- ^/ s; t
9.         if (sum % limit != 0) {
   1 l5 X$ y* y0 ?1 e/ d+ D
10.             count++;
    
11.         }
    
12.         return count;
    + e4 x" c5 G1 T# p: M$ t# ~1 U  W
13.     }
    . P/ i' A8 g# Y; w9 n. z# q; Y2 C
14. }

复制代码

No.3 从第一个节点出发到最后一个节点的受限路径数

9 c2 k1 E/ N8 J, ~; F: u, a) ^8 i; r解题思路
: E' @, i& X. G* J" _
Dijkstra + DP
( E2 Y" A( G  X9 _. b6 T' e; f
代码展示
2 t( V- r! I# r4 N- j7 r: p* T

1. class Solution {
   
2.     static class Edge {
   
3.         int next;
   
4.         int len;
   
5. 
   0 Z" t: _) i/ b  l/ w
6.         Edge(int next, int len) {
   6 q* u. k1 u( l( L
7.             this.next = next;
   ; y% i) C, V4 M3 Z5 c9 q
8.             this.len = len;
   6 o8 t4 C6 C! m& r% C2 K1 k/ n
9.         }
   8 r' D; J- A# O! Y) j, f- h
10.     }
    
11. 
    
12.     public int countRestrictedPaths(int n, int[][] edges) {
    
13.         // 建图
    3 c) o1 }2 R$ y1 t1 U# I, E
14.         Map<Integer, List<Edge>> graph = new HashMap<>();
    5 ?; T0 X8 j3 N0 }# v
15.         for (int[] edge : edges) {
    
16.             for (int i = 0; i < 2; i++) {
    % N! I% Q2 u, H+ ~. m; t; m# h0 I
17.                 if (!graph.containsKey(edge<i>)) {
    6 `/ L: O1 p8 r+ K) Z! v) |
18.                     graph.put(edge<i>, new ArrayList<>());
    / ]" q7 o) y& z. F, U3 V
19.                 }
    . K- U* F8 q. g
20.                 graph.get(edge<i>).add(new Edge(edge[1 - i], edge[2]));
    . y! i/ ?! l( G$ x2 p0 q
21.             }
    
22.         }
    ( t  P; L# f" L# a# i! \
23.                 // dijkstra 求出 distanceToLastNode
      j' M' ~3 D! D0 F5 S# A% X
24.         var distanceToLastNode = dijkstra(n, graph);
    
25.         // DP
    ( ^- b' `# S- z, B% P" x$ K
26.         int[] mem = new int[n + 1];
    
27.         Arrays.fill(mem, -1);
    9 m& E! i: g* W; I8 {" X" e1 q, c
28.         mem[n] = 1;
    " X0 J. Z7 [4 n5 |' ]2 e- ]
29.         return dp(1, mem, distanceToLastNode, graph);
    
30.     }
    
31. 
    ( Y- _) r- N- d( S4 d
32.     private int dp(int cur, int[] mem, Map<Integer, Integer> distanceToLastNode, Map<Integer, List<Edge>> graph) {
    
33.         if (mem[cur] >= 0) {
    
34.             return mem[cur];
    * X" l( a2 Y! X/ Y) }1 M1 k$ l
35.         }
    ' |1 t6 i" G, T  S' h! A4 D
36.         mem[cur] = 0;
    0 W, X, M8 z" e1 @. F6 h% f8 ^) f
37.         for (var next : graph.get(cur)) {
    
38.             if (distanceToLastNode.get(cur) > distanceToLastNode.get(next.next)) {
    
39.                 mem[cur] = (mem[cur] + dp(next.next, mem, distanceToLastNode, graph)) % 1000000007;
    , ^' O/ S+ [9 X4 T" l" H# g
40.             }
    / B7 f) S. {, e4 u, H0 k
41.         }
    7 g# y+ ~0 G/ B- X; Y3 J5 G
42.         return mem[cur];
    
43.     }
    
44. 
    
45.     static class Node {
    + W2 Q3 Q5 S/ N  q9 N2 F
46.         int to;
    
47.         int len;
    
48. 
    4 l6 P, q& H  u+ ~6 s" R  X9 _
49.         Node(int to, int len) {
    / ~3 Q0 O0 b5 O! J. n/ s
50.             Look @t This To... = to;
    7 ]2 Z; l3 I% t( O; v: I  O7 ]  d$ R
51.             this.len = len;
    
52.         }
    
53.     }
    / S$ [4 |' \" j  A, L
54. 
    
55.     private Map<Integer, Integer> dijkstra(int start, Map<Integer, List<Edge>> graph) {
    + N. r/ t$ N  h" R/ g- x
56.         Set<Integer> visited = new HashSet<>();
    ' _# m4 ]6 U7 _' i/ S* v. z7 y
57.         Map<Integer, Integer> res = new HashMap<>();
    
58.         PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> (o1.len - o2.len));
    , i; X; c1 J; K2 h, R
59.         res.put(start, 0);
    
60.         heap.add(new Node(start, 0));
    
61.         while (!heap.isEmpty()) {
    0 W8 Q$ c" \( C9 P+ e
62.             Node node = heap.poll();
    
63.             if (visited.contains(node.to)) {
    6 E# X1 S- R- P8 J  }
64.                 continue;
    
65.             }
    
66.             visited.add(node.to);
    ) r0 F, h4 z# D" I) F9 X& F
67.             for (Edge e : graph.get(node.to)) {
    8 H" Q1 L6 N, y, Z
68.                 if (res.getOrDefault(e.next, Integer.MAX_VALUE) > node.len + e.len) {
      b5 W3 S0 K, ]1 n: ~! L
69.                     res.put(e.next, node.len + e.len);
    * L9 l  X: ?' w+ Q! B
70.                     heap.add(new Node(e.next, node.len + e.len));
    ! @! H- d1 c) J  f: u8 l7 ?0 }( j
71.                 }
    
72.             }
    
73.         }
    4 ^; @7 |8 `0 p! p& I: \3 ?
74.         return res;
    
75.     }
    
76. }</i></i></i>

复制代码

1 T" l" i* I0 \$ j9 S" c
No.4 使所有区间的异或结果为零
; c5 f' \+ T, [3 h; i( i
( Q3 |! u0 b5 w4 }5 J. t3 i解题思路

DP
! y7 n+ P* U5 O# s4 C  l7 @3 Q- c
代码展示
8 a$ ^" H: w8 q) p

1. class Solution {
   
2.     public int minChanges(int[] nums, int k) {
   ( ]  L  G; g+ p0 \7 R0 Q' i2 y
3.         // count[j] 表示在每个长度为 k 的子区间的第 i 个位置上，数字 j 出现了多少次
   
4.         int[][] count = new int[k][1 << 10];
   $ O. w5 w& K" P0 d
5.         for (int i = 0; i < nums.length; i++) {
   
6.             count[i % k][nums]++;
     T1 D7 [4 Z( i3 J3 f  |9 q
7.         }
   
8. 
   , d+ b* d2 b* c5 g, t/ u
9.         // dp 表示将每个子区间的前 i 个位置变成一致的至少要改变多少个数字
   
10.         int[][] dp = new int[k + 1][1 << 10];
    
11.         for (int i = 0; i <= k; i++) {
    
12.             Arrays.fill(dp, nums.length);
    
13.         }
    
14.         dp[0][0] = 0;
    # e+ a9 M9 [( j; f; \" n" K
15. 
    
16.         int min = nums.length, sum = 0;
    " }' D6 J* s  M+ f+ X! \% V
17.         for (int i = 1; i <= k; i++) {
    
18.             int[] cur = count[i - 1];
    
19.             int tot = 0, max = 0;
    
20.             for (int j : cur) {
    
21.                 tot += j;
    
22.                 max = Math.max(max, j);
    
23.             }
    - A/ f9 h9 h9 J7 }4 F
24.             sum += tot - max;
    ) H4 k, d5 ~/ u4 K6 \
25.             min = Math.min(min, max);
    
26.             for (int j = 0; j < (1 << 10); j++)
    
27.                 if (cur[j] > 0) {
    
28.                     int now = tot - cur[j];
    4 C5 s; `  T) ]0 K
29.                     for (int K = 0; K < (1 << 10); K++)
    
30.                         dp[j ^ K] = Math.min(dp[j ^ K], dp[i - 1][K] + now);
    - A* Q4 G! t' l: G' Q! ]
31.                 }
    # D1 P# S3 ~) A
32.         }
    / ~0 m0 k; G4 @% T1 Z
33.         return Math.min(dp[k][0], min + sum);
    ' A  s& L5 z0 W
34.     }
    * F, v* o  n7 C9 V% ]+ L8 Q0 s
35. }

复制代码

上岸算法由华大学长精心创立，是一家致力于用高质量，高互动性小班课程来帮助学生更好的在就业市场中定位以及求职的公司。我们以顶级的课程质量，高互动性的教学方式以及独特的小班教学模式来帮助学生更快的跨过求职的鸿沟，用最高效，经济，合理的方式帮助更多学生快速找到梦寐以求的工作。
9 K; V/ F' Z* f! C" D! N6 Q  A