【贪心算法】（第十四篇）
目录
可被三整除的最⼤和（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;
}
}