当前位置:网站首页>[LeetCode84双周赛] [模拟] 6174. 任务调度器 II,[贪心&数学] 6144. 将数组排序的最少替换次数
[LeetCode84双周赛] [模拟] 6174. 任务调度器 II,[贪心&数学] 6144. 将数组排序的最少替换次数
2022-08-09 02:24:00 【哇咔咔负负得正】
LeetCode 6174. 任务调度器 II
https://leetcode.cn/problems/task-scheduler-ii/
这道题一开始我模拟做,超时了,参考别人的题解,发现一些步骤上可以简化的。
版本 1
class Solution {
public:
long long taskSchedulerII(vector<int>& tasks, int space) {
unordered_map<int, long long> hash;
long long ans = 0;
for (auto & x : tasks) {
// 若没有做过同一类型的任务,或者中间间隔天数满足 space,ans 结果加一天
if (hash[x] == 0 || ans - hash[x] > space) {
ans++;
// 否则,将 ans 赋值为上一次同一类型的任务的日子 + space 时间间隔 + 1
} else {
ans = hash[x] + space + 1;
}
// 最后将该类型任务日子变为当前的 ans 的日子
hash[x] = ans;
}
return ans;
}
};
版本 2
class Solution {
public:
long long taskSchedulerII(vector<int>& tasks, int space) {
unordered_map<int, long long> hash;
long long ans = 0;
for (auto & x : tasks) {
ans++; // 完成该任务,天数+1
if (hash[x] != 0) {
ans = max(ans, hash[x] + space + 1); // 看看是否要间隔 space 天
}
hash[x] = ans; // 记录完成任务的时间
}
return ans;
}
};
LeetCode 6144. 将数组排序的最少替换次数
https://leetcode.cn/problems/minimum-replacements-to-sort-the-array/
因为最后的数组要满足递增,所以最后一个不要拆!如果最后一个拆了,前面拆的次数也会变多。
从后往前遍历,维护拆完后的数组中的最小值 minValue
,
若 nums[i] > minValue
,对 nums[i]
进行拆分,怎么拆?
拆出来的最大值 >= minValue
- 拆出来地最小份数 k = ⌈ n u m s [ i ] m i n V a l u e ⌉ \lceil \frac{nums[i]}{minValue} \rceil ⌈minValuenums[i]⌉,拆的次数为
k - 1
- 拆出来的最小值要尽可能地大,这样前面的数拆分也不会太小。其实就是让拆出来的每一份更加均匀,
拆出来的最小值 =
⌊ n u m s [ i ] k ⌋ \lfloor \frac{nums[i]}{k} \rfloor ⌊knums[i]⌋
class Solution:
def minimumReplacement(self, nums: List[int]) -> int:
ans = 0
minValue = nums[-1] # 最后一个不用拆
for x in nums[-2::-1]: # 从倒数第二个开始遍历
if x > minValue:
k = ceil(x / minValue) # 上取整
ans += k - 1
minValue = x // k
else:
minValue = x
return ans
边栏推荐
猜你喜欢
D. Tournament Countdown
9.1-----24. Swap the nodes in the linked list in pairs
力扣刷题记录5.1-----59. 螺旋矩阵 II
Duplicate class com.google.common.util.concurrent.ListenableFuture found in modules
<爆>2022中文版-《海外博士申请指南-材料准备、时间线、套磁、面试及录取》免费分享
MT4 / MQ4L entry to the master of EA tutorial lesson two (2) - - MQL language commonly used function account information commonly used functions
【电商运营】不知道怎么做网站优化?这里有你需要知道的一切!
Likou Brush Question Record 8.1-----206. Reverse linked list
历史最全DL相关书籍、课程、视频、论文、数据集、会议、框架和工具整理分享
数据库设计的总结
随机推荐
gpio子系统和pinctrl子系统(上)
New Swagger3.0 tutorial, OAS3 quick configuration guide, to automate API interface documentation!
高性能 MySQL(十二):分区表
如何最大限度地减少企业受到供应链攻击的风险
Duplicate class com.google.common.util.concurrent.ListenableFuture found in modules
Maya engine modeling
[C language brush questions] Application of fast and slow pointers in linked lists
数仓第一篇:基础架构
使网络安全威胁风险更高和成本更高的五个趋势
The security of the pension insurance?Reliable?
边缘计算的三个关键好处
ROS2错误:不支持OpenGL 1.5 GLRenderSystem:: ci initialiseContext在C: \ \ ws \构建……
17.flink Table Api基础概念讲解
Flume (四) --------- Flume 企业开发案例
JS 实现千分位分隔符
物联网未来:未来五年的预期
Cyclictest 简介 安装 测试
力扣刷题记录3.1-----977. 有序数组的平方
What is the difference between a project manager and a product manager?
Etcd realize large-scale application service management of actual combat