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

- e, T1 M7 t& I1 `
  Y$ Z9 J) o9 y, I7 u. r

No.1 哪种连续子字符串更长

解题思路

签到题。

代码展示

1. class Solution {
   3 w. u$ Q2 T; a3 a9 Q& B% w, X
2.    public boolean checkZeroOnes(String s) {
   
3.        return check(s, '1') > check(s, '0');
   1 r3 N, V! O; @# k+ \
4.    }
   & [1 y1 z+ C/ G1 q
5. 
   ( ^+ P8 Y9 W$ T" H
6.    private int check(String s, char c) {
   ' }+ w6 q$ Y9 P
7.        int result = 0, count = 0;
   ( I" {8 f  s. i9 [/ x
8.        for (int i = 0; i < s.length(); i++) {
   
9.            if (s.charAt(i) == c) {
   
10.                count++;
    
11.                result = Math.max(result, count);
    
12.            } else {
    # m) a8 ?4 x' c3 x$ S2 N2 ]" j
13.                count = 0;
    
14.            }
    
15.        }
    9 \/ y" S- ~% M( P
16.        return result;
    . n3 z: c. z- j
17.    }
    - N1 R; O+ \7 ~
18. }

复制代码

秋招将近，华大学长/斯坦福学姐联合组织了一场面向北美2021秋招的算法带刷公益活动。

带刷内容源于Leetcode 原题/近期大厂算法面试真题。

模拟面试+面试技巧分享，备战秋招！

只要你熟练掌握一门计算机语言，比如：java/ python 等，即可免费参与本次刷题活动。

活动时间：2021/6/1-2021/6/25

No.2 准时到达的列车最小时速

解题思路

二分答案。

对于给定车速计算通勤总耗时的时候，建议仅在最后一次运算使用浮点运算，其他均使用整型向上取整的除法。

代码展示

1. class Solution {
   
2.    public int minSpeedOnTime(int[] dist, double hour) {
   
3.        if (!check(dist, hour, (int) (1e7 + 1))) {
   6 _) L! A6 K1 L2 L- `: X0 `
4.            return -1;
   0 s& I- s3 H- q. c) S
5.        }
   
6.        int left = 1, right = (int) 1e7;
   
7.        while (left + 1 < right) {
   3 `' X" t  g7 e+ r
8.            int mid = (left + right) / 2;
   
9.            if (check(dist, hour, mid)) {
   3 Q& \, Q' o6 A9 I5 y8 c
10.                right = mid;
    
11.            } else {
    
12.                left = mid;
    2 N- W( G1 @! U3 i  O' T. S" |$ G
13.            }
    
14.        }
    
15.        return check(dist, hour, left) ? left : right;
    0 x  d4 ]( @" L: m) W7 P1 P8 Y+ i% J3 l/ \
16.    }
    
17. 
    ( x# ?! w3 e2 j/ S' _+ [# _5 F2 s& H
18.    private boolean check(int[] dist, double hour, int speed) {
    - P0 @: R. T& Y  \, s
19.        int cost = 0;
    
20.        for (int i = 0; i < dist.length - 1; i++) {
    5 W/ P+ e* q$ }4 Y* L% r" S
21.            cost += (dist[i] + speed - 1) / speed;
    8 s/ w! h/ V2 j( ^8 U) @6 R* p0 V5 c
22.        }
    
23.        return hour >= (double) cost + (1.0 * dist[dist.length - 1] / speed);
    * Y/ t# }0 b3 z; e0 X9 D
24.    }
    " z7 i8 u( N7 R8 ^2 f4 N: N
25. }

复制代码

No.3 跳跃游戏 VII

解题思路

类似于滑动窗口，使用队列维护可以跳跃到当前点的点集合。

代码展示

1. class Solution {
   6 ?' {; R4 N* \$ I
2.    public boolean canReach(String s, int minJump, int maxJump) {
     A) R( j( C. p/ h- M
3.        int n = s.length();
   
4.        char[] str = s.toCharArray();
   
5.        if (str[n - 1] == '1') {
   4 R3 u  c2 a& n4 p, c
6.            return false;
   $ \) W8 `7 F/ X7 J, ^: }' ^/ b  C
7.        }
   
8.        LinkedList<Integer> queue = new LinkedList<>();
   % s/ ?$ E  Y5 H7 H9 G( e7 g  B8 B
9.        queue.add(0);
   
10.        for (int i = 1; i < str.length; i++) {
    - u: V' s- e: m; u4 ~/ A
11.            while (!queue.isEmpty() && queue.getFirst() + maxJump < i) {
    7 ^/ Z* E2 A; J; q6 ]
12.                queue.pollFirst();
    
13.            }
    
14.            if (!queue.isEmpty() && str[i] == '0' && queue.getFirst() + minJump <= i) {
    
15.                if (i == str.length - 1) {
    * s3 m% h1 Q+ k$ ^) v
16.                    return true;
    8 ^9 e) ^  B8 S, k3 o$ g
17.                }
    
18.                queue.add(i);
    
19.            }
    
20.        }
    9 l: l" P: t8 v
21.        return false;
    6 ^: U4 o3 t! |, e
22.    }
    
23. }

复制代码

No.4 石子游戏 VIII

解题思路

看似每次要重新放回去一个总和石子很复杂，但其实恰相反：放回去的石子必然被对手拿到，因此抵消了自己拿到的和。

代码展示

1. class Solution {
   6 h% h" L& _; M4 R8 u4 x" t
2.    public int stoneGameVIII(int[] stones) {
   : s: f" Z& T+ z5 g7 i* b( \
3.        int n = stones.length;
   
4.        long[] sum = new long[n];
   2 n, F! `+ ~0 P: {6 Z, Q+ l
5.        sum[0] = stones[0];
   
6.        for (int i = 1; i < n; i++) {
   
7.            sum[i] = sum[i - 1] + stones[i];
   
8.        }
   ) h* `9 ~7 }/ F+ ~. P0 a; F
9.        long[] dp = new long[n];
   
10.        dp[n - 1] = sum[n - 1];
    * ~- i6 \, C" T& k! a* E
11.        long max = dp[n - 1];
    * ~( Q& v! N; [" C
12.        for (int i = n - 2; i > 0; i--) {
    : ~5 i) u2 U5 h
13.            dp[i] = sum[i] - max;
    
14.            max = Math.max(max, dp[i]);
    
15.        }
    1 {/ x$ J" k) w5 _3 G  |# \* e
16.        return (int) max;
    
17.    }
    ! I$ e8 d) p  {3 c2 p( m
18. }
    

复制代码

/ a- [3 v( f7 P! X5 P9 G/ r