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

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

解题思路

签到题。

代码展示

1. class Solution {
   ' O5 f; H' {) p8 `& c" G: w
2.    public boolean checkZeroOnes(String s) {
   
3.        return check(s, '1') > check(s, '0');
   
4.    }
   
5. 
   
6.    private int check(String s, char c) {
   
7.        int result = 0, count = 0;
   
8.        for (int i = 0; i < s.length(); i++) {
   
9.            if (s.charAt(i) == c) {
   9 l0 @6 h: q1 z, z! h6 T2 Q
10.                count++;
    
11.                result = Math.max(result, count);
    
12.            } else {
    % h2 V- S8 G2 D3 d2 M$ ?! ^+ g
13.                count = 0;
      w# q6 o) R9 I6 O( w
14.            }
    1 k9 Q5 C4 k; ], p5 \, u
15.        }
    & `$ |: r' ?5 M( I( v# s1 D3 [
16.        return result;
    
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))) {
   ) {  I3 n) G4 I* R2 w+ X/ t2 r
4.            return -1;
   ! ^# Q* p+ \: s* g. }
5.        }
   - ^$ I6 P; s. A# H6 y" c
6.        int left = 1, right = (int) 1e7;
   2 X4 H( V% Q, e. }2 M
7.        while (left + 1 < right) {
   5 S" R' Y# {* i: b- G
8.            int mid = (left + right) / 2;
   
9.            if (check(dist, hour, mid)) {
   6 O! c; v5 Y; o
10.                right = mid;
    
11.            } else {
    
12.                left = mid;
    2 n% G1 @! k4 C
13.            }
    0 ]  C  n3 ~& _! N/ [: r0 G7 {
14.        }
    ( e/ A. `! @1 ?: Q! i
15.        return check(dist, hour, left) ? left : right;
    
16.    }
    
17. 
    
18.    private boolean check(int[] dist, double hour, int speed) {
    
19.        int cost = 0;
    " S+ r1 O' G% d) t- ~! s% W( L
20.        for (int i = 0; i < dist.length - 1; i++) {
    6 Y9 W' X" R9 e' H# a/ W* j& R1 J
21.            cost += (dist[i] + speed - 1) / speed;
    3 [  E. M9 J0 |: a2 n* @2 N
22.        }
    
23.        return hour >= (double) cost + (1.0 * dist[dist.length - 1] / speed);
    , M$ ^; Z$ a' s1 m
24.    }
    
25. }

复制代码

No.3 跳跃游戏 VII

解题思路

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

代码展示

1. class Solution {
   
2.    public boolean canReach(String s, int minJump, int maxJump) {
   # A! E# K) P. N% `9 `3 B2 x* Y5 Z
3.        int n = s.length();
   ; f% o: w6 }9 y, ^, K$ `+ T: A+ x
4.        char[] str = s.toCharArray();
   ; F2 h" f2 C8 d% U: t
5.        if (str[n - 1] == '1') {
   9 G3 [# N$ x+ `7 G
6.            return false;
   8 a7 Z/ v9 y# F
7.        }
   
8.        LinkedList<Integer> queue = new LinkedList<>();
   
9.        queue.add(0);
   " x$ k( _9 U9 z. w$ ^
10.        for (int i = 1; i < str.length; i++) {
    , l+ g/ e9 Z& I# v/ J6 g
11.            while (!queue.isEmpty() && queue.getFirst() + maxJump < i) {
    
12.                queue.pollFirst();
    
13.            }
    / e4 D+ v2 R! R
14.            if (!queue.isEmpty() && str[i] == '0' && queue.getFirst() + minJump <= i) {
    
15.                if (i == str.length - 1) {
    
16.                    return true;
    
17.                }
    
18.                queue.add(i);
    9 F' D+ p5 S; k7 g
19.            }
    8 I+ \9 H. g3 O2 V
20.        }
    / V7 N( D3 v" Z" L
21.        return false;
    * t5 ^1 ~1 V5 R4 n! W
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];
   . ^$ \. P, {2 q' a- k' y+ z- l: f
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];
   
10.        dp[n - 1] = sum[n - 1];
    4 Z$ ?8 W6 z. T
11.        long max = dp[n - 1];
    
12.        for (int i = n - 2; i > 0; i--) {
    
13.            dp[i] = sum[i] - max;
    
14.            max = Math.max(max, dp[i]);
    
15.        }
    2 Q4 V( Y& h% G( @
16.        return (int) max;
    $ [: t* Q3 H5 a+ ]
17.    }
    . i7 x6 d% }7 I6 o% S
18. }
    

复制代码