LeetCode笔记：Weekly Contest 236 比赛记录
LeetCode笔记：Weekly Contest 236 比赛记录
- LeetCode笔记：Weekly Contest 236
- 0. 赛后总结
- 1. 题目一
- 1. 解题思路
- 2. 代码实现
- 2. 题目二
- 1. 解题思路
- 2. 代码实现
- 3. 题目三
- 1. 解题思路
- 2. 代码实现
- 4. 题目四
- 1. 解题思路
- 2. 代码实现
0. 赛后总结
中午和本科同学出去聚餐去了，就没有参加比赛，结果下午看了一下题目之后，发现都还算是比较简单的题目，如果这次参加了比赛的话大概率估计能够搞定4题然后拿个不错的名次，可惜了……
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
第一题的解题思路其实就是蛮直接的：
- 首先，考察数组中是否存在0，如果有0则直接返回0；
- 考察数组中负数的个数，如果是奇数个就返回-1，反之返回1。
2. 代码实现
给出python代码实现如下：
class Solution:
def arraySign(self, nums: List[int]) -> int:
cnt = 0
for i in nums:
if i == 0:
return 0
elif i < 0:
cnt += 1
return 1 - 2 * (cnt % 2)提交代码评测得到：耗时60ms，占用内存14.1MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
第二题如果作为一道数学奥赛题我估计就挺难了，不过放在这里，尤其在n不大于500的情况下，我们只需要实际模拟一下游戏的运行过程就可以快速地得到答案了。
2. 代码实现
给出python代码实现如下：
class Solution:
def findTheWinner(self, n: int, k: int) -> int:
arr = [i+1 for i in range(n)]
flag = 0
for _ in range(n-1):
flag = (flag + k-1) % n
arr.pop(flag)
n -= 1
return arr[0]提交代码评测得到：耗时32ms，占用内存14.1MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题的思路其实也还好，就是动态规划，只要考虑一下递推规则就好。
显然，如果某一条道路的下一个位置上如果没有石头，那么直接往前走即可；如果下一个位置上有石头，那么需要跳转到下一个合法的路径上，即当前位置上没有石头，且下一个位置上也没有石头。
我们再利用缓存机制，就可以快速地给出代码实现了。
2. 代码实现
给出python代码实现如下：
class Solution:
def minSideJumps(self, obstacles: List[int]) -> int:
n = len(obstacles)
@lru_cache(None)
def dp(idx, lane):
while idx+1 < n and obstacles[idx+1] != lane:
idx += 1
if idx == n-1:
return 0 if obstacles[idx] != lane else 1
res = 1 + min([dp(idx, l) for l in [1,2,3] if l != lane and obstacles[idx] != l])
return res
return dp(0, 2)提交代码评测得到：耗时3408ms，占用内存427.7MB。
当然，不使用缓存的方式而是采用基础的动态规划的方法也没啥问题，上述思路也可以快速地做转换，不过这里就不多做展开了，有兴趣的读者可以自行试一下。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题的核心在于如何令计算最小化。
这里可以优化的点有两个：
- 优化最后m个元素的选取过程，使之不需要每次都做一次选取操作；
- 计算mk均值时尽可能减少计算量。
其中，我对于1进行了主要的优化，但是对于第二点事实上没有做太好的优化。
简单来说，我将最后m个元素摘出来组成了一个有序数组，然后每次加入一个元素时通过二分法进行维护这个有序数组。
但是在求和时还是比较直接的每次都是去掉头尾的k个元素进行求和，这部分内容我没有优化，但是感觉还是可以优化的。
但是whatever，代码算是通过了评测，因此就偷懒没继续往下想了，有兴趣的读者可以再往下深入思考一下。
2. 代码实现
给出python代码实现如下：
class MKAverage:
def __init__(self, m: int, k: int):
self.m = m
self.k = k
self.mem = []
self.cache = []
def addElement(self, num: int) -> None:
self.mem.append(num)
bisect.insort(self.cache, num)
if len(self.cache) > self.m:
tgt = self.mem[-self.m-1]
idx = bisect.bisect_left(self.cache, tgt)
self.cache.pop(idx)
def calculateMKAverage(self) -> int:
if len(self.cache) < self.m:
return -1
return sum(self.cache[self.k:self.m-self.k]) // (self.m-2*self.k)提交代码评测得到：耗时624ms，占用内存58MB。