贪心算法题

0简介

0.1什么是贪心算法 

贪心算法是用贪婪(鼠目寸光)的角度，找到解决问题的最优解

贪心策略：(从局部最优 --> 整体最优)

1把解决问题的过程分为若干步；

2解决每一个问题时，都选择当前“看上去”最优的解法；

3“希望”得到全局最优解

0.2贪心算法特点

1贪心策略的提出

a.没有任何模板和标准

b.可能每道题的贪心标准是不同的

2贪心策略的正确性

a有可能贪心策略是错误的（例二和例三）

b也就是正确的贪心策略是需要证明的！

0.3证明找零问题 

1柠檬水找零

oj链接：柠檬水找零

class Solution
{
public:bool lemonadeChange(vector<int> &bills){int five = 0, ten = 0;for (auto &bill : bills){if (bill == 5)five++;else if (bill == 10){if (five == 0)return false;elseten++, five--;}else{if (ten == 0){if (five >= 3)five -= 3;elsereturn false;}else{ten--;if (five >= 1)five -= 1;elsereturn false;}}}return true;}
};
//简化版
class Solution
{
public:bool lemonadeChange(vector<int> &bills){int five = 0, ten = 0;for (int i = 0; i < bills.size(); i++){if (bills[i] == 5)five++;else if (bills[i] == 10){five--;ten++;}else{if (ten)ten--, five--;elsefive -= 3;}if (five < 0)return false;}return true;}
};

 

2将数组和减半的最小操作次数 

oj链接：将数组和减半的最少操作次数

class Solution
{
public:int halveArray(vector<int> &nums){priority_queue<double> qe;double sum = 0; // 不能用int！for (auto &num : nums){qe.push(num);sum += num;}int cnt = 0;double aim = sum / 2;while (true){double maxval = qe.top();qe.pop();sum -= maxval;cnt++;maxval /= 2;sum += maxval;if (sum <= aim)return cnt;qe.push(maxval);}}
};class Solution
{
public:int halveArray(vector<int> &nums){priority_queue<double> qe;double sum = 0.0;for (auto &num : nums){qe.push(num);sum += num;}sum /= 2.0;int cnt = 0;while (sum > 0){double t = qe.top() / 2.0;qe.pop();sum -= t;cnt++;qe.push(t);}return cnt;}
};

3最大数 

oj链接：最大数

class Solution
{
public:class cmp{public:bool operator()(const string &s1, const string &s2){return s1 + s2 > s2 + s1;}};string largestNumber(vector<int> &nums){vector<string> str;for (auto &e : nums)str.push_back(to_string(e));sort(str.begin(), str.end(), cmp());string ret;for (auto &e : str)ret += e;if (ret[0] == '0')return "0";return ret;}
};

4摆动序列 

oj链接：摆动序列

 

class Solution
{
public:int left = 0, ret = 0;int wiggleMaxLength(vector<int> &nums){for (int i = 0; i < nums.size() - 1; i++){int right = nums[i + 1] - nums[i];if (right == 0)continue; // 有连续相等的情况if (left * right <= 0)ret++; // left=0 -> 开始处于第一个位置也要加left = right;}return ret + 1; // 加上最后一个位置}
};

5最长递增子序列

oj链接：最长递增子序列

class Solution
{
public:int lengthOfLIS(vector<int> &nums){vector<int> ret;ret.push_back(nums[0]);for (int i = 1; i < nums.size(); i++){int x = nums[i];if (x > ret.back())ret.push_back(x);else{// 二分插入位置int left = 0, right = ret.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (ret[mid] < x)left = mid + 1;elseright = mid;}ret[left] = x;}}return ret.size();}
};

6递增的三元子序列

oj链接：递增的三元子序列

思路：与上题类似！ 

class Solution
{
public:bool increasingTriplet(vector<int> &nums){vector<int> ret;ret.push_back(nums[0]);for (int i = 1; i < nums.size(); i++){int x = nums[i];if (x > ret.back())ret.push_back(x);else{int left = 0, right = ret.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (ret[mid] < x)left = mid + 1;elseright = mid;}ret[left] = x;}}return ret.size() >= 3;}
};

7最长连续递增序列

oj链接：最长连续递增序列

该方法是从暴力解法（两层for循环）优化来的，所以暴力解法对，这个贪心一定对！  

class Solution
{
public:int findLengthOfLCIS(vector<int> &nums){int n = nums.size(), ret = 1;for (int i = 0; i < n; i++){int j = i;while (j + 1 < n && nums[j] < nums[j + 1])j++;ret = max(j - i + 1, ret);i = j;}return ret;}
};

8买卖股票的最佳时机 

 oj链接：买卖股票的最佳时机

该方法是从暴力解法（两层for循环）优化来的，所以暴力解法对，这个贪心一定对！  

class Solution
{
public:int maxProfit(vector<int> &prices){int n = prices.size(), ret = 0;int MinPrice = INT_MAX;for (int i = 0; i < n; i++){int profit = prices[i] - MinPrice;MinPrice = min(MinPrice, prices[i]);ret = max(profit, ret);}return ret;}
};

此题也可以采用 动态规划58道算法题 中的买卖股票的最佳时机Ⅲ的思路来解决~

9买卖股票的最佳时机Ⅱ

 oj链接：买卖股票的最佳时机 II

//双指针
class Solution
{
public:int maxProfit(vector<int> &prices){int n = prices.size(), ret = 0;for (int i = 0; i < n; i++){int j = i;while (j + 1 < n && prices[j] < prices[j + 1])j++;ret += prices[j] - prices[i];i = j;}return ret;}
};//一天一天拆分
class Solution
{
public:int maxProfit(vector<int> &prices){int n = prices.size(), ret = 0;for (int i = 0, right = 0; i < n - 1; i++){right = prices[i + 1] - prices[i];if (right > 0)ret += right;}return ret;}
};

10K次取反后最大化的数组和

oj链接：K 次取反后最大化的数组和

//解法1：原始分类讨论
class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int m = 0, minElem = INT_MAX, n = nums.size();for (auto x : nums) {if (x < 0)m++;minElem = min(minElem, abs(x)); // 求绝对值最⼩的那个数}// 分类讨论int ret = 0;if (m > k) {sort(nums.begin(), nums.end());for (int i = 0; i < k; i++) // 前 k ⼩个负数，变成正数{ret += -nums[i];}for (int i = k; i < n; i++) // 后⾯的数不变{ret += nums[i];}} else {// 把所有的负数变成正数for (auto x : nums)ret += abs(x);if ((k - m) % 2) // 判断是否处理最⼩的正数{ret -= minElem * 2;}}return ret;}
};
//解法2：利用小堆
class Solution
{
public:int largestSumAfterKNegations(vector<int> &nums, int k){priority_queue<int, vector<int>, greater<int>> qe;for (auto &num : nums)qe.push(num);while (k){int tmp = qe.top();qe.pop();tmp = -tmp;qe.push(tmp);k--;}int ret = 0;while (!qe.empty()){ret += qe.top();qe.pop();}return ret;}
};

11按身高排序 

oj链接：按身高排序

// 解法1
class Solution
{
public:vector<string> sortPeople(vector<string> &names, vector<int> &heights){int n = names.size();pair<int, string> pr[n];for (int i = 0; i < n; i++){pr[i].first = heights[i];pr[i].second = names[i];}sort(pr, pr + n, greater());vector<string> ret(n);for (int i = 0; i < n; i++)ret[i] = pr[i].second;return ret;}
};// 解法2
class Solution
{
public:vector<string> sortPeople(vector<string> &names, vector<int> &heights){int n = names.size();map<int, string> hash;for (int i = 0; i < n; i++)hash[heights[i]] = names[i];vector<string> ret;for (auto &[a, b] : hash)ret.push_back(b);reverse(ret.begin(), ret.end());return ret;}
};// 解法3
class Solution
{
public:vector<string> sortPeople(vector<string> &names, vector<int> &heights){int n = names.size();vector<int> index(n);for (int i = 0; i < n; i++)index[i] = i;sort(index.begin(), index.end(), [&](int i, int j){ return heights[i] > heights[j]; });vector<string> ret(n);for (int i = 0; i < n; i++)ret[i] = names[index[i]];return ret;}
};

12优势洗牌

oj链接：优势洗牌

class Solution
{
public:vector<int> advantageCount(vector<int> &nums1, vector<int> &nums2){int n = nums2.size();vector<int> index2(n);for (int i = 0; i < n; i++)index2[i] = i;sort(index2.begin(), index2.end(), [&](int i, int j){ return nums2[i] < nums2[j]; });sort(nums1.begin(), nums1.end());vector<int> ret(n);// 田忌赛马int left = 0, right = n - 1;for (int i = 0; i < n; i++){if (nums1[i] > nums2[index2[left]])ret[index2[left++]] = nums1[i]; // 比你大elseret[index2[right--]] = nums1[i]; // 比你小/相等 取对付你最大的数: nums2[index[right]]}return ret;}
};

13最长回文串

oj链接：最长回文串

class Solution
{
public:int longestPalindrome(string s){unordered_map<char, int> hash;for (auto &a : s)hash[a]++;int ret = 0, tmp = 0;for (auto &[a, b] : hash){// if(b%2==0) ret+=b;// else ret+=b-1;ret += b / 2 * 2;}if (ret < s.size())ret++;return ret;}
};

14增减字符串匹配 

oj链接：增减字符串匹配

class Solution
{
public:vector<int> diStringMatch(string s){vector<int> ret;int l = 0, r = s.size();for (auto &ch : s){if (ch == 'I')ret.push_back(l++);elseret.push_back(r--);}ret.push_back(l /*r*/);return ret;}
};

15分发饼干 

 oj链接：分发饼干

class Solution
{
public:int findContentChildren(vector<int> &g, vector<int> &s){if (s.size() == 0)return 0;sort(g.begin(), g.end());sort(s.begin(), s.end());int i = 0, j = 0;while (i < g.size() && j < s.size()){if (g[i] <= s[j]){i++;j++;}elsej++;}return i;}
};

16最优除法

oj链接：最优除法

class Solution
{
public:string optimalDivision(vector<int> &nums){if (nums.size() == 1){return to_string(nums[0]);}else if (nums.size() == 2){return to_string(nums[0]) + "/" + to_string(nums[1]);}string ret = to_string(nums[0]) + "/(" + to_string(nums[1]);for (int i = 2; i < nums.size(); i++){ret += "/" + to_string(nums[i]);}ret += ")";return ret;}
};

17跳跃游戏Ⅱ

oj链接：跳跃游戏 II

// 解法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] >= i - j)dp[i] = min(dp[i], dp[j] + 1);}}return dp[n - 1];}
};// 解法2
class Solution
{
public:int jump(vector<int> &nums){int n = nums.size();int left = 0, right = 0, ret = 0, maxpos = 0;while (left < n && right < n){if (maxpos >= n - 1)return ret;ret++;for (int i = left; i <= right; i++)maxpos = max(maxpos, nums[i] + i);left = right + 1;right = maxpos;}return ret;}
};

18跳跃游戏 

oj链接：跳跃游戏

与上面的思路一致，只不过在while循环更换判断条件即可！ 

class Solution {
public:bool canJump(vector<int>& nums) {int n=nums.size(),left=0,right=0,maxpos=0;while(left<=right)//如果到不了n-1: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;}
};

19加油站 

 oj链接：加油站

class Solution
{
public:int canCompleteCircuit(vector<int> &gas, vector<int> &cost){int n = gas.size();for (int i = 0; i < n; i++){int pos = 0, cnt = 0;for (; pos < n; pos++){int index = (pos + i) % n;cnt += gas[index] - cost[index];if (cnt < 0)break;}if (cnt >= 0)return i;i = i + pos;}return -1;}
};

20单调递增的数字 

 oj链接：单调递增的数字

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 == m - 1)return n;cout << i << endl;// 回退找相等数的第一个while (i - 1 >= 0 && s[i - 1] == s[i])i--;s[i] -= 1;for (int j = i + 1; j < m; j++)s[j] = '9';return stoi(s);}
};

21坏了的计算器 

oj链接：坏了的计算器

class Solution
{
public:int brokenCalc(int startValue, int target){// 第一种情况//  if(target<=startValue) return startValue-target;// 第二种情况int cnt = 0;while (target > startValue){if (target % 2 != 0)target += 1;elsetarget /= 2;cnt++;}return cnt + startValue - target;}
};

22合并区间

oj链接：合并区间

class Solution
{
public:vector<vector<int>> merge(vector<vector<int>> &intervals){if (intervals.size() == 1)return intervals;sort(intervals.begin(), intervals.end()); // 左端点排序vector<vector<int>> ret;int n = intervals.size(), left = intervals[0][0], right = intervals[0][1];for (int i = 1; i < n; i++){int next_left = intervals[i][0], next_right = intervals[i][1];if (right >= next_left)right = max(right, next_right);else{ret.push_back({left, right});left = next_left;right = next_right;}if (i == n - 1)ret.push_back({left, right}); // 最后一组区间放到ret中}return ret;}
};

23无重叠区间 

oj链接：无重叠区间

class Solution
{
public:int eraseOverlapIntervals(vector<vector<int>> &intervals){if (intervals.size() == 1)return 0;sort(intervals.begin(), intervals.end());int n = intervals.size(), ret = 0, left = intervals[0][0], right = intervals[0][1];for (int i = 1; i < n; i++){int next_left = intervals[i][0], next_right = intervals[i][1];if (right > next_left){ret++;right = min(right, next_right); // 删除最大的right区间}else{left = next_left;right = next_right;}}return ret;}
};

24用最少量的箭引爆气球

oj链接：用最少数量的箭引爆气球

class Solution
{
public:int findMinArrowShots(vector<vector<int>> &points){if (points.size() == 1)return 1;sort(points.begin(), points.end());int left = points[0][0], right = points[0][1];int n = points.size(), ret = 1;for (int i = 1; i < n; i++){int next_left = points[i][0], next_right = points[i][1];if (right >= next_left){// 相交的区间去与下一个比// left=max(left,next_left);right = min(right, next_right);}else{// left=next_left;right = next_right;ret++;}}return ret;}
};

25整数替换

oj链接：整数替换

//解法1
class Solution
{
public:unordered_map<int, int> memo; // 不用vector:存不下int integerReplacement(int n){return MinCount(n);}int MinCount(long long n) // n越界处理{// 记忆化if (memo.count(n))return memo[n];if (n == 1){memo[n] = 0;return memo[n];}int ret = 0;if (n % 2 != 0)ret = min(MinCount(n + 1), MinCount(n - 1)) + 1;elseret = MinCount(n / 2) + 1;// 记忆化memo[n] = ret;return memo[n];}
};//解法2
class Solution
{
public:int integerReplacement(long long n){int ret = 0;while (n != 1){if (n % 2 == 0)n /= 2;else{if (n % 4 == 1 || n == 3)n -= 1;elsen += 1;}ret++;}return ret;}
};

26俄罗斯套娃信封问题

oj链接：俄罗斯套娃信封问题

class Solution
{
public:int maxEnvelopes(vector<vector<int>> &envelopes){int ret = 0, n = envelopes.size();sort(envelopes.begin(), envelopes.end());vector<int> dp(n, 1);for (int i = 0; i < n; i++){for (int j = 0; j < i; j++){if (envelopes[j][1] < envelopes[i][1] && envelopes[j][0] < envelopes[i][0])dp[i] = max(dp[i], dp[j] + 1);}ret = max(ret, dp[i]);}return ret;}
};

class Solution
{
public:int maxEnvelopes(vector<vector<int>> &envelopes){sort(envelopes.begin(), envelopes.end(), [](vector<int> &v1, vector<int> &v2){ return v1[0] == v2[0] ? v1[1] > v2[1] : v1[0] < v2[0]; });// 重排完序后就变成了最长递增子序列的问题(以每个区间的第二个数为基准)vector<int> ret;ret.push_back(envelopes[0][1]);int n = envelopes.size();for (int i = 1; i < n; i++){int t = envelopes[i][1];if (ret.back() < t)ret.push_back(t);else{int left = 0, right = ret.size() - 1;while (left < right){int middle = left + (right - left) / 2;if (ret[middle] >= t)right = middle;elseleft = middle + 1;}ret[left] = t;}}return ret.size();}
};

27可被三整除的最大和

oj链接：可被三整除的最大和

class Solution
{
public:int maxSumDivThree(vector<int> &nums){int sum = 0, ret = 0;for (auto &e : nums)sum += e;if (sum % 3 == 0)return sum;else if (sum % 3 == 1){// 定义y1和y2来求最小值和次小值 注意数据溢出问题int x = 0x3f3f3f3f3f, y1 = 0x3f3f3f3f3f, y2 = 0x3f3f3f3f3f;for (auto &e : nums){if (e % 3 == 1)x = min(x, e);else if (e % 3 == 2){if (e < y1){y2 = y1;y1 = e;}else if (y1 <= e && e <= y2)y2 = e;}}ret = max(sum - x, sum - y1 - y2);}else{int y = 0x3f3f3f3f3f, x1 = 0x3f3f3f3f3f, x2 = 0x3f3f3f3f3f;for (auto &e : nums){if (e % 3 == 1){if (e < x1){x2 = x1;x1 = e;}else if (x1 <= e && e <= x2)x2 = e;}else if (e % 3 == 2)y = min(y, e);}ret = max(sum - y, sum - x1 - x2);}return ret;}
};