做题结果：1882. 使用服务器处理任务
难度中等55
给你两个 下标从 0 开始 的整数数组 servers 和 tasks ，长度分别为 n 和 m 。servers[i] 是第 i 台服务器的 权重 ，而 tasks[j] 是处理第 j 项任务 所需要的时间（单位：秒）。
你正在运行一个仿真系统，在处理完所有任务后，该系统将会关闭。每台服务器只能同时处理一项任务。第 0 项任务在第 0 秒可以开始处理，相应地，第 j 项任务在第 j 秒可以开始处理。处理第 j 项任务时，你需要为它分配一台 权重最小 的空闲服务器。如果存在多台相同权重的空闲服务器，请选择 下标最小 的服务器。如果一台空闲服务器在第 t 秒分配到第 j 项任务，那么在 t + tasks[j] 时它将恢复空闲状态。
如果没有空闲服务器，则必须等待，直到出现一台空闲服务器，并 尽可能早 地处理剩余任务。 如果有多项任务等待分配，则按照 下标递增 的顺序完成分配。
如果同一时刻存在多台空闲服务器，可以同时将多项任务分别分配给它们。
构建长度为 m 的答案数组 ans ，其中 ans[j] 是第 j 项任务分配的服务器的下标。
返回答案数组 ans 。
示例 1：
输入：servers = [3,3,2], tasks = [1,2,3,2,1,2] 输出：[2,2,0,2,1,2] 解释：事件按时间顺序如下： - 0 秒时，第 0 项任务加入到任务队列，使用第 2 台服务器处理到 1 秒。 - 1 秒时，第 2 台服务器空闲，第 1 项任务加入到任务队列，使用第 2 台服务器处理到 3 秒。 - 2 秒时，第 2 项任务加入到任务队列，使用第 0 台服务器处理到 5 秒。 - 3 秒时，第 2 台服务器空闲，第 3 项任务加入到任务队列，使用第 2 台服务器处理到 5 秒。 - 4 秒时，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 5 秒。 - 5 秒时，所有服务器都空闲，第 5 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。示例 2：
输入：servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1] 输出：[1,4,1,4,1,3,2] 解释：事件按时间顺序如下： - 0 秒时，第 0 项任务加入到任务队列，使用第 1 台服务器处理到 2 秒。 - 1 秒时，第 1 项任务加入到任务队列，使用第 4 台服务器处理到 2 秒。 - 2 秒时，第 1 台和第 4 台服务器空闲，第 2 项任务加入到任务队列，使用第 1 台服务器处理到 4 秒。 - 3 秒时，第 3 项任务加入到任务队列，使用第 4 台服务器处理到 7 秒。 - 4 秒时，第 1 台服务器空闲，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 9 秒。 - 5 秒时，第 5 项任务加入到任务队列，使用第 3 台服务器处理到 7 秒。 - 6 秒时，第 6 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。提示：
- servers.length == n
- tasks.length == m
- 1 <= n, m <= 2 * 105
- 1 <= servers[i], tasks[j] <= 2 * 105
失败
原因分析：整体思路正确，大致想到用两个优先队列
1. 一个用于代表未占用服务器
2. 另一个代表已占用服务器
失败原因：1. 未考虑到已占用服务器的释放顺序的其中一个条件：权重，权重小的在同等条件下应该优先释放，在没有空闲服务器时，权重小的应该优先从占用服务器中取出
2. 时间处理问题，全占用时间不应对后续任务处理时间造成影响，这个时间不是互相累加的是并行的
观察其他人代码后，调整如下：
class Solution {
public int[] assignTasks(int[] servers, int[] tasks) {
// [3,3,2]
//[1,2,3,2,1,2]
//1.pq存放服务器编号
//2.最小的拿出来放另一个pq，用于延时，第二个pq栈顶小于当前时间时不出来
//3.如果2不出的情况，1为空，则2出来一个，调时间
int n = servers.length;
int[] release = new int[n];
//就绪服务器
PriorityQueue readyServer = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
if(servers[o1]!=servers[o2]) return servers[o1]-servers[o2];
return o1-o2;
}
});
for(int i = 0; i < n; i++){
readyServer.offer(i);
}
// 占用服务器
PriorityQueue occupyServer = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
if(release[o1]!=release[o2]) return release[o1]-release[o2];
if(servers[o1]!=servers[o2]) return servers[o1]-servers[o2];
return o1-o2;
}
});
int m =tasks.length;
int[] ans = new int[m];
for(int i = 0; i < m; i++){
int task = tasks[i];
while (!occupyServer.isEmpty()&&release[occupyServer.peek()]<=i){
readyServer.add(occupyServer.poll());
}
if(!readyServer.isEmpty()){
int index = readyServer.poll();
release[index] = i+task;
occupyServer.offer(index);
ans[i] = index;
}else{
int releaseIdx = occupyServer.poll();
release[releaseIdx]+=task;
occupyServer.offer(releaseIdx);
ans[i] = releaseIdx;
}
}
return ans;
}
}
做题结果：1865. 找出和为指定值的下标对
难度中等12
给你两个整数数组 nums1 和 nums2 ，请你实现一个支持下述两类查询的数据结构：
- 累加 ，将一个正整数加到 nums2 中指定下标对应元素上。
- 计数 ，统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目（0 <= i < nums1.length 且 0 <= j < nums2.length）。
实现 FindSumPairs 类：
- FindSumPairs(int[] nums1, int[] nums2) 使用整数数组 nums1 和 nums2 初始化 FindSumPairs 对象。
- void add(int index, int val) 将 val 加到 nums2[index] 上，即，执行 nums2[index] += val 。
- int count(int tot) 返回满足 nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。
示例：
输入： ["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"] [[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]] 输出： [null, 8, null, 2, 1, null, null, 11] 解释： FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]); findSumPairs.count(7); // 返回 8 ; 下标对 (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) 满足 2 + 5 = 7 ，下标对 (5,1), (5,5) 满足 3 + 4 = 7 findSumPairs.add(3, 2); // 此时 nums2 = [1,4,5,4,5,4] findSumPairs.count(8); // 返回 2 ；下标对 (5,2), (5,4) 满足 3 + 5 = 8 findSumPairs.count(4); // 返回 1 ；下标对 (5,0) 满足 3 + 1 = 4 findSumPairs.add(0, 1); // 此时 nums2 = [2,4,5,4,5,4] findSumPairs.add(1, 1); // 此时 nums2 = [2,5,5,4,5,4] findSumPairs.count(7); // 返回 11 ；下标对 (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) 满足 2 + 5 = 7 ，下标对 (5,3), (5,5) 满足 3 + 4 = 7提示：
- 1 <= nums1.length <= 1000
- 1 <= nums2.length <= 10^5
- 1 <= nums1[i] <= 10^9
- 1 <= nums2[i] <= 10^5
- 0 <= index < nums2.length
- 1 <= val <= 10^5
- 1 <= tot <= 10^9
- 最多调用 add 和 count 函数各 1000 次
成功
思路：1. nums1 小，查询时复杂度高，用nums2
2. 哈希存储 nums2中的 值->数目 映射
3. add过程修改映射值
class FindSumPairs {
int[] nums1;
Map cnts = new HashMap<>();
int[] nums2;
public FindSumPairs(int[] nums1, int[] nums2) {
this.nums1 = nums1;
this.nums2 = nums2;
for(int num:nums2){
cnts.put(num,cnts.getOrDefault(num,0)+1);
}
}
public void add(int index, int val) {
int cnt = cnts.get(nums2[index]);
if(cnt == 1){
cnts.remove(nums2[index]);
}else{
cnts.put(nums2[index],cnt-1);
}
nums2[index] += val;
cnts.put(nums2[index],cnts.getOrDefault(nums2[index],0)+1);
}
public int count(int tot) {
int ans = 0;
for(int num:nums1){
ans += cnts.getOrDefault(tot-num,0);
}
return ans;
}
}
评论点赞收藏✨关注，是送给作者最好的礼物，愿我们共同学习，一起进步
如果对作者发布的内容感兴趣，可点击下方关注公众号 钰娘娘知识汇总 查看更多作者文章哦！
