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

) E9 s: v- r9 O7 V
4 I3 Q% H- y1 D5 @8 G

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

解题思路

签到题。

代码展示

1. class Solution {
   
2.    public boolean checkZeroOnes(String s) {
   
3.        return check(s, '1') > check(s, '0');
   ; `4 f# X' q: N0 ?+ U( b
4.    }
   , f: V; f; S" [# F) ]+ J
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) {
   
10.                count++;
      {* V" p/ z. H- r3 y6 i
11.                result = Math.max(result, count);
    & H5 j2 q! k9 U. |5 S
12.            } else {
    
13.                count = 0;
    
14.            }
    
15.        }
    
16.        return result;
    , I+ v* u  e- O. U9 @5 ?8 ]8 o
17.    }
    0 [0 Z: ^/ o% I. F* G
18. }

复制代码

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

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

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

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

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

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

解题思路

二分答案。

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

代码展示

1. class Solution {
   , d. C; \: \* [6 I! v
2.    public int minSpeedOnTime(int[] dist, double hour) {
   8 c2 }4 R  D' n5 E7 y6 W
3.        if (!check(dist, hour, (int) (1e7 + 1))) {
   
4.            return -1;
   ; l' G8 o  L" d2 h. k9 H7 x
5.        }
   
6.        int left = 1, right = (int) 1e7;
   
7.        while (left + 1 < right) {
   ; Z' e7 H/ a) m* ~8 ~1 z
8.            int mid = (left + right) / 2;
     F* ]- n8 P4 K' X
9.            if (check(dist, hour, mid)) {
   
10.                right = mid;
    
11.            } else {
    
12.                left = mid;
    
13.            }
    : d) Q- A- J  P8 M+ j. b- S1 ?
14.        }
    * K* [4 B0 `6 ^- @4 r) ?1 O/ A4 U6 ]
15.        return check(dist, hour, left) ? left : right;
    
16.    }
    - Z. O7 E9 o2 e. N- O9 w# h' u2 ~: y
17. 
    / p% @* t+ {! h  y
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.        }
    2 X% x/ c. }' t
23.        return hour >= (double) cost + (1.0 * dist[dist.length - 1] / speed);
    
24.    }
    + }( c/ X% o1 \0 }  n
25. }

复制代码

2 W8 p" D4 j) j( k

No.3 跳跃游戏 VII

解题思路

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

代码展示

1. class Solution {
   2 M- E3 i6 S0 J1 N  _( X9 }
2.    public boolean canReach(String s, int minJump, int maxJump) {
   
3.        int n = s.length();
   1 |% Y# r+ l; [4 S, [- ?3 b
4.        char[] str = s.toCharArray();
   
5.        if (str[n - 1] == '1') {
   6 ^. x/ i; Z8 c: W2 C( |
6.            return false;
   
7.        }
   * S. o/ G3 E+ o( W+ b
8.        LinkedList<Integer> queue = new LinkedList<>();
   
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.            }
    
14.            if (!queue.isEmpty() && str[i] == '0' && queue.getFirst() + minJump <= i) {
    2 s- P! q  s5 @: v
15.                if (i == str.length - 1) {
    
16.                    return true;
    ) d7 I! P$ _9 ?4 P  R
17.                }
    
18.                queue.add(i);
    
19.            }
    8 w5 ], E5 Y4 _4 @
20.        }
    
21.        return false;
    % q" P9 Y' ?) ]. q* j5 F
22.    }
    2 p: w( s) M- p& R" C
23. }

复制代码

No.4 石子游戏 VIII

解题思路

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

代码展示

1. class Solution {
   4 X( u. h1 ^. m- U$ `
2.    public int stoneGameVIII(int[] stones) {
   : ~6 U' f0 f! \( f! G% D' |  a
3.        int n = stones.length;
   9 B" k5 e: F' I& m  E: h. c
4.        long[] sum = new long[n];
   
5.        sum[0] = stones[0];
   0 `5 }  t" Y8 f* |* }
6.        for (int i = 1; i < n; i++) {
   8 \7 w. W* D( M( R" e, }
7.            sum[i] = sum[i - 1] + stones[i];
   ' Z" l' _! W! a
8.        }
   
9.        long[] dp = new long[n];
   
10.        dp[n - 1] = sum[n - 1];
    
11.        long max = dp[n - 1];
    
12.        for (int i = n - 2; i > 0; i--) {
    ! T5 [' K' M4 t" `
13.            dp[i] = sum[i] - max;
    
14.            max = Math.max(max, dp[i]);
    
15.        }
    
16.        return (int) max;
    
17.    }
    
18. }
    

复制代码