题目

给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。一开始，你在下标 0 处，且该位置的值一定为 ‘0’ 。当同时满足如下条件时，你可以从下标 i 移动到下标 j 处：

i + minJump <= j <= min(i + maxJump, s.length - 1) 且
s[j] == ‘0’.
如果你可以到达 s 的下标 s.length - 1 处，请你返回 true ，否则返回 false 。

示例 1：

输入：s = “011010”, minJump = 2, maxJump = 3
输出：true

解释：
第一步，从下标 0 移动到下标 3 。
第二步，从下标 3 移动到下标 5 。
示例 2：

输入：s = “01101110”, minJump = 2, maxJump = 3
输出：false

提示：

2 <= s.length <= 10^5
s[i] 要么是 ‘0’ ，要么是 ‘1’
s[0] == ‘0’
1 <= minJump <= maxJump < s.length

思路

普通的动态规划很好想，但是肯定会超时。我们设1871. 跳跃游戏 VII - 图1表示能不能到达1871. 跳跃游戏 VII - 图2位置，1871. 跳跃游戏 VII - 图3

因为对于每个i我们都遍历了1871. 跳跃游戏 VII - 图4个前面的位置，看有没有一个可达的位置，所以超时。一个优化的思路是，我们将1871. 跳跃游戏 VII - 图5由1871. 跳跃游戏 VII - 图6型改为1871. 跳跃游戏 VII - 图7型，使用1871. 跳跃游戏 VII - 图8的好处是只要1871. 跳跃游戏 VII - 图9内有一个1871. 跳跃游戏 VII - 图10值为1871. 跳跃游戏 VII - 图11就好，而这个条件可以用前缀和在1871. 跳跃游戏 VII - 图12#card=math&code=O%281%29&id=YeaB4)时间内求解。因此除了1871. 跳跃游戏 VII - 图13数组在维护一个前缀和数组1871. 跳跃游戏 VII - 图14，判断1871. 跳跃游戏 VII - 图15位置能否到达时，只要判断1871. 跳跃游戏 VII - 图16是否大于1871. 跳跃游戏 VII - 图17即可。

有一些细节要注意，一是1871. 跳跃游戏 VII - 图18和1871. 跳跃游戏 VII - 图19都可能小于1871. 跳跃游戏 VII - 图20，二是下标1871. 跳跃游戏 VII - 图21不同于后面的位置，不需要满足1871. 跳跃游戏 VII - 图22区间和大于1871. 跳跃游戏 VII - 图23，三是1871. 跳跃游戏 VII - 图24数组可以省略，只需要最后到了1871. 跳跃游戏 VII - 图25位置判断一下即可。

代码

dp+前缀和

  1. class Solution {
  2.     public boolean canReach(String s, int minJump, int maxJump) {
  3.         int n = s.length();
  4.         int[] pre = new int[n + 1];
  5.         for (int i = 0; i < n; i++) {
  6.             // pre[i + 1]最少为pre[i]
  7.             pre[i + 1] = pre[i];
  8.             // 只有遇到0才可能到达
  9.             if (s.charAt(i) == '0') {
  10.                 int right = i - minJump;
  11.                 int left = Math.max(i - maxJump, 0);
  12.                 // 区间右边界最小为0，同时区间和大于0，就表示当前位置可达；或者i == 0表示0下标可达
  13.                 if (right >= 0 && pre[right + 1] - pre[left] > 0 || i == 0) {
  14.                     if (i == n - 1) {
  15.                         return true;
  16.                     }
  17.                     // 原来使用了dp数组这里有dp[i] = 1，同时更新pre[i + 1]
  18.                     pre[i + 1]++;
  19.                 }
  20.             }
  21.         }
  22.         return false;
  23.     }
  24. }

有序集合

这道题是当时一场周赛的题目，当时没想到前缀和，用的有序集合，现在回看还觉得自己当时很厉害（其实是现在变菜了…

有序集合题目都是有规律可循的，再比如1871. 跳跃游戏 VII - 图26题，两个题目都是关于两个变量在两个不等式约束下的问题，使用 TreeSet 可以空间换时间，以 1871. 跳跃游戏 VII - 图27#card=math&code=log%28n%29&id=U52SF) 而非1871. 跳跃游戏 VII - 图28#card=math&code=O%28n%29&id=NeH6p)时间查找出满足题意的值。

  1. class Solution {
  2.     public static boolean canReach(String s, int minJump, int maxJump) {
  3.         int n = s.length();
  4.         char[] arr = s.toCharArray();
  5.         // set存储了可以到达的点的下标
  6.         TreeSet<Integer> sortedSet = new TreeSet<>();
  7.         sortedSet.add(0);
  8.         boolean ans = false;
  9.         // 判断i位置是否可达
  10.         for (int i = 0; i < n; i++) {
  11.             if (arr[i] == '1') continue;
  12.             // j+min<=i<=j+max (注意i j和题目中相反 这里j是上一个位置)
  13.             // 上式右边不等式可变形为j>=i-max 因此先找最小的j
  14.             // ------一个小问题------
  15.             // ------为什么要找最小的而不是最大的j呢------
  16.             // ------因为如果找到的小的j都不满足左边不等式 j+min<=i 那么大的一定更不满足了 所以找小的就好了------
  17.             // ------小问题解答结束------
  18.             // 如果找到j 再判断左边不等式是否成立 如果也成立 则说明i可达 并将i加入set中 另外当i==n-1时 就将答案置为true
  19.             // 如果没找到j 说明当前i不可达 看下一个i
  20.             Integer ceil = sortedSet.ceiling(i - maxJump);
  21.             if (ceil != null && ceil + minJump <= i) {
  22.                 if (i == n - 1) ans = true;
  23.                 sortedSet.add(i);
  24.             }
  25.         }
  26.         return ans;
  27.     }
  28. }