一、6141. 合并相似的物品

1. 题目描述

2. 思路分析

解法：模拟
维护一个map<int, int> hash,hash[i]表示价值为i the sum of the weights of the items.由于map是有序的,traverse directlymapThe result can be used as the answer.

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. 思路分析

解法：枚举
The number of bad pairs=The number of all pairs-满足i < j且 j - i == nums[j] - nums[i]的数对数目.
Shift terms on both sides of the equation,变为nums[i] - i == nums[j] - j.So only one needs to be maintainedunordered_map<int, int> mp,mp[i]Indicates satisfaction so farnums[i] - i == x的i有几个.我们枚举j,and subtract it from the answermp[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]表示类型xThe most recent end time of the task.Enumerates all tasks in order,Set the current task type to x,Elapsed before executing the current taskt的时间,那么：

1. 若t - mp[x] >= space,Indicates that the cooldown time has expired,可以直接执行任务.t += ,并更新mp[x] = t.
2. 若t - mp[x] < space,Indicates that the cooldown time has not expired.根据题意,The earliest executable type at this time x The time of the task is 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. 思路分析

解法：贪心
Think forward from the second-to-last number.Let the number currently under consideration be x,Its last number is y：

1. 若x <= y,根据贪心,We should not splitx;
2. 若x > y,我们需要拆分 x so that the maximum value after splitting does not exceed y,And according to greed,The minimum value after splitting should be as large as possible.根据数学知识,The less the number of dismantling,And split as much as possible to make the minimum value as large as possible.因此我们对 x 进行 (k - 1) The split turns it into kk 个数,The minimum of these is $\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;
    }
};

关注博主不迷路,内容持续更新中.