题目1
跳跃游戏ii
给你一个数组v v[i] 表示从i开始最多能跳几格，求到达n - 1下标的最少次数
思路： 我们设置一个变量right 来维护当前跳跃的范围，endd来维护当前可以到达的最大格子，ans 来记录答案
操作过程如下：
- 每走到一个新的格子 判断当前格子在不在跳跃可达的范围内，如果不行的话 说明需要一次额外的跳跃，此时ans++, right = endd
- 每走到一个新的格子 更新
end = max(end, i + v[i])代码：
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
int ans = 0, right = 0, endd = 0;
for (int i = 0 ; i < n; i++)
{
endd = max(endd, i + v[i]);
if (i == right)
{
if (i == endd)
{
cout << -1;
return;
}
ans++;
right = endd;
}
}题目2
浇水问题：
给你一个数组v 其中 v[i] 表示第i个地方有一个水管 浇水可以覆盖 求使得整个花园都能浇到水的最少水管数目 如果无法完全覆盖，返回－1
思路： 我们先创建一个新的数组right 其中
right[i]表示第i个位置开始 能到达的范围 例如：v[3] = 2那么v[3]可以覆盖 的范围 那么right[1] = max(right[1], 5)
随后，这个问题就跟题目一一模一样了
代码：
int n;
cin >> n;
vector<int>v(n);
for (int i = 0; i < n; i++) cin >> v[i];
vector<int> right(n);
for (int i = 0; i < n; i++) right[i - v[i]] = max(right[i - v[i]], i + v[i]);
int ans = 0, curright = 0, nextright = 0;
for (int i = 0; i < n; i++)
{
nextright = max(nextright, right[i]);
if (i == curright)
{
if (i == nextright)
{
cout << -1;
return;
}
ans++;
curright = nextright;
}
}
cout << ans;