You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:
i + minJump <= j <= min(i + maxJump, s.length - 1), ands[j] == '0'.
Return true if you can reach index s.length - 1 in s, or false otherwise.
Example 1:
Input: s = "011010", minJump = 2, maxJump = 3 Output: true Explanation: In the first step, move from index 0 to index 3. In the second step, move from index 3 to index 5.
Example 2:
Input: s = "01101110", minJump = 2, maxJump = 3 Output: false
Constraints:
2 <= s.length <= 105s[i]is either'0'or'1'.s[0] == '0'1 <= minJump <= maxJump < s.length
Solution 1: TreeSet /Dequq + Binary Search
Maintain a set of reachable indices so far, for each ‘0’ index check whether it can be reached from any of the elements in the set.
Time complexity: O(nlogn)
Space complexity: O(n)
C++/set
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua, 296 ms, 59.7MB class Solution { public: bool canReach(string s, int minJump, int maxJump) { if (s.back() != '0') return false; const int n = s.length(); set<int> seen{0}; for (int i = minJump; i < n; ++i) { if (s[i] != '0') continue; while (!seen.empty() && (*seen.begin()) + maxJump < i) seen.erase(seen.begin()); auto it = seen.upper_bound(i - minJump); if (it != seen.begin() && *prev(it) + minJump <= i) seen.insert(i); } return seen.count(n - 1); } }; |
C++/deque
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua, 280 ms, 19MB class Solution { public: bool canReach(string s, int minJump, int maxJump) { if (s.back() != '0') return false; const int n = s.length(); deque<int> seen{0}; for (int i = minJump; i < n; ++i) { if (s[i] != '0') continue; while (!seen.empty() && (seen.front()) + maxJump < i) seen.pop_front(); auto it = upper_bound(begin(seen), end(seen), i - minJump); if (it != seen.begin() && *prev(it) + minJump <= i) seen.push_back(i); } return seen.back() == n - 1; } }; |
Solution 2: Queue
Same idea, we can replace the deque in sol1 with a queue, and only check the smallest element in the queue.
C++/set
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua, 56ms, 19.2MB class Solution { public: bool canReach(string s, int minJump, int maxJump) { if (s.back() != '0') return false; const int n = s.length(); queue<int> q{{0}}; for (int i = minJump; i < n; ++i) { if (s[i] != '0') continue; while (!q.empty() && q.front() + maxJump < i) q.pop(); if (!q.empty() && q.front() + minJump <= i) q.push(i); } return q.back() == n - 1; } }; |
Time complexity: O(n)
Space complexity: O(n)
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment