【算法】C++贪心算法解题（单调递增数字、坏了的计算器、合并区间）
文章目录
- 前言
- 算法题
- 1.单调递增的数字
- 2.坏了的计算器
- 3.合并区间
前言
关于贪心算法/策略的概念、理解性问题在：
【算法】贪心算法解析：基本概念、策略证明与代码例题演示
算法题
1.单调递增的数字
思路
题目要求：找到 满足单调递增的 <= n的最大数字；
比如：
-
n = 1330, ret = 1229
-
n = 241, ret = 239
-
n = 1001, ret = 0999 -> 999
-
n = 233, ret = 233
- 不难看出来，当n的位数第一次出现递减时，ret 的该位应该降位；
- 但降位之前应该确保n的递减位前面没有值相同的，所以应该先向前检索
则总结出思路：
- 首先找出首个递减的位置：
while(i + 1 < m && s[i] <= s[i+1]) i++; - 随后判断递减位置之前，是否存在连续相同的数：
while(i - 1 >= 0 && s[i] == s[i-1]) i--; - 随后递减位-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++;// n 本身就是递增数if(i + 1 == m) return n;// 如果在首位递减的数 有连续相同的：回推while(i - 1 >= 0 && s[i] == s[i-1]) i--;// 递减位-1，后面全填9s[i]--;for(int j = i + 1; j < m; ++j) s[j] = '9';return stoi(s);}
};
2.坏了的计算器
思路
从 target 回溯到 startValue，以找到最小操作数：
-
回溯操作：
- 如果
target大于startValue：- 如果
target是偶数，将target除以 2。 - 如果
target是奇数，将target加 1（使其变为偶数，以便下一步除以 2）。
- 如果
- 每次操作计数
ret加 1。
- 如果
-
处理剩余部分：
- 当
target小于或等于startValue时，将startValue减去target并加到ret中，这部分是直接的加法操作。
- 当
最终返回 ret 加上 startValue 和 target 之间的差值，即 startValue - target
代码
class Solution {
public:int brokenCalc(int startValue, int target) {// 正难则反：从target -> startValue 的最小操作数int ret = 0;while(target > startValue){if(target % 2 == 0) // 偶数除以2target /= 2;else // 奇数+1target += 1; ret++;}return ret + startValue - target;}
};
3.合并区间
思路
-
排序：
- 按照每个区间的左端点进行排序，以确保处理区间时按顺序考虑它们的重叠情况。
-
初始化：
- 设置初始区间的左端点
left和右端点right为第一个区间的端点。
- 设置初始区间的左端点
-
遍历和合并：
- 从第二个区间开始，遍历所有区间。
- 对于每个区间，检查它的左端点是否小于或等于当前的右端点：
- 如果是，说明区间有重叠，更新右端点为当前区间的右端点和之前右端点中的最大值。
- 如果不是，说明区间不重叠，将当前区间
[left, right]添加到结果中，并更新left和right为当前区间的端点。
-
添加最后一个区间：
- 遍历完成后，将最后的区间
[left, right]添加到结果中。
- 遍历完成后，将最后的区间
代码
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {// 以左端点排序sort(intervals.begin(), intervals.end());// 首区间的左右端点int left = intervals[0][0], right = intervals[0][1];vector<vector<int>> ret;for(int i = 1; i < intervals.size(); ++i){// 并集// 两个区间的左右端点int a = intervals[i][0], b = intervals[i][1];if(a <= right) { // 有重叠right = max(right, b);} else { // 无重叠ret.push_back({left, right});left = a, right = b;}}ret.push_back({left, right}); // 最后一个区间return ret;}
};