【贪心算法】区间类算法题（整数替换、俄罗斯套娃、重构字符串等、C++）

思路

题目求解将整数 n 转换为 1 的最小操作次数。操作可以是将 n 变为 n/2（当 n 是偶数时）或将 n 增加或减少 1（当 n 是奇数时）：

1. 如果 n 是偶数：直接将 n 除以 2，并增加操作计数 ret。
2. 如果 n 是奇数：
   • 特例：当 n 是 3 时，直接将其变为 1，共需要两次操作。
   • 一般情况：根据 n 的末尾二进制位判断操作：
     • 末尾为 01：n % 4 == 1，则将 n 减 1 并除以 2。
     • 末尾为 11：n % 4 == 3，则将 n 加 1 并除以 2。

代码

class Solution {
public:int integerReplacement(int n) {// 贪心int ret = 0;while(n > 1){if(n % 2 == 0){n /= 2;++ret;}else{// 以二进制进行分析if(n == 3){ret += 2;n = 1;} else if (n % 4 == 1) { // ....01n = (n - 1) / 2;ret += 2;} else { // ...11n = n / 2 + 1;ret += 2;}}    }return ret;}
};

思路

题目要求解“俄罗斯套娃信封”问题，即找出能在彼此中嵌套的最大信封数目。核心思路是：贪心 + 二分

1. 排序：首先对信封按左端点升序排序，如果左端点相同，则按右端点降序排序。这确保了左端点相同的信封不会嵌套。

2. 贪心 + 二分搜索：

   • 使用一个动态数组 ret 来存储当前有效的信封序列的右端点。
   • 遍历每个信封的右端点 b：
     • 如果 b 大于 ret 的最后一个元素，表示可以将 b 追加到 ret 的末尾。
     • 否则，使用二分搜索在 ret 中找到第一个不小于 b 的位置，并替换该位置的值，以维持 ret 的非递减顺序。

3. 返回结果：ret 的大小即为最大嵌套信封的数目。

这个算法的时间复杂度为 O(n log n)，其中 n 是信封的数量。

class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {sort(envelopes.begin(), envelopes.end(), [&](const vector<int>& v1, const vector<int>& v2){// 左端点不同，则按左端点排序; 左端点相同，则按右端点排序降序return v1[0] != v2[0] ? v1[0] < v2[0] : v1[1] > v2[1];});// 贪心 + 二分优化vector<int> ret;ret.push_back(envelopes[0][1]);for(int i = 1; i < envelopes.size(); ++i){int b = envelopes[i][1];if(b > ret.back()){ret.push_back(b);}else{// 二分: 到第一个大于或等于当前元素的位置int left = 0, right = ret.size() - 1;while(left < right){int mid = (left + right) >> 1;if(ret[mid] >= b) right = mid;else left = mid + 1;}ret[left] = b;}}return ret.size();}
};

思路

题目要求计算一个数组 nums 中的最大和，使其能被3整除。具体步骤如下：

1. 初始化变量：sum 记录数组总和，x1, x2 分别记录 %3 == 1 的最小和次小数，y1, y2 记录 %3 == 2 的最小和次小数。

2. 遍历数组：累加 sum，同时更新 x1, x2, y1, y2 记录对应的最小值。

3. 分类讨论：

   • 如果 sum % 3 == 0，则 sum 已经可以被3整除，直接返回。
   • 如果 sum % 3 == 1，考虑去掉 %3 == 1 的最小值或去掉 %3 == 2 的最小两个值（以保证总和能被3整除），取两者的最大值。
   • 如果 sum % 3 == 2，类似地，考虑去掉 %3 == 2 的最小值或去掉 %3 == 1 的最小两个值，取两者的最大值。

4. 返回结果：如果没有满足条件的结果，返回 -1。

代码

class Solution {
public:int maxSumDivThree(vector<int>& nums) {const int INF = 0x3f3f3f3f;// x1,x2: 标记%3==1的数 的最小与次小数// y1,y2: 标记%3==2的数 的最小与次小数int sum = 0, x1 = INF, x2 = INF, y1 = INF, y2 = INF;for(auto num : nums){sum += num;if(num % 3 == 1){if(num < x1) x2 = x1, x1 = num;else if(num < x2) x2 = num;}else if (num % 3 == 2){if(num < y1) y2 = y1, y1 = num;else if(num < y2) y2 = num;}}// 分类讨论if(sum % 3 == 0) return sum;else if (sum % 3 == 1) return max(sum - x1, sum - y1 - y2);// else return max(sum - y1, sum - x1 - x2); else if (sum % 3 == 2) return max(sum - y1, sum - x1 - x2); return -1;}
};

思路

题目要求重新排列 barcodes 中的元素，使得相同元素不相邻。下面是代码的步骤：

1. 统计元素频率：使用 unordered_map 记录每个元素的出现次数，并找到出现次数最多的元素 maxVal 和其出现次数 maxCount。

2. 插入最多的元素：在结果向量 ret 的偶数位置（0, 2, 4, ...）中填充最多出现的元素 maxVal。

3. 插入其余元素：将其他元素插入到结果向量中，首先填充偶数位置后，如果偶数位置已满，则从奇数位置开始填充。

4. 返回结果向量：生成的向量符合要求，即相同元素不相邻。

代码

class Solution {
public:vector<int> rearrangeBarcodes(vector<int>& barcodes) {unordered_map<int, int> hash; // 用于记录出现次数最多的那个数int maxVal = 0, maxCount = 0;for(auto x : barcodes){if(maxCount < ++hash[x])maxVal = x, maxCount = hash[x];}// 插入出现次数最多的那个元素maxValvector<int> ret(barcodes.size());int index = 0;for(int i = 0; i < maxCount; ++i){ret[index] = maxVal;index += 2;}// 插入其余元素hash.erase(maxVal);for(auto [a, b] : hash){// 根据每一位的次数插入for(int i = 0; i < b; ++i){// 超出数组范围后从奇数开始插入元素if(index >= barcodes.size()) index = 1;ret[index] = a;index += 2;}}return ret;}
};

思路

题目要求重排字符串 s，使得相同字符不相邻。代码步骤如下：

1. 统计字符频率：使用 unordered_map 记录每个字符的出现次数，并找出出现次数最多的字符 maxCh 和其出现次数 maxCount。

2. 检查可重排性：如果 maxCount 超过 (n + 1) / 2，则无法重排，直接返回空字符串。

3. 填充结果字符串：

   • 处理最多的字符：首先将出现次数最多的字符 maxCh 插入到结果字符串的所有偶数位置（0, 2, 4, ...）。
   • 处理其余字符：将其余字符插入到结果字符串的空闲位置中，先填充偶数位置，如果偶数位置填满，则转到奇数位置。

4. 返回结果字符串：生成的字符串符合要求，确保相同字符不相邻。

代码

class Solution {
public:string reorganizeString(string s) {unordered_map<char, int> hash; // 统计字符以及出现次数// 找出现次数最多的字符char maxCh = ' '; int maxCount = 0, n = s.size();for(auto ch : s){if(maxCount > (n + 1) / 2) return ""; // 不能重构if(maxCount < ++hash[ch]){maxCount = hash[ch];maxCh = ch;}}// 处理出现次数最多的字符int index = 0;string ret(n, ' '); // 结果字符串for(int i = 0; i < maxCount; ++i){// ret.insert(index, 1, maxCh);ret[index] = maxCh;index += 2;}// 处理其余字符hash.erase(maxCh);for(auto [a, b] : hash){// 对每个元素进行次数插入for(int j = 0; j < b; ++j){if(index >= n) index = 1;ret[index] = a;index += 2;}}return ret;}
};