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

7 }* Y$ C7 j3 M- F7 x9 O

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

解题思路

签到题。

代码展示

1. class Solution {
   
2.    public boolean checkZeroOnes(String s) {
   / w9 R) H6 j: h5 e: y/ q
3.        return check(s, '1') > check(s, '0');
   
4.    }
   
5. 
   
6.    private int check(String s, char c) {
   
7.        int result = 0, count = 0;
   5 \7 |( D$ S3 ?; B" a% f0 W. X# G
8.        for (int i = 0; i < s.length(); i++) {
   0 X5 V; v& q6 v2 G
9.            if (s.charAt(i) == c) {
   
10.                count++;
    
11.                result = Math.max(result, count);
    " R& R2 A4 {- b4 U- \8 p" R- D
12.            } else {
    
13.                count = 0;
    ; T/ F& h9 n* S" A+ Z  K# K& c+ Y
14.            }
    . ~8 A9 j. u3 ~) e  v
15.        }
    8 @/ Y1 U8 G$ t' `. n% S2 N7 o( L
16.        return result;
    
17.    }
    ! p6 U) s: Y( {: C1 g8 C0 w
18. }

复制代码

4 I! m/ m2 q' p" l. ?8 U% W

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

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

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

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

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

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

解题思路

二分答案。

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

代码展示

1. class Solution {
   - O- ], O4 L8 D8 a# b0 ~& P
2.    public int minSpeedOnTime(int[] dist, double hour) {
   ' Z' ^$ a) \0 b7 ^
3.        if (!check(dist, hour, (int) (1e7 + 1))) {
   : I3 V5 ?# l1 w* S
4.            return -1;
   . j& t+ q) X% j
5.        }
   + n. F! A$ {0 Q9 K2 u
6.        int left = 1, right = (int) 1e7;
   
7.        while (left + 1 < right) {
   
8.            int mid = (left + right) / 2;
   
9.            if (check(dist, hour, mid)) {
   
10.                right = mid;
    % b* L& D- v0 ~! V
11.            } else {
    # W3 J0 e+ _2 c/ b
12.                left = mid;
    ; |: }6 \2 v9 z2 r3 y
13.            }
    : a  C/ ?% o: D% w. d0 r3 E. h  L
14.        }
    
15.        return check(dist, hour, left) ? left : right;
    
16.    }
    7 D! P( J* k. {& [+ Q. s" ]
17. 
    
18.    private boolean check(int[] dist, double hour, int speed) {
    
19.        int cost = 0;
    
20.        for (int i = 0; i < dist.length - 1; i++) {
    
21.            cost += (dist[i] + speed - 1) / speed;
    
22.        }
    
23.        return hour >= (double) cost + (1.0 * dist[dist.length - 1] / speed);
    / j/ k, C4 [  k( ~( F5 H( X
24.    }
    ( `: s) p" y: i0 P# {7 d. r/ A
25. }

复制代码

: S/ U6 m! B, j/ d: C4 x: @

No.3 跳跃游戏 VII

解题思路

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

代码展示

1. class Solution {
   
2.    public boolean canReach(String s, int minJump, int maxJump) {
     h7 l- k% z) K3 l9 m* v4 E0 L
3.        int n = s.length();
   # |0 f: b. G: Y$ ]$ T2 O6 |4 [
4.        char[] str = s.toCharArray();
   + ]6 b8 `" g6 x2 E1 ?
5.        if (str[n - 1] == '1') {
   & t3 R% S9 {! I$ O5 H/ `
6.            return false;
   
7.        }
   : K+ l: |4 n7 Q5 S/ a
8.        LinkedList<Integer> queue = new LinkedList<>();
   
9.        queue.add(0);
   9 M" ]+ n/ F- S3 s1 J) O
10.        for (int i = 1; i < str.length; i++) {
    
11.            while (!queue.isEmpty() && queue.getFirst() + maxJump < i) {
    
12.                queue.pollFirst();
    
13.            }
    
14.            if (!queue.isEmpty() && str[i] == '0' && queue.getFirst() + minJump <= i) {
    
15.                if (i == str.length - 1) {
    4 [4 ?/ j# ~4 O& ?
16.                    return true;
    
17.                }
    $ O; Y; [# k) s
18.                queue.add(i);
    & c, Z, d* I3 p1 T. E! h  k0 u
19.            }
    - U, Y  @& `+ c7 |. E: y9 u
20.        }
    0 R  b" B3 z/ a5 ?  W' {# c
21.        return false;
    
22.    }
    ) W# Q' a% _& q# z0 j; E: |
23. }

复制代码

No.4 石子游戏 VIII

解题思路

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

代码展示

1. class Solution {
   
2.    public int stoneGameVIII(int[] stones) {
   3 A: z1 f" Y" S  b4 Q. G, |
3.        int n = stones.length;
   
4.        long[] sum = new long[n];
   
5.        sum[0] = stones[0];
   - i8 A: B7 H+ b- N) e
6.        for (int i = 1; i < n; i++) {
   % T# W5 r3 j2 |, U" l. b
7.            sum[i] = sum[i - 1] + stones[i];
   1 F3 t# M1 |. }6 m# v
8.        }
   
9.        long[] dp = new long[n];
   
10.        dp[n - 1] = sum[n - 1];
    & Z: a" I, s* O
11.        long max = dp[n - 1];
    
12.        for (int i = n - 2; i > 0; i--) {
    9 g1 `5 N* o/ E6 D' r- b
13.            dp[i] = sum[i] - max;
    % s3 o& N8 [3 ?0 x/ F- q; b+ v( a
14.            max = Math.max(max, dp[i]);
    
15.        }
    
16.        return (int) max;
    
17.    }
    & n+ k8 }' V+ e
18. }
    

复制代码