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

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

解题思路

签到题。

代码展示

1. class Solution {
   
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;
   3 S1 O$ J$ g: m7 l7 i. N( T
8.        for (int i = 0; i < s.length(); i++) {
   1 v$ I- k# `+ t. w' d7 |3 h+ E
9.            if (s.charAt(i) == c) {
   
10.                count++;
    
11.                result = Math.max(result, count);
    
12.            } else {
    
13.                count = 0;
    
14.            }
      p2 {" @/ y6 W6 n
15.        }
    
16.        return result;
    $ N' x; [) \( H8 ~& I4 k
17.    }
    
18. }

复制代码

& M2 G5 ~1 {! ^( \

秋招将近，华大学长/斯坦福学姐联合组织了一场面向北美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 s4 k0 S6 k% Z: f+ P+ d
5.        }
   
6.        int left = 1, right = (int) 1e7;
   ) M7 P4 O" o7 M" j. V
7.        while (left + 1 < right) {
   
8.            int mid = (left + right) / 2;
   ; C  [3 T( ~% R% O! g, |% R
9.            if (check(dist, hour, mid)) {
   
10.                right = mid;
    
11.            } else {
    - W# L5 Q& Y! n
12.                left = mid;
    
13.            }
    " t1 c/ s' \" m
14.        }
    
15.        return check(dist, hour, left) ? left : right;
    ; D. j, N5 h8 q; O
16.    }
    ; }6 @0 ?+ L; V- w% O6 B& I
17. 
    
18.    private boolean check(int[] dist, double hour, int speed) {
    # q2 @& L" V: c0 J7 |% T! H
19.        int cost = 0;
    
20.        for (int i = 0; i < dist.length - 1; i++) {
    
21.            cost += (dist[i] + speed - 1) / speed;
    ( `. t* P7 v% S0 ^- e6 l
22.        }
    ) y' d, p7 a7 J! }- X. n/ y+ y
23.        return hour >= (double) cost + (1.0 * dist[dist.length - 1] / speed);
    9 X0 {( c& s! c( o$ v# w0 i5 [' W6 a9 S
24.    }
    
25. }

复制代码

No.3 跳跃游戏 VII

解题思路

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

代码展示

1. class Solution {
   
2.    public boolean canReach(String s, int minJump, int maxJump) {
   8 v; i1 d4 F4 D: g! b
3.        int n = s.length();
   
4.        char[] str = s.toCharArray();
   
5.        if (str[n - 1] == '1') {
   
6.            return false;
   
7.        }
   5 K! |3 t! }1 S
8.        LinkedList<Integer> queue = new LinkedList<>();
   , p+ M% M' k$ Y$ O$ S  ~, H9 B; |
9.        queue.add(0);
   
10.        for (int i = 1; i < str.length; i++) {
    
11.            while (!queue.isEmpty() && queue.getFirst() + maxJump < i) {
    ' |  s7 G' C3 A) w, m
12.                queue.pollFirst();
    
13.            }
    
14.            if (!queue.isEmpty() && str[i] == '0' && queue.getFirst() + minJump <= i) {
    ! V" z  x1 N8 I: g
15.                if (i == str.length - 1) {
    
16.                    return true;
    8 T$ u5 Q) M6 C! ~2 l2 `. H1 m$ Z* n
17.                }
    $ B7 u5 E4 k$ R/ ]0 L' O: n: s$ F
18.                queue.add(i);
    : ^* a$ |% W* M# }  `. Y/ l
19.            }
    " I7 Z, F( `( p% X( V! s' e2 Y" {: d
20.        }
    
21.        return false;
    
22.    }
    5 |7 v5 u1 ]+ S6 A
23. }

复制代码

No.4 石子游戏 VIII

解题思路

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

代码展示

1. class Solution {
   ! K8 q& G& S' |6 V
2.    public int stoneGameVIII(int[] stones) {
   ! S& O+ u- p$ P; I3 n
3.        int n = stones.length;
   9 H' t2 i1 i; ?) w! q9 ^
4.        long[] sum = new long[n];
   
5.        sum[0] = stones[0];
   ! G+ F9 z+ ^* n2 T
6.        for (int i = 1; i < n; i++) {
   
7.            sum[i] = sum[i - 1] + stones[i];
   9 ]( T6 p0 q5 o" `2 M
8.        }
   
9.        long[] dp = new long[n];
   
10.        dp[n - 1] = sum[n - 1];
    7 d- B) K1 {' k1 ~4 W
11.        long max = dp[n - 1];
    * H! e1 y; K2 o, L
12.        for (int i = n - 2; i > 0; i--) {
    
13.            dp[i] = sum[i] - max;
    
14.            max = Math.max(max, dp[i]);
    6 T7 g& j6 q  C$ }
15.        }
    
16.        return (int) max;
    * W! S" w0 {; \! o( U1 J
17.    }
    ( d  \7 @, R- v) B) V% D
18. }
    

复制代码