解法：模拟
维护一个map<int, int> hash，hash[i]表示价值为i 的物品的重量之和。由于map是有序的，直接把遍历map的结果作为答案即可。
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;
}
};
解法：枚举
坏数对的数量=所有数对的数量-满足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)。
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;
}
};
解法：模拟
维护一个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。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;
}
};
解法：贪心
从倒数第二个数开始往前考虑。设当前考虑的数为x，它的后一个数为y：
x <= y，根据贪心，我们不应拆分x；x > y,我们需要拆分 x 使得拆分后的最大值不超过 y，且根据贪心，拆分后的最小值要尽量大。根据数学知识，拆的次数越少，且拆得尽量平均才能让最小值尽量大。因此我们对 x 进行 (k - 1) 次拆分把它变成 kk 个数，其中的最小值就是
⌊
x
/
k
⌋
\lfloor x/k \rfloor
⌊x/k⌋。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;
}
};
关注博主不迷路，内容持续更新中。