文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個下標從 0 開始的二進制字符串 s 和兩個整數(shù) 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

類似題目：
LeetCode 55. 跳躍游戲（貪心）

• 創(chuàng)建訪問標記 vis，并且記錄最遠可達的位置，保證每個位置不重復(fù)訪問，$O(n)$ 時間復(fù)雜度

class Solution { public:bool canReach(string s, int minJump, int maxJump) {if(s.back() == '1')return false;int n = s.size(), end = 0;//最遠可到達的位置 endvector<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;} };

44 ms 15.7 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1871. 跳跃游戏 VII（贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。