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

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

解题思路

签到题。

代码展示

1. class Solution {
   9 J! k" m! @/ L/ D6 w- W  v1 y9 M: V
2.    public boolean checkZeroOnes(String s) {
   + B" m) s* H5 i9 H
3.        return check(s, '1') > check(s, '0');
   : D! M5 |4 q1 H, f$ m) I
4.    }
   
5. 
   ; k) b# l' {3 d6 B8 q; a
6.    private int check(String s, char c) {
   $ S# c/ G  r5 ]
7.        int result = 0, count = 0;
   
8.        for (int i = 0; i < s.length(); i++) {
   / \1 B& _0 L7 _# R) y/ [
9.            if (s.charAt(i) == c) {
   6 j; z, `5 N0 H  ?/ E
10.                count++;
    
11.                result = Math.max(result, count);
    
12.            } else {
    
13.                count = 0;
    , d) j; a6 D0 z  n
14.            }
      X5 k9 r# F+ d
15.        }
    
16.        return result;
    
17.    }
    
18. }

复制代码

" k$ m7 k+ ]- L

秋招将近，华大学长/斯坦福学姐联合组织了一场面向北美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))) {
   
4.            return -1;
   
5.        }
   
6.        int left = 1, right = (int) 1e7;
   9 Z* v* Q0 F& R; i4 N5 s
7.        while (left + 1 < right) {
   
8.            int mid = (left + right) / 2;
   
9.            if (check(dist, hour, mid)) {
   
10.                right = mid;
    1 x' r' G  ^4 k4 J" ~: S7 N! E+ z
11.            } else {
    " {8 v) a/ _; Q# c
12.                left = mid;
    - k8 F( X) O3 k# p* Z% ?2 E, G* Z1 H
13.            }
    ' d! B$ r1 O3 a5 A+ U
14.        }
    9 ^: j3 I( ^1 y0 b& B/ i
15.        return check(dist, hour, left) ? left : right;
    7 w. j- k0 q5 q
16.    }
    : d$ `7 Y* w/ E1 M& Z
17. 
    
18.    private boolean check(int[] dist, double hour, int speed) {
    
19.        int cost = 0;
    / }8 H- k2 @9 v% V: `
20.        for (int i = 0; i < dist.length - 1; i++) {
    
21.            cost += (dist[i] + speed - 1) / speed;
    3 j) N6 P( z* s) ?
22.        }
    ! H/ F6 W' l5 |# c2 T
23.        return hour >= (double) cost + (1.0 * dist[dist.length - 1] / speed);
    ) _$ a6 Y6 A5 d% }
24.    }
    
25. }

复制代码

( h7 v: I& C5 K2 G

No.3 跳跃游戏 VII

解题思路

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

代码展示

1. class Solution {
   4 e, X" q3 R4 v+ q, W1 ?: k4 Q
2.    public boolean canReach(String s, int minJump, int maxJump) {
   9 d& q' i$ I; b' x4 b
3.        int n = s.length();
   
4.        char[] str = s.toCharArray();
   
5.        if (str[n - 1] == '1') {
   . J7 {. F# n. z' p
6.            return false;
   
7.        }
   
8.        LinkedList<Integer> queue = new LinkedList<>();
   4 i- D% `  T# _7 O! f3 Z
9.        queue.add(0);
   ; I: c* L# Y2 u5 {  Q# l0 b2 Z
10.        for (int i = 1; i < str.length; i++) {
    
11.            while (!queue.isEmpty() && queue.getFirst() + maxJump < i) {
    ' M& e+ M3 [5 J2 q& `
12.                queue.pollFirst();
    - d$ o8 }1 {% J' w2 g& C9 A& S
13.            }
    
14.            if (!queue.isEmpty() && str[i] == '0' && queue.getFirst() + minJump <= i) {
    6 s, j9 s* f+ P; A
15.                if (i == str.length - 1) {
    3 x/ W$ ~3 |- H
16.                    return true;
    
17.                }
    : v( B8 r1 b, ]
18.                queue.add(i);
    & S( X8 z1 w5 B  ]2 H* U5 t
19.            }
    
20.        }
    # f4 Y# U9 {* w9 q8 d. C8 F% K6 ~2 R
21.        return false;
    4 @* C, X  I: o0 b5 r: P
22.    }
    
23. }

复制代码

No.4 石子游戏 VIII

解题思路

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

代码展示

1. class Solution {
   
2.    public int stoneGameVIII(int[] stones) {
   
3.        int n = stones.length;
   9 |6 t3 F9 K- g& r9 n
4.        long[] sum = new long[n];
   ) u9 x/ U% x6 W4 U
5.        sum[0] = stones[0];
   
6.        for (int i = 1; i < n; i++) {
   
7.            sum[i] = sum[i - 1] + stones[i];
   
8.        }
   
9.        long[] dp = new long[n];
   % ]  w( x) `" [0 J+ R5 Z
10.        dp[n - 1] = sum[n - 1];
    8 x( ?. a8 g& F6 C% a9 G3 V
11.        long max = dp[n - 1];
    * _& l5 b6 {3 h/ v9 ?
12.        for (int i = n - 2; i > 0; i--) {
    + s$ C+ W8 o( K
13.            dp[i] = sum[i] - max;
    - U- P( R) ]0 Z) ^
14.            max = Math.max(max, dp[i]);
    
15.        }
    
16.        return (int) max;
    ) ?0 [/ S6 C/ h+ H
17.    }
      i5 C9 S% j* m) Y" X
18. }
    

复制代码

) |6 ~( U0 w( \( Q  X( S