LeetCode Weekly Contest 243
这是对 LeetCode 第243场周赛的简单讲解和评论。
以下会包括对Leetcode周赛 243的每一题的题解，代码，难度分析，题目类型，以及一些个人对这题的看法等，希望读者们喜欢！
💡注意 ： 题解并不一定都是最优解（代码以pass 了 LeetCode 的 Oline Judge 为准），文章初衷是给读者们提供一定的想法和问题的解决方案
- [Check if Word Equals Summation of Two Words
- Maximum Value after Insertion
- Process Tasks Using Servers
- Minimum Skips to Arrive at Meeting On Time
前言 : 参加Contest 的好处
- 每周抽点时间去练习和学习新的题目这对于个人的编程能力与问题解决能力都有很大的帮助
- 在规定的时间内解决一定的题目，这和真实的OA (Online Assessment) 或者 Onsite 面试是一样的，可以把它当作一个很好的 Mock 练习机会
- 当你有碰到做不出的题目的时候，你能知道自己的弱项在哪里，然后可以根据这进行加强和练习，比赛是一面给自己的镜子
对本场比赛的一些看法
本场比赛难度相对比较正常，都是比较常规的题目，第三题稍微有点难度需要一点思考
1880. 简单的暴力签到题1881. 一道贪心题目1882. 一道用两个Heap的模拟题目，需要进行一点简单的优化1883.比较难的DP 题目
1882 Process Tasks Using Servers
题意：
给你两个数组，一个是servers 一个是tasks。对于tasks[i]，他在 i 的时刻以后才可以被处理，并且处理需要的时间是tasks[i]。我们需要用server 里面weight最小的那个来处理当前的task，如果有多个weight一样的server，用index最小的那个。如果当前没有有空的server，我们就等到有空的时候。并且如果使用一个server去处理当前的task，这个server在tasks[i]+i 的时候才能有空
思路：
- 这题我们可以用两个heap 直接进行模拟
- 第一个heap 里面装的是available server。我们按照他们的weight 排序，如果weight一样，我们按index排序
- 第二个heap 里面装的是正在处理task的server，我们按他们的结束时间从小排序，如果时间到了，我们把它们poll出来加进第一个heap里
- 我们maintain 一个时间variable t表示当前的时间，如果说当前heap1 的size是0，也就是说没有可以处理task的server的话，我们可以把t直接跳到heap2 里面时间最小的那个，那么我们就可以从heap2 里面把用完的server取出来放进heap1里面了
💡代码：
class Solution {
public int[] assignTasks(int[] A, int[] B) {//A:servers B:tasks
int n = A.length, m = B.length;
int res[] = new int[m];
PriorityQueue < int[] > pq1 = new PriorityQueue < > ((a, b) -> { //[weight,index,time]
if (a[0] == b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
}); //available servers
PriorityQueue < int[] > pq2 = new PriorityQueue < > ((a, b) -> {
return a[2] - b[2];
}); //busy server
for (int i = 0; i < A.length; i++) {
pq1.add(new int[] {A[i], i, 0});
}
int t = 0;
for (int i = 0; i < B.length; i++) {
t = Math.max(t, i);//update time
while (pq2.size() > 0 && pq2.peek()[2] <= t) {
pq1.add(pq2.poll());//把完成任务的server加进heap1里面
}
if (pq1.size() == 0) {
t = pq2.peek()[2];//进行时间跳跃，这样就可以把完成任务的server加进heap1里面
while (pq2.size() > 0 && pq2.peek()[2] <= t) {
pq1.add(pq2.poll());
}
}
int p[] = pq1.poll();
res[i] = p[1];
int newt = t + B[i];
pq2.add(new int[] {p[0], p[1], newt});
}
return res;
}
}
空间复杂度和时间复杂度：
- 时间复杂度：O(m log(n))
- 空间复杂度：O(n)
- n ：len(servers) m:len(tasks)
