LeetCode 1871. 跳跃游戏 VII（贪心）

Michael阿明

发布于 2021-09-06 03:05:06

19100

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录

- 1. 题目
- 2. 解题

1. 题目

给你一个下标从 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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/jump-game-vii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

LeetCode 55. 跳跃游戏（贪心）

创建访问标记 vis，并且记录最远可达的位置，保证每个位置不重复访问，O(n) 时间复杂度

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        if(s.back() == '1')
            return false;
        int n = s.size(), end = 0;//最远可到达的位置 end
        vector<bool> vis(n, false);
        vis[0] = true;
        for(int i = 0; i < n && i <= end; i++)
        {
            if(!vis[i]) continue;
            int p1 = i+minJump;
            int p2 = min(n-1, i+maxJump);
            for(int j = max(p1, end+1); j <= p2; ++j)//max保证每个位置只检查1次
            {
                if(s[j] == '0')
                {
                    vis[j] = true;
                    if(j == n-1)//走到最后了
                        return true;
                }
            }
            end = p2;//更新end位置
        }
        return false;
    }
};