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

解题思路

签到题。

代码展示

class Solution { 
   public boolean checkZeroOnes(String s) { 
       return check(s, '1') > check(s, '0'); 
   } 

   private int check(String s, char c) { 
       int result = 0, count = 0; 
       for (int i = 0; i < s.length(); i++) { 
           if (s.charAt(i) == c) { 
               count++; 
               result = Math.max(result, count); 
           } else { 
               count = 0; 
           } 
       } 
       return result; 
   } 
}

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

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

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

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

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

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

解题思路

二分答案。

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

代码展示

class Solution { 
   public int minSpeedOnTime(int[] dist, double hour) { 
       if (!check(dist, hour, (int) (1e7 + 1))) { 
           return -1; 
       } 
       int left = 1, right = (int) 1e7; 
       while (left + 1 < right) { 
           int mid = (left + right) / 2; 
           if (check(dist, hour, mid)) { 
               right = mid; 
           } else { 
               left = mid; 
           } 
       } 
       return check(dist, hour, left) ? left : right; 
   } 

   private boolean check(int[] dist, double hour, int speed) { 
       int cost = 0; 
       for (int i = 0; i < dist.length - 1; i++) { 
           cost += (dist[i] + speed - 1) / speed; 
       } 
       return hour >= (double) cost + (1.0 * dist[dist.length - 1] / speed); 
   } 
}

No.3 跳跃游戏 VII

解题思路

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

代码展示

class Solution { 
   public boolean canReach(String s, int minJump, int maxJump) { 
       int n = s.length(); 
       char[] str = s.toCharArray(); 
       if (str[n - 1] == '1') { 
           return false; 
       } 
       LinkedList<Integer> queue = new LinkedList<>(); 
       queue.add(0); 
       for (int i = 1; i < str.length; i++) { 
           while (!queue.isEmpty() && queue.getFirst() + maxJump < i) { 
               queue.pollFirst(); 
           } 
           if (!queue.isEmpty() && str[i] == '0' && queue.getFirst() + minJump <= i) { 
               if (i == str.length - 1) { 
                   return true; 
               } 
               queue.add(i); 
           } 
       } 
       return false; 
   } 
}

No.4 石子游戏 VIII

解题思路

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

代码展示

class Solution { 
   public int stoneGameVIII(int[] stones) { 
       int n = stones.length; 
       long[] sum = new long[n]; 
       sum[0] = stones[0]; 
       for (int i = 1; i < n; i++) { 
           sum[i] = sum[i - 1] + stones[i]; 
       } 
       long[] dp = new long[n]; 
       dp[n - 1] = sum[n - 1]; 
       long max = dp[n - 1]; 
       for (int i = n - 2; i > 0; i--) { 
           dp[i] = sum[i] - max; 
           max = Math.max(max, dp[i]); 
       } 
       return (int) max; 
   } 
}