跳跃问题
有一类常见的问题，在河上有n个点，求跳到某个位置所需要的最小步数或者是能否抵达
对于这类问题的解决通常是使用分块，搜索…
1. 求可到达性
Jump Game
1.1 大意
从每个位置能够跳跃的最大格数为这个点的数字，求能否到达最后一个位置
1.2 solve
进行分块，每次的上限被更新为这个块的能够到达的最远距离
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
#define N 1010
int dp[N];
bool canJump(vector<int>& nums) {
int now_pos = 0, next_pos = 0, i = 0;
int n = nums.size();
if (n <= 1) return 1;
while (next_pos - i + 1 > 0) {
for (; i <= now_pos; i++) {
next_pos = max(next_pos, nums[i] + i);
if (next_pos >= n - 1) return 1;
}
now_pos = next_pos;
}
return 0;
}
};
|
2. 求达到的最少步数
Jump Game II
2.1 大意
从这个位置跳到最后一位位置所需要的最少步数，在每个点能够跳跃的步数为这个点对应的数字
2.2 solve
此时我们可以将点按照跳跃的次数进行分块
下一次的结束位置为这一段的最大结束位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int jump(vector<int>& nums) {
int now_max = 0, next_max = 0, level = 0, i = 0;
int n = nums.size();
if (n <= 1) return 0;
while (next_max - i + 1 > 0) {
level ++;
for (; i <= now_max; i++) {
next_max = max(next_max, nums[i] + i);
if (next_max >= n - 1) return level;
}
now_max = next_max;
}
return 0;
}
};
|
3. 求是否可以到达一个特定的点
Jump Game III
3.1 大意
每次可以跳跃的位置是i+arr[i] 和i - arr[i],求是否可以到达val为0的点
3.2 solve
DFS or BFS is ok
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
#define N 51000
queue<int>v;
int vis[N], n;
void push(int x, queue<int>&v) {
if (x < 0 ||x >= n) return;
if (vis[x]) return;
v.push(x);
vis[x] = 1;
}
bool canReach(vector<int>& arr, int start) {
n = arr.size();
push(start, v);
memset(vis, 0, sizeof vis);
while(!v.empty()) {
int i = v.front();
if (arr[i]==0) return 1;
v.pop();
int to1 = i + arr[i];
int to2 = i - arr[i];
push(to1, v);
push(to2, v);
}
return 0;
}
};
|
4. 设置了最小跳跃距离和最大跳跃距离求能否到达最后的点
4.1 大意
在每个点可以跳跃的距离都是在min ~ max之间，且仅当这个点为0的时候才可以进行跳跃
Jump Game vii
4.2 solve
使用前缀和数组进行求解，注意的是此时需要将v[0] = 1, v[1] = -1
后面每次将最小抵达的点+1,最大点+1的位置+1，最终最后一个点>0时成立
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
#define N 100100
bool canReach(string s, int minJump, int maxJump) {
int n = s.size();
if (s.back() != '0') return 0;
vector<int>v(n, 0);
v[0] = 1, v[1] = -1;
for (int i = 0; i < n; i++) {
if (i) v[i] += v[i-1];
if (s[i] == '1') continue;
if (v[i] && i + minJump < n) v[i+minJump]++;
if (v[i] && i + maxJump + 1 < n) v[i+maxJump +1]--;
}
return v.back() > 0;
}
};
|
5. 得到跳跃过程中的最大价值
在这种问题中，我们每次可以走到的位置为min(nowpow+k,n−1)。
Jump game vi
使用deque进行存储，从最后面进行存储，当老人的岁数大于i + k的时候，将其出队，当老人的值小于当前的值时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
#define ll long long
deque<int>dq;
int maxResult(vector<int>& nums, int k) {
ll curr = 0;
for (int i = nums.size() - 1; i >= 0; i--) {
curr = nums[i] + (dq.empty() ? 0: nums[dq.front()]);
while (!dq.empty() && curr > nums[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
if (dq.front() >= i + k) dq.pop_front();
nums[i] = curr;
}
return curr;
}
};
|
