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 题目
1883 Minimum Skips to Arrive at Meeting On Time
题意：
给一个数组dis，dis[i] 表示到达i的距离。现在主人公的要在t 个小时之前到达最后一个地方，并且它的speed是x。对于每一次出发，我们必须要等到整数hour的时候才可以出发。当然我们拥有skip的机会，如果我们skip了的话我们可以不用等到整数hour出发。并且最后的目的地只要我们到达了就行，所以可以把它看成一个自动skip问用最小的skip到达目的地如果不能到达目的地，返回-1Example 1:Input: dist = [1,3,2], speed = 4, hoursBefore = 2Output: 1Explanation:Without skipping any rests, you will arrive in (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 hours.You can skip the first rest to arrive in ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 hours.Note that the second rest is shortened because you finish traveling the second road at an integer hour due to skipping the first rest.Example 2:Input: dist = [7,3,5,5], speed = 2, hoursBefore = 10Output: 2Explanation:Without skipping any rests, you will arrive in (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 hours.You can skip the first and third rest to arrive in ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 hours.Example 3:Input: dist = [7,3,5,5], speed = 1, hoursBefore = 10Output: -1Explanation: It is impossible to arrive at the meeting on time even if you skip all the rests.
思路：
- 我们用dpi 表示如果当前起点是i，用了j个skip 用了的最少时间，那么我们只要枚举dpn-1，如果比t 小的话，我们就直接返回j
- 不少人此题用dp 使用double，但是double对于precision是个玄学问题，所以这里给出了用int的方法
- 我们先把最后一个目的地做特殊处理，因为是自动skip
- 对于当前的目的地，我们有两种选择，skip或者不skip
- 如果skip的话，dpi = dpi-1 + A[i]
- 如果不skip的话，dpi = dpi-1 + A[i]，并且我们要把 dpi promote 到时speed的倍数，这样就保证了我们在整数hour出发并且不需要使用double
💡代码：
class Solution {
public int minSkips(int[] A, int speed, int t) {
int n=A.length;
int dp[][]=new int[A.length-1][A.length];
double last=(A[A.length-1]+0.0)/speed;
if(A.length==1){
if(last<=t)return 0;
else return -1;
}
int sum=0;
for(int i=0;i<A.length-1;i++){//初始化每个点 0 skip的情况
int mod=A[i]%speed;
sum+=A[i];
if(mod!=0){//promote
sum+=(speed-mod);
}
dp[i][0]=sum;
}
dp[0][1]=A[0];//skip第一个点的话
for(int i=1;i<A.length-1;i++){
for(int skip=1;skip<=i+1;skip++){
int mn=Integer.MAX_VALUE;
//not skip
if(skip<=i){
int last1=dp[i-1][skip]+A[i];
int mod=(last1)%speed;
if(mod!=0){
last1+=(speed-mod);
}
mn=Math.min(mn,last1);
}
//skip
int last2=dp[i-1][skip-1];
mn=Math.min(mn,last2+A[i]);
dp[i][skip]=mn;
}
}
for(int i=0;i<=n-1;i++){
//到达dis[n-2] 使用i个skip的最短时间
double a=(dp[n-2][i]+0.0)/speed;
if(a+last<=t){
return i;
}
}
return -1;
}
}
空间复杂度和时间复杂度：
- 时间复杂度：O(n^2)
- 空间复杂度：O(n^2)
