【贪心算法】day10
📝前言说明：
- 本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分
- 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）贪心策略正确性的 “证明”
- 文章中的理解仅为个人理解。如有错误，感谢纠错
🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀ZEEKLOG主页 愚润泽
你可以点击下方链接，进行其他贪心算法题目的学习
| 点击链接 | 开始学习 |
|---|---|
| 贪心day1 | 贪心day2 |
| 贪心day3 | 贪心day4 |
| 贪心day5 | 贪心day6 |
| 贪心day7 | 贪心day8 |
| 贪心day9 | 贪心day10 |
也可以点击下面连接，学习其他算法
| 点击链接 | 开始学习 |
|---|---|
| 优选专题 | 动态规划 |
| 递归、搜索与回溯 | 贪心算法 |
题单获取→ 【贪心算法】题单汇总
题目
1262. 可被三整除的最大和
题目链接：https://leetcode.cn/problems/greatest-sum-divisible-by-three/description/
优质解
思路：
- 反向思考，先把所有数加起来再删除小数字
- 通过
%3所得的结果，分类讨论
代码：
classSolution{public:intmaxSumDivThree(vector<int>& nums){ ranges::sort(nums);int s = std::accumulate(nums.begin(), nums.end(),0);if(s %3==0)return s; vector<int> a[3];// 用来分别存储 %3 == 1 和 %3 == 2 的数，多开一个方便下标对应for(int x: nums) a[x %3].push_back(x);int ans =0;if(s %3==2)// 删 一个%3==2 或者 两个%3==1（和下面的个数是相对的）swap(a[1], a[2]);if(a[1].size()) ans = s - a[1][0];if(a[2].size()>=2) ans =max(ans, s - a[2][0]- a[2][1]);return ans;}};时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度： O ( n ) O(n) O(n)
1054. 距离相等的条形码
题目链接：https://leetcode.cn/problems/distant-barcodes/description/
优质解
思路：
- 贪心策略：从最多的数开始，摆放，每个一个位置摆放一个数
代码：
classSolution{public: vector<int>rearrangeBarcodes(vector<int>& barcodes){int n = barcodes.size(); unordered_map<int,int> count;for(int x: barcodes)// 统计每个数出现的次数 count[x]++;// 排序 priority_queue<pair<int,int>> heap;for(auto&[x, cx]: count) heap.push({cx, x});// 默认按第一个元素的个数排序，这样可以省的写仿函数比较器// 填写答案 vector<int>ans(n,0);int i =0;// 从单数位置开始放while(heap.size()){auto[cx, x]= heap.top(); heap.pop();for(int j =0; j < cx; j++){if(i >= n) i =1;// 放偶数位置 ans[i]= x; i +=2;}}return ans;}};时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度： O ( n ) O(n) O(n)
767. 重构字符串
题目链接：https://leetcode.cn/problems/reorganize-string/description/
个人解
思路：
- 和上一题方法一样，不过多做了一些处理
屎山代码：
classSolution{public: string reorganizeString(string s){// 当个数最多的字母的个数，大于其他所有字母个数的和，那就无法重新排序int n = s.size(); unordered_map <char,int> count;for(char c:s) count[c]++; priority_queue<pair<int,char>> q;int m =0, sum =0;for(auto[x,cx]: count){ q.push({cx, x}); sum += cx; m =max(m, cx);}if(sum +1< m *2)return"";int i =0; string ans(n,' ');while(q.size()){auto[cx, x]= q.top(); q.pop();for(int j =0; j < cx; j++){if(i >= n) i =1; ans[i]= x; i +=2;}}return ans;}};时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( n ) O(n) O(n)
🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！
