【贪心算法篇】：“贪心”之旅--算法练习题中的智慧与策略（三）

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：贪心算法篇–CSDN博客

在这里插入图片描述

文章目录

前言
例题
- 1.最优除法
- 2.跳跃游戏2
- 3.跳跃游戏1
- 4.加油站
- 5.单调递增的数字
- 6.坏了的计算器

前言

本篇文章是对贪心算法练习题的讲解，有关贪心算法的讲解可以看本系列的第一篇文章，这里就不再讲解，继续讲解相关练习题。

例题

1.最优除法

题目：

在这里插入图片描述

算法原理：

在这里插入图片描述

代码实现：

string optimalDivision(vector<int>& nums){//先处理个数小于等于2的情况if(nums.size()==1){return to_string(nums[0]);}if(nums.size()==2){return to_string(nums[0]) + '/' + to_string(nums[1]);}string ret;//只在第一个数后面加上（，最后一个数后面加上）for (int i = 0; i < nums.size(); i++){ret += to_string(nums[i]);if(i==0){ret += "/(";}else if(i==nums.size()-1){ret += ')';}else{ret += '/';}}return ret;
}

2.跳跃游戏2

题目：

在这里插入图片描述

算法原理：

本道题和下一道题跳跃游戏1的区别就是，本题要求统计最小跳跃次数，有就返回，没有就返回-1；下面图片中讲解本道题的贪心策略。

在这里插入图片描述

代码实现：

int jump(vector<int>& nums){//左指针表示当前位置可以跳的最左位置，也就是跳的最小的步数位置//右指针和maxpos指针表示当前位置可以跳的最右位置，也就是跳的最大的步数位置int left = 0, right = 0, maxpos = 0;int n = nums.size();int ret = 0;//循环条件，当出现左指针大于右指针，结束，表示不能跳到最终位置while(left<=right){//如果maxpos指针的位置大于等于数组的长度，结束if(maxpos>=n-1){return ret;}//从当前左指针位置遍历到右指针位置，更新下一次可以跳到的最右位置for (int i = left; i <= right; i++){maxpos = max(maxpos, nums[i] + i);}//左指针更新为当前右指针的下一个，表示最少跳一步left=right+1;//右指针更新为maxpos指向的位置，表示最多跳的步数right = maxpos;ret++;}return -1;
}

3.跳跃游戏1

题目：

在这里插入图片描述

算法原理：

相较于上一个题，本道题的贪心策略还是相同，只不过最后的返回结果不同，本道题相对简单只需判断能否到达最终位置，能就返回true，不能就返回false。

代码实现：

bool canJump(vector<int>& nums){//和跳跃游戏2相同，只是返回结果不同int left = 0, right = 0, maxpos = 0;int 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;
}

4.加油站

题目：

在这里插入图片描述

算法原理：

本道题其实就是在暴力枚举的基础上利用贪心的思想处理一些没必要的情况，直接看下面图片中的讲解即可。

在这里插入图片描述

代码实现：

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;rest = rest + gas[index] - cost[index];if(rest<0){break;}}if(rest>=0){return i;}//这里是贪心的思想，从小于0的下一个位置开始从新作为起始位置i += step;}return -1;
}

5.单调递增的数字

题目：

在这里插入图片描述

算法原理：

本道题的贪心策略：找到第一个下降的数位，比如123452678中，5的下一个是2，5到2下降，第一个下降的数位就是5，因为只能减小，不能变大，如果把2修改成比5大的，就会导致该数变大，所以只能修改下降数位前面的数字，不能修改下降数位后的数字，5的前面是4，可以将5修改成4，然后后面其余的数全部修改成9，当前就变成123449999，比修改前的小，但是是能修改成的最大的数。

这里就有一个细节点，可能会出现这种情况123442678，第一个下降的数位是4，4的前面还是4，如果修改成1123439999，依然不是递增的，所以，如果下降数位前面有相同的数，要一直向前找，直到找到不同的数修改，这里的正确修改就是123339999，将两个4都修改。

代码实现：

int monotoneIncreasingDigits(int n){//先将数字转化成字符串形式string s = to_string(n);//找到第一个递减的位置int m = s.size();int i = 0;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--;}//第一个相同值-1，其余位置全部修改成9s[i] = s[i] - 1;for (int j = i + 1; j < m; j++){s[j] = '9';}//修改完后转化成数字返回return stoi(s);
}

6.坏了的计算器

题目：

在这里插入图片描述

算法原理：

本道题首先用到的是正难则反思想，正着来是从初始值经过多次减法或者双倍乘法到目标值，而反着来就是从目标值经过多次加法或者二倍除法变成初始值。

因为本道题的数都是正整数，不会出现小数的情况，对于当前数原本有两种情况可以选择，一种是加1，一种是除2；而如果是奇数的话，就只能选择加1，因为除2就会出现小数的情况；而如果是偶数的情况两种情况都可以选择，但是这里用到了贪心的思想，优先选择除2，证明：假设当前数是n，如果先经过k次加1，再除2，最后结果就是(n+k)/2，相当于经过（k+1)次；如果先除2就变成n/2，再加上k/2就变成最后结果(n+k)/2，相当于经过2/k+1次，次数较少，所以优先选择除2。

代码实现：

int brokenCalc(int startValue, int target){//正难则反思想，目标值除法或者加法变成初始值int ret = 0;while(target!=startValue){//如果目标值小于初始值，全选加法if(target<startValue){ret += (startValue - target);break;}//如果大于else{//如果目标值是奇数，选加法if(target%2==1){target += 1;}//如果是偶数，优先选除法else{target /= 2;}ret++;}}return ret;
}