本文涉及知识点

C++差分数组

LeetCode1871. 跳跃游戏 VII

给你一个下标从 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⁵
s[i] 要么是 ‘0’ ，要么是 ‘1’
s[0] == ‘0’
1 <= minJump <= maxJump < s.length

差分数组

差分数组的状态表示

N= s.length
diff[i]记录，如果s[i]是0的话，有多个坐标能跳到i。为了避免处理边界。diff.length 等于 N +maxJump+1

差分数组的初始值

diff[0] =1 ，其它全为0

差分的数组的处理过程

cur = ∑ i j : 0 \sum^{j:0}_{i} ∑ij:0​
if(s[i]==‘0’&&cur ){
diff[i+minJump]++;
diff[i+maxJump+1]–
}

差分数组的返回值

(‘0’==s.back())&&(diff[0…N-1]之和)

代码

核心代码

class Solution {
		public:
			bool canReach(string s, int minJump, int maxJump) {
				const int N = s.length();
				vector<int> diff(N + maxJump + 1);
				int cur = 0;
				diff[0]++;
				diff[1]--;
				for (int i = 0; i < N; i++) {
					cur += diff[i];
					if (cur && ('0' == s[i])) {
						diff[i + minJump]++;
						diff[i + maxJump + 1]--;
					}
				}
				return ('0' == s.back()) && cur;
			}
		};

单元测试

string s;
		int minJump,  maxJump;
		TEST_METHOD(TestMethod1)
		{
			s = "011010", minJump = 2, maxJump = 3;
			auto res = Solution().canReach(s, minJump, maxJump);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod2)
		{
			s = "01101110", minJump = 2, maxJump = 3;
			auto res = Solution().canReach(s, minJump, maxJump);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod3)
		{
			s.assign(100'000,'0'), minJump = 2, maxJump = 10000;
			auto res = Solution().canReach(s, minJump, maxJump);
			AssertEx(true, res);
		}