贪心算法题
目录
0简介
0.1什么是贪心算法
编辑
0.2贪心算法特点
0.3证明找零问题
1柠檬水找零
2将数组和减半的最小操作次数
3最大数
4摆动序列
5最长递增子序列
6递增的三元子序列
7最长连续递增序列
8买卖股票的最佳时机
9买卖股票的最佳时机Ⅱ
10K次取反后最大化的数组和
11按身高排序
12优势洗牌
13最长回文串
14增减字符串匹配
15分发饼干
16最优除法
17跳跃游戏Ⅱ
18跳跃游戏
19加油站
20单调递增的数字
21坏了的计算器
22合并区间
编辑23无重叠区间
24用最少量的箭引爆气球
25整数替换
26俄罗斯套娃信封问题
27可被三整除的最大和
28距离相等的条形码
29重构字符串
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;}
};28距离相等的条形码
oj链接：距离相等的条形码
class Solution
{
public:vector<int> rearrangeBarcodes(vector<int> &barcodes){unordered_map<int, int> hash;int CountMax = 0, ValMax = 0;// 拿出出现次数最多的数for (auto &e : barcodes){if (++hash[e] > CountMax){CountMax = hash[e];ValMax = e;}}int n = barcodes.size();vector<int> ret(n);int index = 0;// 先放次数最多的数for (int i = 0; i < CountMax; i++){ret[index] = ValMax;index += 2;}hash.erase(ValMax);// 再把剩下的(一批一批相同的数)放到剩余的index中for (auto &[x, y] : hash){for (int i = 0; i < y; i++){if (index >= n)index = 1;ret[index] = x;index += 2;}}return ret;}
};29重构字符串
oj链接：重构字符串
对上面提出的贪心策略进行巩固~
class Solution
{
public:string reorganizeString(string s){int n = s.size();int arr[26] = {0};for (auto &ch : s)arr[ch - 'a']++;int CountMax = 0;char tmp = 0;for (int i = 0; i < 26; i++){if (CountMax < arr[i]){CountMax = arr[i];tmp = i + 'a';}}if (CountMax > (n + 1) / 2)return "";else{string ret;ret.resize(n);int index = 0;for (int i = 0; i < CountMax; i++){ret[index] = tmp;index += 2;}arr[tmp - 'a'] = 0;for (int i = 0; i < 26; i++){int Count = arr[i];while (Count--){if (index >= n)index = 1;ret[index] = i + 'a';index += 2;}}return ret;}}
};