【贪心算法】（第十四篇）
目录
可被三整除的最⼤和（medium）
题目解析
讲解算法原理
编写代码
距离相等的条形码（medium）
题目解析
讲解算法原理
编写代码
可被三整除的最⼤和（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个整数数组 nums ，请你找出并返回能被三整除的元素最⼤和。
⽰例1：
输⼊：nums=[3,6,5,1,8]
输出：18
解释：选出数字3,6,1和8，它们的和是18（可被3整除的最⼤和）。⽰例2：
输⼊：nums=[4]
输出：0
解释：4不能被3整除，所以⽆法选出数字，返回0。⽰例3：
输⼊：nums=[1,2,3,4,4]
输出：12
解释：选出数字1,3,4以及4，它们的和是12（可被3整除的最⼤和）。
提⽰：
◦ 1 <= nums.length <= 4 * 10^4
◦ 1 <= nums[i] <= 10^4
讲解算法原理
解法（正难则反+贪⼼+分类讨论）：
正难则反：
我们可以先把所有的数累加在⼀起，然后根据累加和的结果，贪⼼的删除⼀些数。
分类讨论：
设累加和为 sum ，⽤ x 标记 %3 == 1 的数，⽤ y 标记 % 3 == 2 的数。那么根据 sum 的余数，可以分为下⾯三种情况：
a. sum % 3 == 0 ，此时所有元素的和就是满⾜要求的，那么我们⼀个也不⽤删除；b. sum % 3 == 1 ，此时数组中要么存在⼀个 x ，要么存在两个 y 。因为我们要的是最⼤
值，所以应该选择 x 中最⼩的那么数，记为 x1 ，或者是 y 中最⼩以及次⼩的两个数，记为 y1, y2 。
那么，我们应该选择两种情况下的最⼤值： max(sum - x1, sum - y1 - y2) ；c. sum % 3 == 2 ，此时数组中要么存在⼀个 y ，要么存在两个 x 。因为我们要的是最⼤
值，所以应该选择 y 中最⼩的那么数，记为 y1 ，或者是 x 中最⼩以及次⼩的两个数，记为 x1, x2 。
那么，我们应该选择两种情况下的最⼤值： max(sum - y1, sum - x1 - x2) ；
编写代码
c++算法代码：
class Solution
{
public:int maxSumDivThree(vector<int>& nums) {const int INF = 0x3f3f3f3f;int sum = 0, x1 = INF, x2 = INF, y1 = INF, y2 = INF;for(auto x : nums){sum += x;if(x % 3 == 1){if(x < x1) x2 = x1, x1 = x;else if(x < x2) x2 = x;}else if(x % 3 == 2){if(x < y1) y2 = y1, y1 = x;else if(x < y2) y2 = x;}}// 分类讨论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);}
};java算法代码：
class Solution
{public int maxSumDivThree(int[] nums) {int INF = 0x3f3f3f3f;int sum = 0, x1 = INF, x2 = INF, y1 = INF, y2 = INF;for(int x : nums){sum += x;if(x % 3 == 1){if(x < x1){x2 = x1;x1 = x;}else if(x < x2){x2 = x;}}else if(x % 3 == 2){if(x < y1){y2 = y1;y1 = x;}else if(x < y2){y2 = x;}}}// 分类讨论if(sum % 3 == 0) return sum;else if(sum % 3 == 1) return Math.max(sum - x1, sum - y1 - y2);else return Math.max(sum - y1, sum - x1 - x2);}
}距离相等的条形码（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
在⼀个仓库⾥，有⼀排条形码，其中第 i 个条形码为 barcodes[i] 。
请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。你可以返回任何满⾜该要求的答案，此题保证存在答案。
⽰例1：
输⼊：barcodes=[1,1,1,2,2,2]
输出：[2,1,2,1,2,1]
⽰例2：
输⼊：barcodes=[1,1,1,1,2,2,3,3]
输出：[1,3,1,3,2,1,2,1]
提⽰：
◦ 1 <= barcodes.length <= 10000
◦ 1 <= barcodes[i] <= 10000
讲解算法原理
解法（贪⼼）：
贪⼼策略：
每次处理⼀批相同的数字，往n个空⾥⾯摆放；
每次摆放的时候，隔⼀个格⼦摆放⼀个数；
优先处理出现次数最多的那个数。
编写代码
c++算法代码：
class Solution
{
public:vector<int> rearrangeBarcodes(vector<int>& b) {unordered_map<int, int> hash; // 统计每个数出现的频次 int maxVal = 0, maxCount = 0; for(auto x : b){if(maxCount < ++hash[x]){maxCount = hash[x];maxVal = x;}}int n = b.size();vector<int> ret(n);int index = 0;// 先处理出现次数最多的那个数for(int i = 0; i < maxCount; i++){ret[index] = maxVal;index += 2;}// 处理剩下的数hash.erase(maxVal);for(auto& [x, y] : hash){for(int i = 0; i < y; i++){if(index >= n) index = 1;ret[index] = x;index += 2;}}return ret;}
};java算法代码：
class Solution
{public int[] rearrangeBarcodes(int[] b) {Map<Integer, Integer> hash = new HashMap<>(); // 统计每个数出现了多少次 int maxVal = 0, maxCount = 0;for(int x : b){hash.put(x, hash.getOrDefault(x, 0) + 1);if(maxCount < hash.get(x)){maxVal = x;maxCount = hash.get(x);}}int n = b.length;int[] ret = new int[n];int index = 0;// 先处理出现次数最多的那个数for(int i = 0; i < maxCount; i++){ret[index] = maxVal;index += 2;}hash.remove(maxVal);for(int x : hash.keySet()){for(int i = 0; i < hash.get(x); i++){if(index >= n) index = 1;ret[index] = x;index += 2;}}return ret;}
}