【C++刷题】优选算法——贪心第三辑

1. 坏了的计算器
   

int brokenCalc(int startValue, int target) {int step = 0;while (target > startValue) {if (target % 2 == 0) target /= 2;else target += 1;++step;}return step + startValue - target;
}

2. 合并区间
   
   区间问题，先排序

    vector<vector<int>> merge(vector<vector<int>>& intervals) {ranges::sort(intervals, [](vector<int>& left, vector<int>& right){return left[0] < right[0];});vector<vector<int>> ret;vector<int> tmp = intervals[0];for (int i = 1; i < intervals.size(); ++i) {if (intervals[i][0] <= tmp[1]) {tmp[1] = max(tmp[1], intervals[i][1]);} else {ret.push_back(tmp);tmp = intervals[i];}}ret.push_back(tmp);return ret;}

3. 无重叠区间
   

int eraseOverlapIntervals(vector<vector<int>>& intervals) {ranges::sort(intervals);int right = intervals[0][1], count = 0;for (int i = 1; i < intervals.size(); ++i) {if (intervals[i][0] < right) {if (intervals[i][1] < right) {right = intervals[i][1];}++count;} else {right = intervals[i][1];}}return count;
}

4. 用最少数量的箭引爆气球
   

int findMinArrowShots(vector<vector<int>>& points) {ranges::sort(points);int  right = points[0][1], count = 1;for (int i = 1; i < points.size(); ++i) {if (points[i][0] <= right) {right = min(right, points[i][1]);} else {++count;right = points[i][1];}}return count;
}

5. 整数替换
   

// 推荐解法一
class Solution {unordered_map<int, int> memo;
public:int integerReplacement(long long n) {if (memo.count(n)) return memo[n];if (n == 1) {memo[n] = 0;return memo[n];}if (n % 2 == 0) {memo[n] = integerReplacement(n / 2) + 1;return memo[n];} else {memo[n] = min(integerReplacement(n + 1), integerReplacement(n - 1)) + 1;return memo[n];}}
};// 解法二
/*
二进制知识：
偶数：二进制表示的最后一位为 0
奇数：二进制表示的最后一位为 1
除 2 操作：二进制表示统一右移一位
*/
class Solution {
public:int integerReplacement(long long n) {int count = 0;while (n != 1) {if (n % 2 == 0) {n /= 2;++count;} else {if (n == 3) {n = 1;count += 2;}else if (n % 4 == 1) {n -= 1;++count;} else {n += 1;++count;}}}return count;}
};

6. 俄罗斯套娃信封问题
   

class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {ranges::sort(envelopes, [](vector<int>& left, vector<int>& right){return left[0] != right[0] ? left[0] < right[0] : left[1] > right[1];});vector<int> v = { envelopes[0][1] };int n = envelopes.size();for (int i = 1; i < n; ++i) {if (envelopes[i][1] < v.back()) {int left = 0, right = v.size() - 1;while (left < right) {int mid = left + (right - left) / 2;if (v[mid] < envelopes[i][1]) {left = mid + 1;} else {right = mid;}}v[left] = envelopes[i][1];} else if (envelopes[i][1] > v.back()) {v.push_back(envelopes[i][1]);}}return v.size();}
};

7. 可被三整除的最大和
   

class Solution {
public:int maxSumDivThree(vector<int>& nums) {int sum = 0;int min_1 = INT_MAX, sec_1 = INT_MAX, min_2 = INT_MAX, sec_2 = INT_MAX;for (int e : nums) {sum += e;if (e % 3 == 1) {if (e < min_1) {sec_1 = min_1;min_1 = e;} else if (e < sec_1) {sec_1 = e;}} else if (e % 3 == 2) {if (e < min_2) {sec_2 = min_2;min_2 = e;} else if (e < sec_2) {sec_2 = e;}}}if (sum % 3 == 0) {return sum;} else if (sum  % 3 == 1) {if (min_1 !=INT_MAX && sec_2 !=INT_MAX) {return max(sum - min_1, sum - min_2 - sec_2);} else if (min_1 !=INT_MAX) {return sum - min_1;} else {return sum - min_2 - sec_2;}} else {if (min_2 !=INT_MAX && sec_1 !=INT_MAX) {return max(sum - min_2, sum - min_1 - sec_1);} else if (min_2 !=INT_MAX) {return sum - min_2;} else {return sum - min_1 - sec_1;}}}
};

8. 距离相等的条形码
   

class Solution {
public:vector<int> rearrangeBarcodes(vector<int>& barcodes) {ranges::sort(barcodes);int num = barcodes[0], count = 1, left = 0, right = 1;while (right < barcodes.size()) {if (barcodes[right] == barcodes[left]) {++right;} else {if (right - left > count) {count = right - left;num = barcodes[left];}left = right;++right;}}if (right - left > count) {count = right - left;num = barcodes[left];}vector<int> ret(barcodes.size());int i = 0;while (count) {ret[i] = num;--count;i += 2;}for (int j = 0; j < barcodes.size(); ++j) {if (i >= ret.size()) i = 1;if (barcodes[j] != num) {ret[i] = barcodes[j];i += 2;}}return ret;}
};

9. 重构字符串
   

class Solution {
public:string reorganizeString(string s) {ranges::sort(s);char max_c = s[0];int count = 1, left = 0, right = 1;while (right < s.size()) {if (s[right] == s[left]) {++right;} else {if (right - left > count) {count = right - left;max_c = s[left];}left = right;++right;}}if (right - left > count) {count = right - left;max_c = s[left];}if (count > (s.size() + 1) / 2) return "";string ret = s;int i = 0;while (count) {ret[i] = max_c;--count;i += 2;}for (int j = 0; j < s.size(); ++j) {if (i >= ret.size()) i = 1;if (s[j] != max_c) {ret[i] = s[j];i += 2;}}return ret;}
};