❤ 作者主页： 欢迎来到我的技术博客😎
❀ 个人介绍：大家好，本人热衷于 Java后端开发，欢迎来交流学习哦！(￣▽￣)~*
🍊 如果文章对您有帮助，记得 关注、 点赞、 收藏、 评论⭐️⭐️⭐️
📣 您的支持将是我创作的动力，让我们一起加油进步吧！！！🎉🎉
@toc
一、6141. 合并相似的物品
1. 题目描述
2. 思路分析
解法：模拟
维护一个map<int, int> hash，hash[i]表示价值为i 的物品的重量之和。由于map是有序的，直接把遍历map的结果作为答案即可。
3. 代码实现
class Solution {
public:
vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
map<int, int> hash;
for (auto& p : items1) hash[p[0]] += p[1];
for (auto& p : items2) hash[p[0]] += p[1];
vector<vector<int>> res;
for (auto& [k, v] : hash)
res.push_back({k, v});
return res;
}
};二、6142. 统计坏数对的数目
1. 题目描述
2. 思路分析
解法：枚举
坏数对的数量=所有数对的数量-满足i < j且 j - i == nums[j] - nums[i]的数对数目。
把等式两边移项，变为nums[i] - i == nums[j] - j。因此只需要维护一个unordered_map<int, int> mp,mp[i]表示目前为止满足nums[i] - i == x的i有几个。我们枚举j，并从答案中减去mp[nums[j] - j]的值即可。
时间复杂度为O(n)。
3. 代码实现
typedef long long LL;
class Solution {
public:
long long countBadPairs(vector<int>& nums) {
int n = nums.size();
LL ans = n * (n - 1ll) / 2;
unordered_map<int, int> mp;
for (int i = 0; i < n; i ++ ) {
int t = nums[i] - i;
ans -= mp[t];
mp[t] ++;
}
return ans;
}
};三、6174. 任务调度器 II
1. 题目描述
2. 思路分析
解法：模拟
维护一个unordered_map<int, int> mp,mp[x]表示类型x的任务最近一次的结束时间。按顺序枚举所有任务，设当前任务类型为x，执行当前任务之前已经经过了t的时间，那么：
- 若
t - mp[x] >= space,说明冷却时间已经结束，可以直接执行任务。t +=，并更新mp[x] = t. - 若
t - mp[x] < space,说明冷却时间还未结束。根据题意，此时最早能执行类型x任务的时间是mp[x] + space + 1。因此，t = mp[x] + space + 1，并更新mp[x] = t。
3. 代码实现
typedef long long LL;
class Solution {
public:
long long taskSchedulerII(vector<int>& tasks, int space) {
int n = tasks.size();
unordered_map<int, LL> mp;
for (int x : tasks) mp[x] = -1e8;
LL ans = 0;
for (int i = 0; i < n; i ++ ) {
LL &last = mp[tasks[i]];
if (ans - last >= space) ans ++, last = ans;
else ans = last + space + 1, last = ans;
}
return ans;
}
};四、6144. 将数组排序的最少替换次数
1. 题目描述
2. 思路分析
解法：贪心
从倒数第二个数开始往前考虑。设当前考虑的数为x，它的后一个数为y：
- 若
x <= y，根据贪心，我们不应拆分x； - 若
x > y,我们需要拆分x使得拆分后的最大值不超过y，且根据贪心，拆分后的最小值要尽量大。根据数学知识，拆的次数越少，且拆得尽量平均才能让最小值尽量大。因此我们对x进行(k - 1)次拆分把它变成 kk 个数，其中的最小值就是$\lfloor x/k \rfloor$。
3. 代码实现
typedef long long LL;
class Solution {
public:
long long minimumReplacement(vector<int>& nums) {
int n = nums.size();
LL res = 0;
for (int i = n - 2, last = nums.back(); i >= 0; i -- ) {
if (nums[i] < last) last = nums[i];
else {
int k = (nums[i] + last - 1) / last;
res += k - 1;
last = nums[i] / k;
}
}
return res;
}
};关注博主不迷路，内容持续更新中。
