从最小/最大开始贪心
3074. 重新分装苹果
给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。 一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。 请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的 最小 数量。 注意，同一个包裹中的苹果可以分装到不同的箱子中。
int minimumBoxes(vector<int>& apple, vector<int>& capacity)
{
int sum = reduce(apple.begin(), apple.end());
ranges::sort(capacity, greater());
int result = 0;
while(sum > 0)
{
sum -= capacity[result++];
}
return result;
}
2279. 装满石头的背包的最大数量
现有编号从 0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，石头可以往 任意 背包中放置。
请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的 最大 数量。
示例 1：
输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
输出：3
解释：
1 块石头放入背包 0 ，1 块石头放入背包 1 。
每个背包中的石头总数是 [2,3,4,4] 。
背包 0 、背包 1 和 背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。
int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks)
{
vector<int> diff(capacity.size(), 0);
for(int i = 0; i < capacity.size(); i++)
{
diff[i] = capacity[i] - rocks[i];
if(diff[i] < 0) diff[i] = 0;
}
ranges::sort(diff.begin(), diff.end());
int result = 0;
for(int i = 0; i < capacity.size(); i++)
{
if(additionalRocks <= 0) break;
if(diff[i] > 0 && additionalRocks >= diff[i])
{
additionalRocks -= diff[i];
result++;
}
else if(diff[i] == 0)
{
result++;
}
}
return result;
}
1833. 雪糕的最大数量
夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。
商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。
注意：Tony 可以按任意顺序购买雪糕。
给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。
你必须使用计数排序解决此问题。
示例 1：
输入：costs = [1,3,2,4,1], coins = 7
输出：4
解释：Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7
class Solution {
public:
int maxIceCream(vector<int>& costs, int coins)
{
vector<int> freq(100001);
for (int& cost : costs)
{
freq[cost]++;
}
int count = 0;
for (int i = 1; i <= 100000; i++)
{
if (coins >= i)
{
int curCount = min(freq[i], coins / i);
count += curCount;
coins -= i * curCount;
}
else
break;
}
return count;
}
};
解释
由于数组 costs 中的元素不会超过 100000，因此可以使用计数排序，将时间复杂度降低到线性。
使用数组 freq 记录数组 costs 中的每个元素出现的次数，其中 freq[i] 表示元素 i 在数组 costs 中出现的次数。仍然使用贪心的思想，买最便宜的雪糕，因此按照下标从小到大的顺序遍历数组 freq，对于每个下标，如果该下标不超过剩余的硬币数，则根据下标值和该下标处的元素值计算价格为该下标的雪糕的可以购买的最大数量，然后将硬币数减去购买当前雪糕的花费，当遇到一个下标超过剩余的硬币数时，结束遍历，此时购买的雪糕数量即为可以购买雪糕的最大数量。
复杂度分析
时间复杂度：O(n+C)，其中 n 是数组 costs 的长度，C 是数组 costs 中的元素的最大可能值，这道题中 C=10^5。
空间复杂度：O(C)，其中 C 是数组 costs 中的元素的最大可能值，这道题中 C=10^5。需要使用 O(C) 的空间记录数组 costs 中的每个元素的次数。
1481. 不同整数的最少数目
给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。
输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。
class Solution {
public:
int findLeastNumOfUniqueInts(vector<int>& arr, int k)
{
int result = 0;
unordered_map<int, int> mp;
for(auto a : arr) mp[a]++;
vector<int> freq;
for(auto [k, v] : mp)
{
freq.push_back(v);
}
sort(freq.begin(), freq.end());
for(int i = 0; i < freq.size(); i++)
{
if(freq[i] == 0) continue;
if(k >= freq[i])
{
k -= freq[i];
result++;
}
}
return freq.size() - result;
}
};
单序列配对
561. 数组拆分
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。
示例 1：
输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4
class Solution {
public:
int arrayPairSum(vector<int>& nums)
{
int result = 0;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i += 2)
{
result += nums[i];
}
return result;
}
};
881. 救生艇
给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回 承载所有人所需的最小船数 。
输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit)
{
sort(people.begin(), people.end());
int result = 0, left = 0, right = people.size() - 1;
while(left <= right)
{
if(people[left] + people[right] > limit)
{
right--;
}
else
{
left++;
right--;
}
result++;
}
return result;
}
};
双序列配对
2449. 使数组相似的最少操作次数
给你两个正整数数组 nums 和 target ，两个数组长度相等。
在一次操作中，你可以选择两个 不同 的下标 i 和 j ，其中 0 <= i, j < nums.length ，并且：
- 令
nums[i] = nums[i] + 2且 - 令
nums[j] = nums[j] - 2。
如果两个数组中每个元素出现的频率相等，我们称两个数组是 相似 的。
请你返回将 nums 变得与 target 相似的最少操作次数。测试数据保证 nums 一定能变得与 target 相似。
输入：nums = [8,12,6], target = [2,14,10]
输出：2
解释：可以用两步操作将 nums 变得与 target 相似：
- 选择 i = 0 和 j = 2 ，nums = [10,12,4] 。
- 选择 i = 1 和 j = 2 ，nums = [10,14,2] 。
2 次操作是最少需要的操作次数。
class Solution {
public:
void f(vector<int> &a)
{
for(int &x : a)
if(x % 2) x = -x;
sort(a.begin(), a.end());
}
long long makeSimilar(vector<int>& nums, vector<int>& target)
{
f(nums);
f(target);
long long ans = 0L;
for(int i = 0; i < nums.size(); i++)
{
ans += abs(nums[i] - target[i]);
}
return ans / 4;
}
};
（1）把两个数组进行初始化：先把所有的奇数变为负数，然后从小到大排序。
（2）遍历：将两个数组中的元素逐个相减，得出绝对值结果，并将结果逐个相加。
（3）将结果除以4，即为最终结果。
826. 安排工作以达到最大收益
你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:
difficulty[i]表示第i个工作的难度，profit[i]表示第i个工作的收益。worker[i]是第i个工人的能力，即该工人只能完成难度小于等于worker[i]的工作。
每个工人 最多 只能安排 一个 工作，但是一个工作可以 完成多次 。
- 举个例子，如果 3 个工人都尝试完成一份报酬为
$1的同样工作，那么总收益为$3。如果一个工人不能完成任何工作，他的收益为$0。
返回 在把工人分配到工作岗位后，我们所能获得的最大利润 。
示例 1：
输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。
class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker)
{
int n = difficulty.size();
vector<pair<int, int>> vec(n);
for(int i = 0; i < n; i++)
{
vec[i] = {difficulty[i], profit[i]};
}
sort(vec.begin(), vec.end());
sort(worker.begin(), worker.end());
int result = 0, curMaxProfit = 0, index = 0;
for(auto w : worker)
{
while(index < n && w >= vec[index].first)
{
curMaxProfit = max(curMaxProfit, vec[index++].second);
}
result += curMaxProfit;
}
return result;
}
};
总结：排序 + 双指针
对于工人来说，只要我能干的，比我强的工人也能干，那么剩下的就是看谁给的收益高了，使用双指针比较即可。
从最左/最右开始贪心
2027. 转换字符串的最少操作次数
给你一个字符串 s ，由 n 个字符组成，每个字符不是 'X' 就是 'O' 。
一次 操作 定义为从 s 中选出 三个连续字符 并将选中的每个字符都转换为 'O' 。注意，如果字符已经是 'O' ，只需要保持 不变 。
返回将 s 中所有字符均转换为 'O' 需要执行的 最少 操作次数。
输入：s = "XXX"
输出：1
解释：XXX -> OOO
一次操作，选中全部 3 个字符，并将它们转换为'O' 。
class Solution {
public:
int minimumMoves(string s)
{
int result = 0;
for(int i = 0; i < s.size();)
{
if(s[i] == 'X')
{
result++;
i += 3;
continue;
}
i++;
}
return result;
}
};
2789. 合并后数组中的最大元素
给你一个下标从 0 开始、由正整数组成的数组 nums 。
你可以在数组上执行下述操作 任意 次：
- 选中一个同时满足
0 <= i < nums.length - 1和nums[i] <= nums[i + 1]的整数i。将元素nums[i + 1]替换为nums[i] + nums[i + 1]，并从数组中删除元素nums[i]。
返回你可以从最终数组中获得的 最大 元素的值。
输入：nums = [2,3,7,9,3]
输出：21
解释：我们可以在数组上执行下述操作：
- 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
- 选中 i = 1 ，得到数组 nums = [5,16,3] 。
- 选中 i = 0 ，得到数组 nums = [21,3] 。
最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。
class Solution {
public:
long long maxArrayValue(vector<int>& nums)
{
long long res = nums.back();
for(int i = nums.size() - 2; i >= 0; i--)
{
res = nums[i] <= res ? nums[i] + res : nums[i];
}
return res;
}
};
总结：从后向前遍历的贪心，依旧是：你能干的我也能干原则。
1529. 最少的后缀翻转次数
给你一个长度为 n 、下标从 0 开始的二进制字符串 target 。你自己有另一个长度为 n 的二进制字符串 s ，最初每一位上都是 0 。你想要让 s 和 target 相等。
在一步操作，你可以选择下标 i（0 <= i < n）并翻转在 闭区间 [i, n - 1] 内的所有位。翻转意味着 '0' 变为 '1' ，而 '1' 变为 '0' 。
返回使 s 与 target 相等需要的最少翻转次数。
输入：target = "10111"
输出：3
解释：最初，s = "00000" 。
选择下标 i = 2: "00000" -> "00111"
选择下标 i = 0: "00111" -> "11000"
选择下标 i = 1: "11000" -> "10111"
要达成目标，需要至少 3 次翻转。
10101 => 5次
class Solution {
public:
int minFlips(string s)
{
s = "0"+s;
int res = 0;
for (int i = 1; i < s.size(); ++i)
if (s[i] != s[i-1]) ++res;
return res;
}
};
脑筋急转弯：
连续的0或1可以看成一个，因为它们只需要一次翻转就可以全部改变
那么只需要把注意力放在不连续的数字上面：
每个数字和前一个数字不一样，则最终结果+1
3228. 将 1 移动到末尾的最大操作次数
给你一个 二进制字符串 s。
你可以对这个字符串执行 任意次 下述操作：
- 选择字符串中的任一下标
i（i + 1 < s.length），该下标满足s[i] == '1'且s[i + 1] == '0'。 - 将字符
s[i]向 右移 直到它到达字符串的末端或另一个'1'。例如，对于s = "010010"，如果我们选择i = 1，结果字符串将会是s = "000110"。
返回你能执行的 最大 操作次数。
示例 1：
输入： s = “1001101”
输出： 4
解释：
可以执行以下操作：
- 选择下标
i = 0。结果字符串为s = "0011101"。 - 选择下标
i = 4。结果字符串为s = "0011011"。 - 选择下标
i = 3。结果字符串为s = "0010111"。 - 选择下标
i = 2。结果字符串为s = "0001111"。
class Solution {
public:
int maxOperations(string s)
{
int ans = 0, cnt1 = 0;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == '1')
cnt1++;
else if (i != 0 && s[i - 1] == '1')
ans += cnt1;
}
return ans;
}
};
WAYNETS.ORG 
Leave a comment