No.1 Which continuous substring is longer

Their thinking

Sign in.

The code shown

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; }}Copy the code

No.2 minimum speed for trains arriving on time

Their thinking

Dichotomy.

When calculating the total commuting time at a given speed, it is recommended to use floating point operation only in the last operation, and to use the upward division of integer type for all other operations.

The code shown

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); }}Copy the code

No.3 Jump Game VII

Their thinking

Similar to sliding Windows, queues are used to maintain a collection of points that can jump to the current point.

The code shown

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; }}Copy the code

No.4 Stone game VIII

Their thinking

It may seem complicated to put back one total stone at a time, but in fact the opposite is true: the stones put back must be taken by the opponent, thus cancelling out his sum.

The code shown

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; }}Copy the code