找回密码
 注册账号
置顶:如何加入2024届新生微信群

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

上岸算法 回复:0 | 查看:3053 | 发表于 2021-3-8 00:25:30 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

No.1 检查二进制字符串字段
& |  h/ V( Z1 v5 e7 u6 m+ U
9 ^* E5 t5 \9 a% d* ?0 |( B+ C' l解题思路! r/ h1 k( e7 b; @* Z3 b

9 t5 T" }; o8 E5 A符合要求的字符串即前缀全是 1,后缀全是 0 的字符串。) \2 |, s, V- J4 U
, |, |1 c, Q" ^" L2 s; ^0 {
代码展示( {" B, j; @9 u' w! O6 h$ w
- y+ H, g+ h2 N% T
  1. class Solution {" k4 o* W! ^& U  V' R9 [7 ~5 M
  2.     public boolean checkOnesSegment(String s) {$ ~, X1 C2 c- I7 m* Q3 A  j4 C" O9 X% O
  3.         if (!s.contains("0")) {& G5 m0 ~  m- M9 M: u' T
  4.             return true;# Q6 q( X  q; H  x" K! m1 t( X- N6 ?% l
  5.         }
    ; |& r3 f3 C5 f7 e
  6.         if (s.substring(s.indexOf("0")).contains("1")) {
    $ P* B7 N% F+ j: i3 J
  7.             return false;! q$ v4 Y' B/ \$ U
  8.         }
    7 _* F$ X3 e5 Q+ S; e, L7 R. z
  9.         return true;% ]2 r- m# ?* T7 U* A6 q
  10.     }) w' n! z% }! W4 x: D3 [0 _
  11. }
复制代码
) d& T8 F3 ~$ {
No.2 构成特定和需要添加的最少元素
. W  V; m# V# z: }# l9 V$ v: B+ J! l1 N7 ^/ @0 ^1 H  D! D9 V
解题思路
/ G" z% \4 m! w2 p4 x8 L, z; X. W- C4 v2 r+ |* U" z( K/ _; t7 H
贪心即可,每次都添加绝对值尽可能大的。注意总和可能溢出 int,所以中间运算要使用 long。
( _* f& V+ w. I- C" p2 i( E% z8 v7 O- s2 {% O
代码展示
6 u% j  E6 z5 B0 N2 ]' J+ l' X+ ^/ K) [& z1 b. X# Q
  1. class Solution {) T% b/ d4 U- c  H# w
  2.     public int minElements(int[] nums, int limit, int goal) {
    ( A2 s: W3 C4 @
  3.         long sum = 0;6 o3 ?8 N. K4 b6 Y) W
  4.         for (int num : nums) {# J4 e, S! X3 R/ d: z
  5.             sum += num;# d2 n; n& ^& O' |( C5 G2 S
  6.         }( x5 F# k9 \; q6 H: Z. |9 r
  7.         sum = Math.abs(goal - sum);
    5 K! D/ p- c6 C
  8.         int count = (int) (sum / limit);8 y: n" c/ X# {: I$ {9 s7 K2 H; n
  9.         if (sum % limit != 0) {
    # S& e2 k- s0 X: |9 G% l
  10.             count++;# d7 Z- z8 {( J- p  t
  11.         }; @4 L; Z1 y* z
  12.         return count;2 Q. ^& E3 T- X
  13.     }
    5 }/ H- j) ^& o
  14. }
复制代码
* P. A- Y2 X3 G. ]4 \9 `
No.3 从第一个节点出发到最后一个节点的受限路径数

; e7 }8 ^8 a9 O; P) B: P( y& L, Y1 \6 C: J. W1 e. L& g
解题思路' {- \) A1 K7 b2 z1 G, A, u

! a  @2 `/ y2 f3 E' MDijkstra + DP
- S( h% W: C$ z$ h* ]
) P  k2 F3 q- z+ Z. u5 O( D0 c+ W代码展示

+ ~7 z4 {- q# d: p4 x
  f" T1 a/ A  D* P
  1. class Solution {; ]( B' k: k: O3 k- R9 `
  2.     static class Edge {
    ! ]) r# C! W( r3 G
  3.         int next;
    / Y5 S: b7 Q0 K$ \2 f& s2 A
  4.         int len;/ m4 Q" t' a. k! A! l8 ?

  5. , S  _, A$ f9 g5 f
  6.         Edge(int next, int len) {
    7 C4 t6 H4 I/ K7 c0 }! \
  7.             this.next = next;" q# D/ {8 G; N: [
  8.             this.len = len;1 p2 a7 X% L) l1 p; a
  9.         }
    4 ]: ]5 u& [# W4 b4 E
  10.     }. p& C8 A0 v1 F: K) N+ B% y
  11. * K! k8 ^* X2 n1 E8 @
  12.     public int countRestrictedPaths(int n, int[][] edges) {
    # q6 h) _6 p3 \% ], |
  13.         // 建图
      Z6 l! x/ |7 G# y" n; o
  14.         Map<Integer, List<Edge>> graph = new HashMap<>();
    : \+ D- z" b! j) T1 h
  15.         for (int[] edge : edges) {
    & M! e& @- M) l3 y& O( p
  16.             for (int i = 0; i < 2; i++) {) _. H8 Q9 b/ J% g* U5 B. J
  17.                 if (!graph.containsKey(edge<i>)) {
    : [! v6 G2 k  V" o5 q
  18.                     graph.put(edge<i>, new ArrayList<>());6 H0 a' \, s# ^1 w  r0 b
  19.                 }: C7 y0 O& s: B9 f4 \
  20.                 graph.get(edge<i>).add(new Edge(edge[1 - i], edge[2]));% |) ^: ^6 c9 Z5 J# J- Q, ^
  21.             }- ~' q5 _# q4 k
  22.         }
    % |* \( G3 [0 J) G  I. O
  23.                 // dijkstra 求出 distanceToLastNode
    5 N- N# r  p" W2 _2 Q" d" e7 K3 E
  24.         var distanceToLastNode = dijkstra(n, graph);
    9 s1 x8 Y  o8 _% i/ f2 \1 \
  25.         // DP
    ; y5 j* t: ^0 V% l, K
  26.         int[] mem = new int[n + 1];/ d+ h* i1 o  F/ U" C# y# q
  27.         Arrays.fill(mem, -1);. ^6 R- N: {7 t' O$ ^. |
  28.         mem[n] = 1;/ O8 m! k' P' \3 {6 d
  29.         return dp(1, mem, distanceToLastNode, graph);! Q4 I7 g8 Y% \
  30.     }
    ; v, v6 R+ d0 r! H
  31. % }! {8 m; Z3 k0 v1 l  M( |# D
  32.     private int dp(int cur, int[] mem, Map<Integer, Integer> distanceToLastNode, Map<Integer, List<Edge>> graph) {
    9 x' O, j  V' i, J/ i: v0 |
  33.         if (mem[cur] >= 0) {  L1 r- j+ C$ V
  34.             return mem[cur];
    - ^* [" C- U9 q$ m/ x6 Y  f9 m
  35.         }. \4 H1 i; ?' k/ [+ p
  36.         mem[cur] = 0;+ T" I" Q/ S( D( m0 g1 R
  37.         for (var next : graph.get(cur)) {
    , G# K5 ^; D3 N1 G. k
  38.             if (distanceToLastNode.get(cur) > distanceToLastNode.get(next.next)) {
    2 z+ R- S0 X, l. Y! Y' X5 y
  39.                 mem[cur] = (mem[cur] + dp(next.next, mem, distanceToLastNode, graph)) % 1000000007;
    - U9 ?0 r+ b: U, d- X* [7 J
  40.             }3 o+ U+ R  t5 {* {* K
  41.         }
    $ K  F' ]1 B7 ^' c9 u8 s- [
  42.         return mem[cur];
    1 T) o! |* h- H  S" N5 d# S
  43.     }
    0 H0 y3 _5 z4 G% n: b

  44. " z; f# g! T6 Q) g) Q6 d6 D1 z" Q
  45.     static class Node {# z( x/ _. {) O! ?) O( n
  46.         int to;& c, Y; C$ `/ X( o8 t( _  A( h8 F6 T
  47.         int len;& H, n" T0 _" H+ ^

  48. - }; F( e- e9 B$ [: n
  49.         Node(int to, int len) {) d: h8 d' ]4 A9 F1 D+ y% q( X
  50.             Look @t This To... = to;
    2 D1 y$ E2 u9 h2 P5 e: U1 n
  51.             this.len = len;
      Z  \& R3 A/ a4 o7 M  u4 q# O" h' c
  52.         }
    ( S6 n" H* j4 B: ]
  53.     }" y1 z  M) @; Q1 ~

  54. 1 P! e: Q( ^7 v
  55.     private Map<Integer, Integer> dijkstra(int start, Map<Integer, List<Edge>> graph) {6 d4 w4 ]% ^4 H8 m" S" H9 Z
  56.         Set<Integer> visited = new HashSet<>();
    % k" z0 g6 X# ]% s- [; D
  57.         Map<Integer, Integer> res = new HashMap<>();# l4 R* L2 X5 O* M7 `
  58.         PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> (o1.len - o2.len));6 x) z# W# Y& V( ?" F
  59.         res.put(start, 0);! O. H* K6 t" t0 N7 S6 u8 g
  60.         heap.add(new Node(start, 0));8 O7 j+ D, L. ]$ D. Y5 I2 H
  61.         while (!heap.isEmpty()) {
    " Y4 k# O) r  n" A
  62.             Node node = heap.poll();3 S3 l) G$ [  [) R( s- r6 Z
  63.             if (visited.contains(node.to)) {
    * o$ k" _1 [- O+ g
  64.                 continue;1 B; p9 S0 T$ M/ n: L
  65.             }; s6 U. b: z, x: b: [7 X) G+ o' S* o: n
  66.             visited.add(node.to);
    ! U' W6 s/ l. }4 w& S0 X
  67.             for (Edge e : graph.get(node.to)) {
    3 E# w. `4 c- e0 q; ]* x% h/ x
  68.                 if (res.getOrDefault(e.next, Integer.MAX_VALUE) > node.len + e.len) {
    6 L4 U3 l8 x$ U! c. O5 O; K/ n9 O
  69.                     res.put(e.next, node.len + e.len);$ u8 _  M3 f# f$ G+ ]% @
  70.                     heap.add(new Node(e.next, node.len + e.len));' a" h: a, K( f: m. Q! B
  71.                 }
    1 H5 z# s, X" `& Q: L* v
  72.             }
    3 n8 v! r8 P; ^
  73.         }
    2 |" x3 n/ t/ I$ b: p- k& l! v
  74.         return res;
    * R/ @; C, C# ?7 d3 H
  75.     }
    6 g2 |: N1 {. m1 h8 u
  76. }</i></i></i>
复制代码
' a( X3 z& [4 F4 ~

3 u+ q9 J% P- d& G2 t- w, s2 ^! iNo.4 使所有区间的异或结果为零
5 \9 m* n- ~, g) z* Z( Y; ]

6 R  I  }: h# V" x解题思路
6 ]( T1 ~( o3 C; r3 g$ A, C7 C

  D8 B4 j" P& A# [8 ZDP; M0 [& m7 _! ^$ g  l& ]5 x
0 J% `' Z; v% E7 R% B2 t
代码展示
# @7 o0 Q* j  J3 p4 U1 _) L

; p8 G! o; w( ^/ ~
  1. class Solution {- [; S: N' S! {
  2.     public int minChanges(int[] nums, int k) {1 _. G4 d' _1 M# W9 R/ _6 q
  3.         // count[j] 表示在每个长度为 k 的子区间的第 i 个位置上,数字 j 出现了多少次
    + L7 F; V! _1 e5 R3 r
  4.         int[][] count = new int[k][1 << 10];4 q3 a8 z+ o* J
  5.         for (int i = 0; i < nums.length; i++) {/ R6 d/ j7 M( z
  6.             count[i % k][nums]++;
    ! l5 q9 K, H% {
  7.         }, L  q+ {8 S3 `  w/ A
  8. 7 a, L5 y% |, F) ~9 W( B
  9.         // dp 表示将每个子区间的前 i 个位置变成一致的至少要改变多少个数字. ]8 X% N8 f% j; p
  10.         int[][] dp = new int[k + 1][1 << 10];- u- Z. J: ], S3 Z8 u  A5 t
  11.         for (int i = 0; i <= k; i++) {
    0 w; i. V* _& e- L/ K7 ]' w; O  F
  12.             Arrays.fill(dp, nums.length);& {6 K2 f" y; e$ J( N  S' @. Z& P
  13.         }
    7 k0 S8 }; n2 B: G
  14.         dp[0][0] = 0;' V' }* g  p9 ]3 O- E

  15. * S. r$ h, @. S+ M* P) i  O% J
  16.         int min = nums.length, sum = 0;" V) t3 k) s1 k4 y* S4 U" E/ V2 S  s
  17.         for (int i = 1; i <= k; i++) {* a- U7 Y: Z% X! q' X" \. X
  18.             int[] cur = count[i - 1];
    # O5 v! l% y1 d( O' Y
  19.             int tot = 0, max = 0;
    . M3 x2 i! c5 }5 e) Y6 ~
  20.             for (int j : cur) {
    & P7 m6 B5 O* ]
  21.                 tot += j;3 q) A: }3 {' e/ m! B9 M
  22.                 max = Math.max(max, j);; A8 b4 x' P2 S  p
  23.             }
    5 t, C) j1 j4 y1 D
  24.             sum += tot - max;
    7 `! q, Q7 a& @, u( ^. I$ T. g
  25.             min = Math.min(min, max);
    7 l; `8 i' M. N" `" C! `) V$ \
  26.             for (int j = 0; j < (1 << 10); j++)8 ?9 t+ @7 E7 z. x; X6 F) H2 J
  27.                 if (cur[j] > 0) {% v% F& L' q6 a9 c/ F
  28.                     int now = tot - cur[j];2 @! V, k5 B* B/ f) A; P
  29.                     for (int K = 0; K < (1 << 10); K++)
    ) R, i) A0 q' h8 E
  30.                         dp[j ^ K] = Math.min(dp[j ^ K], dp[i - 1][K] + now);
    # v* T/ h" y& `
  31.                 }
    ) ^" w8 }; }, O, r/ d
  32.         }. X: w& P" V' h5 M: a
  33.         return Math.min(dp[k][0], min + sum);* Z) K0 z9 A0 c& ^: x9 L
  34.     }0 F& e* Z4 Y7 K2 T8 v3 r
  35. }
复制代码

, m$ A! F' S1 I! c上岸算法由华大学长精心创立,是一家致力于用高质量,高互动性小班课程来帮助学生更好的在就业市场中定位以及求职的公司。我们以顶级的课程质量,高互动性的教学方式以及独特的小班教学模式来帮助学生更快的跨过求职的鸿沟,用最高效,经济,合理的方式帮助更多学生快速找到梦寐以求的工作。# R, H8 h5 C: x5 [

本帖子中包含更多资源

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

x
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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