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

3 e$ R" N% b7 W) N- }( Q
/ [  F- y% N/ Y6 t7 S! }$ F, A

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

解题思路

签到题。

代码展示

1. class Solution {
   ' E) E' }  B& p; x+ V
2.    public boolean checkZeroOnes(String s) {
   0 o$ T, ~! ^( O7 e
3.        return check(s, '1') > check(s, '0');
   % q/ ]+ S. B2 \+ X
4.    }
   % i' X' {$ R, }. d
5. 
   3 J( j3 e) a4 G; i- e3 C% H1 K
6.    private int check(String s, char c) {
   ( H. W( W0 c5 N& d7 c' W7 x
7.        int result = 0, count = 0;
   " L5 {, W! B/ j$ w4 z
8.        for (int i = 0; i < s.length(); i++) {
   # N$ v- a# ^' ]: t
9.            if (s.charAt(i) == c) {
   , r7 S) n" {4 m  H5 B
10.                count++;
    
11.                result = Math.max(result, count);
    
12.            } else {
    ) r+ \. u1 _  T0 ?# E. o% P+ \
13.                count = 0;
    
14.            }
    $ E  O# O: G% u. r; F
15.        }
    # [. h* i1 R# y# ~
16.        return result;
    ' b" x! l% W" t( ^- ^: b
17.    }
    
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))) {
   
4.            return -1;
   5 x" d4 [; t0 e
5.        }
   
6.        int left = 1, right = (int) 1e7;
   : |8 x1 w; k- u+ B0 L# @! S
7.        while (left + 1 < right) {
   
8.            int mid = (left + right) / 2;
   
9.            if (check(dist, hour, mid)) {
   
10.                right = mid;
    
11.            } else {
    9 p) d8 D( `3 |$ O6 h* w
12.                left = mid;
    
13.            }
    
14.        }
    
15.        return check(dist, hour, left) ? left : right;
    
16.    }
    
17. 
    7 c! S" ^: `9 h% C
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.        }
    1 G, {/ X; j& d% h1 l* ?
23.        return hour >= (double) cost + (1.0 * dist[dist.length - 1] / speed);
    ) c  D5 D4 F5 q  j/ K
24.    }
    8 T1 C  U7 n% K- w/ o
25. }

复制代码

No.3 跳跃游戏 VII

解题思路

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

代码展示

1. class Solution {
   * w; I* T; j. W" ], Y5 T# N9 j/ M
2.    public boolean canReach(String s, int minJump, int maxJump) {
   # q; E; ?( P7 d+ E2 t
3.        int n = s.length();
   1 |; t4 ]8 S% ]7 ]
4.        char[] str = s.toCharArray();
   
5.        if (str[n - 1] == '1') {
   ! O8 a' }( {9 L# l- Y
6.            return false;
   - D  w: _+ l0 |5 v' d1 r+ k
7.        }
   
8.        LinkedList<Integer> queue = new LinkedList<>();
   1 g1 t3 O# G& B, f, l/ n/ c
9.        queue.add(0);
   
10.        for (int i = 1; i < str.length; i++) {
    
11.            while (!queue.isEmpty() && queue.getFirst() + maxJump < i) {
    
12.                queue.pollFirst();
    
13.            }
    ! y* t, i* h$ g: Y% j! `
14.            if (!queue.isEmpty() && str[i] == '0' && queue.getFirst() + minJump <= i) {
    * y3 m' b; x* \, c
15.                if (i == str.length - 1) {
    
16.                    return true;
      k2 q: n" a3 }6 L& d
17.                }
    . {! O% d' E: ~4 T5 V* w7 V
18.                queue.add(i);
    
19.            }
    2 k5 H3 M( I0 v2 w; k, J7 [) \
20.        }
    9 {* e. g6 F/ j' {4 H6 h; F
21.        return false;
    ( @( P& d  q) J1 i
22.    }
    
23. }

复制代码

No.4 石子游戏 VIII

解题思路

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

代码展示

1. class Solution {
   
2.    public int stoneGameVIII(int[] stones) {
   
3.        int n = stones.length;
   
4.        long[] sum = new long[n];
   
5.        sum[0] = stones[0];
   . V; R) I7 P8 h- j8 a
6.        for (int i = 1; i < n; i++) {
   
7.            sum[i] = sum[i - 1] + stones[i];
   
8.        }
   
9.        long[] dp = new long[n];
   
10.        dp[n - 1] = sum[n - 1];
    2 Y0 A" v' ^; e
11.        long max = dp[n - 1];
    
12.        for (int i = n - 2; i > 0; i--) {
    ; y8 y; y4 S' s( e
13.            dp[i] = sum[i] - max;
    
14.            max = Math.max(max, dp[i]);
    
15.        }
    
16.        return (int) max;
    
17.    }
    3 @. s) u3 L+ a9 r
18. }
    

复制代码