当前位置:网站首页>[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
边栏推荐
- How to install yii2
- 程序员的日常生活 | 每日趣闻
- ROS2 ERROR: OpenGL 1.5 is not supported in GLRenderSystem::initialiseContext at C:\ci\ws\build...
- 概率模型校准
- OJ:L3-021 神坛 伪解 排序后遍历
- Mysql 5.7 into the pit
- 10.1-----19. Delete the Nth node from the bottom of the linked list
- 9.1-----24. Swap the nodes in the linked list in pairs
- What is the difference between a project manager and a product manager?
- 【电商运营】不知道怎么做网站优化?这里有你需要知道的一切!
猜你喜欢
随机推荐
Duplicate class com.google.common.util.concurrent.ListenableFuture found in modules
年金险的安全性怎么样啊?可靠吗?
力扣刷题记录9.1-----24. 两两交换链表中的节点
如何保护智能家居避免黑客攻击
【HNUMSC】C语言第二讲
HCIP-R&S By Wakin自用笔记(3)OSPF之各类LSA及LSA更新规则
力扣刷题记录2.1-----27. 移除元素
C#计算SHA1加密和base64编码
2022 Eye Health Brand Franchise Exhibition, Beijing Vision Care Exhibition, China Ophthalmology Technology Summit
帮助安全红队取得成功的11条建议
JS 将对象拆开拼接成 URL
显著性检验--学习笔记
Open3D 计算点云的均值(质心)与协方差
2022眼康品牌加盟展,北京视力保健展,中国眼科医学技术峰会
Redis系列文章导航
力扣刷题记录10.1-----19. 删除链表的倒数第 N 个结点
ROS2错误:不支持OpenGL 1.5 GLRenderSystem:: ci initialiseContext在C: \ \ ws \构建……
2022/8/8 Competition thinking + state pressure dp
10.1-----19. Delete the Nth node from the bottom of the linked list
YOLOV1详解——Pytorch版