贪心算法五
- 1.跳跃游戏 II
- 2.跳跃游戏
- 3.加油站
- 3.单调递增的数字
点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃
1.跳跃游戏 II
题目链接: 45. 跳跃游戏 II
题目分析:
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处。这句话特别重要的地方就是 任意。
下面举个例子,刚开始在0号位置最大跳跃长度是3,可以跳到下标3的位置。
你可以跳转到任意 nums[i + j] 处,这句话意思,nums[i]里面存的3是最大跳跃长度,你可以选择跳3步、跳2步、跳1步。
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
算法原理:
- 贪心(X)
刚开始处于0好位置,这里有一个最大跳跃长度,那每次跳跃的时候就非常贪心的跳最长跳跃长度。但是这种贪心是错的。
2. 动态规划
这个模型无非就是从左往右的一个模型,其实就是动规里面非常常规的线性dp问题。
1.状态表示
dp[i] 表示:从 0 位置开始,到达 i 位置的时候最小跳跃次数
2.状态转移方程
根据最近一步划分情况:
能够到 i 位置的前提是要满足 nums[j] + j >= i,说明能够从 j 位置到达 i 位置,那到达 j 位置的最小跳跃次数 在 加上 从 j 到 i 这一跳跃次,就是到达 i 位置最小跳跃次数,j的位置有很多,因此外面要求dp[i]的最小值。
3.初始化
dp[0] = 0 初始就在0位置,然后要取dp[i]的最小值,因此0位置之后可以初始化 INT_MAX
4.填表顺序
从左往右
5.返回值
dp[i] 表示:从 0 位置开始,到达 i 位置的时候最小跳跃次数,我们要的是到底n-1位置的最小跳跃次数,因此返回dp[n-1]
class Solution {
public:
int jump(vector<int>& nums) {
// 动态规划
int n = nums.size();
vector<int> dp(n, INT_MAX);
dp[0] = 0;
for(int i = 1; i < n; ++i)
for(int j = 0; j < i; ++j)
if(nums[j] + j >= i)
dp[i] = min(dp[i], dp[j] + 1);
return dp[n - 1];
}
};
虽然可以通过,但是实际复杂度是O(N^2)
- 类似于层序遍历的过程
刚开始在2这个位置,此时起跳可以跳到3和1的位置。2这里可以表示第1次起跳的位置,3和1表示第2次起跳的位置。
通过第2次起跳的位置,我们可以得到第3从起跳的位置,然后把重叠的删除,这里其实也有一点小贪心,如果能从第2次的1起跳,那为什么还要从第3次重叠的1起跳呢?跳跃次数更多了。所以只有1和4是第三次起跳的位置。
同理从第3次起跳位置,我们可以得到第4次起跳位置,
你会发现这里类似于层序遍历,每次都能知道起跳的左端点和右端点,然后遍历这一层的时候,又能找到下一层的左端点和右端点。只要发现更新出来下一次起跳位置能够覆盖到n-1位置的时候就停止,因为次数已经可以跳到最后一个位置了
如何实现呢?
我们仅需搞两个指针,left指向当前起跳的左端点,right指向当前起跳的右端点,把这个区间遍历一遍就可以找到下一个起跳区间,其中找左端点很好找就是right + 1,找右端点就是在遍历的过程中,拿着nums[i] + i 找到其中的最大值就是右端点。
在这个遍历过程中,我们仅需遍历一次就行了,所以时间复杂度是O(N)
class Solution {
public:
int jump(vector<int>& nums) {
int left = 0, right = 0, maxPos = 0, ret = 0, n = nums.size();
while(left <= right)// 保险的写法,以防跳不到 n - 1 的位置
{
if(maxPos >= n - 1)// 先判断⼀下是否已经能跳到最后⼀个位置
{
return ret;
}
// 遍历当成层,更新下⼀层的最右端点
for(int i = left; i <= right; ++i)
{
maxPos = max(maxPos, nums[i] + i);
}
left = right + 1;
right = maxPos;
++ret;
}
return -1;// 跳不到的情况
}
};
2.跳跃游戏
题目链接: 55. 跳跃游戏
题目分析:
这道题和上面几乎一模一样,无非上面问的是跳到最后一个位置最小跳跃次数,这道题问的是能否跳到最后一个位置。
算法原理:
完全参考上面的解法3:利用层序遍历的过程
class Solution {
public:
bool canJump(vector<int>& nums) {
int left = 0, right = 0, maxPos = 0, n = nums.size();
while(left <= right)
{
if(maxPos >= n - 1)
{
return true;
}
for(int i = left; i <= right; ++i)
{
maxPos = max(maxPos, nums[i] + i);
}
left = right + 1;
right = maxPos;
}
return false;
}
};
3.加油站
题目链接: 134. 加油站
题目分析:
选择某个加油站为出发点,环绕一周看是否能回到出发点。如果可以就返回对应的下标,不能就返回-1。
初始时油箱是空的,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i],油箱容量是无限的。
假设从3位置出发,刚开始油箱为空,此时可以补充1升汽油,但是需要3升汽油才能到下一个位置。所以这个位置不可以,同理4和5都不可以。
可以从1位置出发 ,从这里可以补充4升汽油,仅需消耗1升就可以到下一个位置,到下一个位置还剩下3升
到2的位置,补充5升,现在共有8升,消耗2升,到下一个位置还有6升
然后补充1升,消耗3升,到下一个位置还剩4,在补充2升,消耗4升,到下一个位置还剩2升,在补充3升,消耗5升,到出发点正好剩下0,可以到达,返回3。
算法原理:
解法一:暴力解法 -> 枚举
首先可以想到一个优化,仅需考虑g和c的差就可以了,比如第一个位置会加1升油,消耗3升油,它们的差就是从这个加油站获得的净收益。如果从负开始走绝对是走不到下一个位置的,所以肯定会选择净收益为正的作为出发点。
我们这道题其实特别像是一道模拟的题,任意枚举一个位置看看从这个位置能不能绕一圈会回来就可以。如果不能就去枚举下一个位置。
所以我们的暴力策略就很简单:
- 依次枚举所有的起点
- 从起点开始,模拟一遍加油的流程即可
虽然策略很简单,但是要注意这里是有环的,所以写代码的时候要考虑如何从最后一个位置回到0位置。
我们的贪心就是根据暴力优化来的,所以先搞定暴力的代码。然后优化的时候仅需加一句代码,就能将时间复杂度从O(N^2)变成O(N)
如何实现暴力的代码?
这里我们主要考虑就是如何从最后一个位置回到第一个位置,其实这里两层for循环就可以搞定,我们创建一个变量step,用这个变量表示从 i 往后走了多少步,step变化是从 0 ~ n - 1。然后 (i + step)% n (数组大小) 就可以从最后一个位置回到第一个位置。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
for(int i = 0; i < n; ++i)// 依次枚举所有的起点
{
int rest = 0;// 标记一下净收益
int step = 0;
for(; step < n; ++step)// 枚举往后走的步数
{
int index = (i + step) % n;// 求出走 step 步之后的下标
rest = rest + gas[index] - cost[index];
if(rest < 0) break;
}
if(rest >= 0) return i;
}
return -1;
}
};
解法二:优化 -> 找规律(贪心)
diff表示g-c的差,我们的暴力解法是依次固定一个位置为起点,从这个起点开始模拟加油流程,其实就是把净收益加一下。
如果发现从a加到f小于0了,说明从f这个位置开始就不能往后走了,所以从a为起来最多能到f这个位置。这里有一个等式。
我们的暴力是枚举下一个起点然后在走。然后我们这里也有个不等式,
我们要想从a走到b,一定是a>=0的,从a加到f < 0,现在第二个不等式又少了a,那更是< 0
同理从c为起点也是越不过f的,a + b >= 0才能到c,等式少了a+b,那更小于0
所以说发现有一个起点点都跑不到某个位置,那中间的都不用在考虑了,不用在枚举了。直接让 i 指针更新到 五角星 后面的一个位置,也就是 i = i + step + 1
我们最差会遍历数组两遍,假设还是以a为起点,发现到h走不到了,下一个位置就是i,最差我们绕回去在遍历一遍再走到h位置,相当于遍历了数组两遍,然后接下来更新 i 的时候 是 i + step + 1 此时就已经越界了。所以最差遍历数组两遍,时间复杂度O(N)
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
for(int i = 0; i < n; ++i)// 依次枚举所有的起点
{
int rest = 0;// 标记一下净收益
int step = 0;
for(; step < n; ++step)// 枚举往后走的步数
{
int index = (i + step) % n;// 求出走 step 步之后的下标
rest = rest + gas[index] - cost[index];
if(rest < 0) break;
}
if(rest >= 0) return i;
i = i + step;//优化
}
return -1;
}
};
3.单调递增的数字
题目链接: 738. 单调递增的数字
题目分析:
算法原理:
解法一:暴力解法 -> 暴力枚举
不是给了我们一个n,然后让找到小于等于n的最大数字,且数字是单调递增的。
所以我们可以从n枚举到0,只要找到数字是单调递增的,就返回。因为我们是从大到小枚举所以这个数一定是小于等于n并且是最大的那个数。
- 从大到小的顺序,枚举 [n,0] 区间内的数字
- 判断数字是否是 “单调递增的”
这里最主要的就是判断一个数是单调递增的。肉眼很好判断,但是让计算机不好判断,这里我们有两个常用方法:
第一种方法:我们遇到有个数字的时候,如果想处理某一位的时候,最常用的方式就是将数字转化为字符串。
比如要找数字中的每一位,如果单看数字1234你很难找每一位,但是我们可以将1234 转化为 “1234”,此时就可以用指针来遍历每一位
class Solution {
public:
int monotoneIncreasingDigits(int n) {
for(int i = n; i >= 0; --i)
{
string nums = to_string(i);
int j = 0, m = nums.size();
for(; j < m - 1; ++j)
{
if(nums[j] > nums[j + 1]) break;
}
if(j == m - 1) return i;
}
return -1;
}
};
第二种方法:% 10 , / 10
prev记录之前%10得到的数字,cur记录/10之后然后当前%10得到的数字。
class Solution {
public:
int monotoneIncreasingDigits(int n) {
for(int i = n; i >= 0; --i)
{
int prev = INT_MAX, cur = 0, num = i;
while(num)
{
cur = num % 10;
if(cur > prev) break;
prev = cur;
num /= 10;
}
if(num == 0) return i;
}
return -1;
}
};
这两种方法都会超时!时间复杂度是O(nlogn),O(logn)表示把数字中的每一位都提取出来时间复杂度是O(logn)
解法二:贪心(找规律)
假设有下面这样一个数,我们观察1-5是递增的,从5后面开始就是递减的。此时第一个贪心,如果前面的数是递增的我们会不会去修改它?肯定不会!修改高位势必会给高位某个数减小,影响太大了。
- 如果高位单调递增的话,我们不去修改
从5之后开始下降,我们最终要想找一个单调递增的话,调整一下后面的数使它从5开始递增并且尽可能的大,但是这个想法是实现不了的,你是会让4变成5,但是整个数相比之前就变大了。所以这个策略不行,调整4367使它从5之后开始递增是实现不了的。原因就是后面数的变化受到5的限制。如何解除这个限制呢?让这个5减小1变成4,然后的数都变成9,绝对是最大递增的。
- 从左往右,找到第一个递减的位置,使其减小1,后面的数全部修改成 9
但是这里还有个问题,比如下面这个数,5是重复的,从左到右扫描到最后一个5的位置,但是执行刚才的策略是让最后一个5减少1,后面数都变成9,但是不行啊,你让最后一个5变成4,这个数就不是一个递增的了。其实我们应该调整第一个5变成4,后面的数都变成9
- 从左往右,找到第一个递减的位置,从这个位置向前推,推到相同区域的最左段使其减小1,后面的数全部修改成 9
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string s = to_string(n);// 把数字转化成字符串
int i = 0, m = s.size();
// 找第⼀个递减的位置
while(i + 1 < m && s[i] <= s[i + 1]) ++i;
if(i + 1 == m) return n;// 判断⼀下特殊情况
// 回推
while(i - 1 >= 0 && s[i] == s[i - 1]) --i;
s[i]--;
for(int j = i + 1; j < m; ++j) s[j] = '9';
return stoi(s);
}
};
证明:
证明方法:反证法
假设贪心解是错误的,那必定会存在一个最优解,证明一下这个最优解是不存在的,那我们的贪心解就是最优的。
这里我们分开讨论,第一种贪心解得到的数和原数个数是匹配的,第二种个数不匹配。
先看第一种情况,假设贪心解不是最优解,那势必会存在一个最优解,最优解是严格大于贪心解并且是严格递增的。其次位数是一样的,贪心解位数都一样,最优解比贪心解大,位数肯定也是一样的。位数一样,从左扫描最优解肯定存在某一位是大于贪心解某一位的。
这里可以分为3个区域,递增区域,让原数减1区域,以及后面的区域。不过如果前两个区域都是一样的话,第三个区域肯定不存在比999还大的。因此我们只考虑前两个区域最优解的某个数大于贪心解
第一块区域,要么大于1、要么大于2、要么大于3,但是都是不存在的,因为这个数是单调递增的,最小的1333333都比原解还大了。
第二块区域,如果中间这个数比贪心解的这个数大最低就是4,但是也是不存在的,最优解也是一个递增的数如果这个是数4,后面即使全是4,最小的是1234444还比原数大,所以也是不存在的。
那后面的区域更别提了,不可能有大于999的数。所以说如果贪心解是错的,根本找不到一个最优解比贪心解大,所以说刚才的假设是错误的,因此我们的贪心解是正确的。
接下来我们看位数减少的情况,我们会发现位数减少的这个数正好是最大的减少位数中的最大数,你想找一个最优解比贪心解还大的情况那必定是6位数,如果是6位数还想保证比原数小,那这个数只能是1111111但是比原数大,因此这个最优解也是不存在的,所以我们的贪心就是最优的。都找不到一个最优解大于贪心解。