LeetCode笔记：Biweekly Contest 86
LeetCode笔记：Biweekly Contest 86
0. 赛后总结
好久没有打比赛了，昨天兴致所至重新去打了一下比赛，惊讶地发现我居然还能够拿到国内238，全球777的排名，还是在我最后一题一开始看错题目的前提下，也算是多少有点小开心了。
不过毕竟昨晚的题目简单，后面还需要再接再厉就是了。
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题其实就是考虑所有连续两个元素的和，看看有没有重复就行了。
2. 代码实现
给出python代码实现如下：
class Solution:
def findSubarrays(self, nums: List[int]) -> bool:
n = len(nums)
seen = set()
for i in range(n-1):
s = nums[i] + nums[i+1]
if s in seen:
return True
seen.add(s)
return False提交代码评测得到：耗时38ms，占用内存13.8MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题蛮有意思的，因为想到了那就是直接写答案的东西，想不到就要绕圈子了，还不一定能搞定。
说白了，对于任何一个大于3的数n，考察n-2进制下的结果就一定是12，因此必然不可能是严格的回文，故我们只需要直接返回False即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def isStrictlyPalindromic(self, n: int) -> bool:
return False提交代码评测得到：耗时26ms，占用内存13.9MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题由于m,n的范围都不会大于12，因此，遍历每一列被block与不被block的情况也就是2^{12} 种情况，即4096种情况，更何况cols参数的限制还会帮我们进行一定的剪枝，因此，我们只需要使用一个遍历即可对获得最终的结果。
思路上来说，我们考察每一种符合条件的情况下没有被block的行的数目，然后取出其中的最小值即可反向求得被block的最大值。
2. 代码实现
给出python代码实现如下：
class Solution:
def maximumRows(self, mat: List[List[int]], cols: int) -> int:
n, m = len(mat), len(mat[0])
cache = defaultdict(set)
for i in range(n):
for j in range(m):
if mat[i][j] == 1:
cache[j].add(i)
def dfs(idx, unblock, cnt):
if idx >= m:
return n - len(unblock)
elif cnt == 0:
return dfs(idx+1, unblock | cache[idx], cnt)
else:
return max(
dfs(idx+1, unblock | cache[idx], cnt),
dfs(idx+1, unblock, cnt-1)
)
return dfs(0, set(), cols)提交代码评测得到：耗时60ms，占用内存14MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题一开始看错题目了，题目上要求是连续的，因此事实上我们只需要维护一个滑动窗口即可。
然后剩下的问题就是怎么快速的得到max(chargeTimes)和sum(runningCosts)这两个值，后者可以通过一个累积累积数组快速求得，而前者我们可以维护一个有序数组，然后不断地加入新加入的元素以及弹出超过时间窗口的元素即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
res = 0
ctimes, rcost, k = [], 0, 0
for idx, (ct, rc) in enumerate(zip(chargeTimes, runningCosts)):
bisect.insort(ctimes, ct)
rcost += rc
k += 1
s = ctimes[-1] + k * rcost
while k > 0 and ctimes[-1] + k * rcost > budget:
k -= 1
rct = chargeTimes[idx-k]
ctimes.pop(bisect.bisect_left(ctimes, rct))
rcost -= runningCosts[idx-k]
res = max(res, k)
return res提交代码评测得到：耗时4500ms，占用内存22.1MB。