leetcode第84场双周赛
2023-04-18 16:29:04 时间
leetcode第84场双周赛
一、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 个数,其中的最小值就是 ⌊ x / k ⌋ lfloor x/k floor ⌊x/k⌋。
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;
}
};
关注博主不迷路,内容持续更新中。
相关文章
- 【Hive】Hive 创建表
- 图解curator如何实现zookeeper分布式锁
- Zookeeper下载、本地模式安装、集群操作
- 解决ZBlog PHP提交评论"名称格式不正确,可能过长或为空"问题
- 看完RabbitMQ了的几种消息模型,我对RabbitMQ有了新的认识
- 解决ZBLOG PHP在PHP7.1出现"operator not supported for strings"问题
- 新注册Name.com域名注册商账户及账户域名过户PUSH教程
- 分布式文件系统fastdfs安装以及python调用
- 记一次解决CodeIgniter框架CKEditor+CKFinder图片上传问题
- 《IntelliJ IDEA 插件开发》第七节:通过Inspection机制,对静态代码安全审查
- 【微服务】Eureka注册中心
- 产品经理9大方法论
- (超详细) Spark环境搭建(Local模式、 StandAlone模式、Spark On Yarn模式)
- 日志可视化方案及Lens-K8S桌面管理平台IDE介绍
- Spark SQL增量查询Hudi表
- failed to authenticate user [elastic] 问题解决
- 微擎添加微信公众号教程 - 获取AppID、AppSecret、启用设置服务器配置
- Linux配置ssh互信
- 解决ECSHOP出现"Deprecated: preg_replace()"报错提示问题
- 解决ECSHOP"Strict Standards: Non-static method cls_image"问题