最少区间覆盖问题

题目

有一个包,若干路由器,包在每个路由器处有一个最大跳的步长,问至少几跳能到达终点。每一个数为正整数。

样例:

[2,3,1,1,1]

输出:

2

解释:

0->1->4

思路1

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int jump(vector<int>& nums) {
int ans = 0, cnt = 0, maxn = 0;
for(int i = 0; i < nums.size() - 1 && i <= cnt; ++i){
if(nums[i] + i > maxn){
maxn = nums[i] + i;
}
if(maxn >= nums.size() - 1){
++ans;
break;
}
if(i == cnt){
if(cnt != maxn){
++ans;
}
cnt = maxn;
}
}
return ans;
}
};

思路2

数组记录,及数组记录当前最优值,类似于筛法求素数。

1
2
3
4
5
6
7
8
9
10
11
12
const int inf = 0x3f3f3f3f;
int solve(vector<int>v){
int len = v.size();
vector<int>dp(len, inf);
dp[0] = 0;
for(int i = 0; i < len && dp[i] != inf; ++i){
for(int j = 1; j <= v[i]; ++j){
dp[j] = min(dp[j], dp[i] + 1);
}
}
return dp[len - 1] != inf ? dp[len - 1] : -1;
}

思路3

排序,下标为左界,值+下标为右值,构成区域块,选最少的块覆盖全部区域,覆盖不了等于到不了终点。左值(右值)排序后右值(左值)贪心比较。

总结

刚拿到该题,以为是做过的题,之前做的是能否到达终点。结果忽略了求最少的步数,写完才发现理解错了。然后就慌了,思路就混乱了。就没有然后了。

还是比较适合笔试题,一个人自在,心里有了包袱就自乱阵脚,好水的题都能出错。


文章结束了,但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!