贪心-leetcode100题目总结-c++实现

本文主要是介绍贪心-leetcode100题目总结-c++实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

贪心的题目其实是不好做的，因为贪心只是一个思想，而非一个数据结构或者一个板子，有数据结构的题目反而很多操作都是常规化的
1.买卖股票
使用一次扫描法用于在过程中找到最大值或者最小值用于顺序结题很有效，有点像哈希优化，在扫描这个数组的时候不断更新（用于后面元素对前面元素有覆盖作用的很有效！）

class Solution {
public:int maxProfit(vector<int>& prices) {// 使用一次扫描法 用于在过程中找到最大值或者最小值 用于顺序结题很有效，有点像哈希优化int minP = INT_MAX;int maxP = 0;for (int price : prices) {maxP = max(price - minP, maxP);minP = min(minP, price);}return maxP;}
};

2.跳跃游戏

要看是否可以到达最后的位置，就一直遍历维护一个maxS，从当前位置还最多可以跳几步！

class Solution {
public:bool canJump(vector<int>& nums) {// 跳跃游戏，维护可以跳到的最大位置int len = nums.size();if (len <= 1)return 1;int cur = 0;int maxS = 0;// 从当前位置可以跳的最大步数for (int i = 0; i < len - 1; i++) {// 每次跳了下一步了，就需要maxS-1，而且maxS = max(nums[i], maxS - 1);if (maxS == 0)return false;}return true;}
};

3.跳跃游戏2

本来想用dp的，因为看到“最小步数”
但是注意，贪心针对的也是“最大”或者“最小”的问题！
本题的“贪心”思路是：在不得已跳的时候在跳，每次在跳的时候更新最大可以到达的额范围即可

class Solution {
public:
//希望“最少”的次数，出现“最”,就可能使用贪心方法，dp也是可能得
//不得不跳的时候再跳（也就是步数+1）
//更新maxint jump(vector<int>& nums) {// 遍历一次 表示跳到这个为止最小需要的步数int len = nums.size();int maxS=0;int step=0;
int end=0;for(int i=0;i<len-1;i++){//能跳到的最大位置，维护一个start 一个endmaxS=max(i+nums[i],maxS);if(i==end){end=maxS;step++;}}return step;}
};

4.划分字母区间

其实第一步也是一遍扫描（本题情况也是后面对于前面有覆盖作用），处理出来一个字母最后出现的位置，得到了这个哈希以后就很好做了

class Solution {
public:vector<int> res;vector<int> partitionLabels(string s) {// 哈希的思路int len = s.size();vector<int> myMap(27, 0); // 先初始化for (int i = 0; i < len; i++) {myMap[s[i] - 'a'] =i; // 相当于也是一个valToIndex数组，从前那个后自动取到最后的}int pre = -1;int border = 0;for (int i = 0; i < len; i++) {border = max(border, myMap[s[i] - 'a']); // 当前的border// 如果i到达了最大的边界if (border == i) {res.push_back(i - pre);pre = i; // 更新preborder = 0;}}return res;}
};