LeetCode笔记：Weekly Contest 237 比赛记录
LeetCode笔记：Weekly Contest 237 比赛记录
0. 赛后总结
久违的参加了一次比赛，结果怎么说呢，一言难尽，4道题算是都做出来了，不过最后一题真的是坑爹，因为完全是一道数学题，如果事先知道他考察的定理那么最后一题的题目就是瞬秒的题目，如果不知道，那么呵呵，goodbye……
我就是卡壳在了最后一题，最后靠着先蒙后证的方式倒是硬生生地猜出了他要考察的定理，要说的话也是蛮有成就感的，但是时间成本上就实在是有点呵呵了，唉……
索性终究是4道题都做出来了，虽然没能挤进国内前5%，但也终究不至于太差，算是中规中矩吧……
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这题就没啥好说的，统计一下出现在给定句子中的所有的字符的数目，然后看一下他是否包含了全部的字母即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def checkIfPangram(self, sentence: str) -> bool:
cnt = [0 for _ in range(26)]
for c in sentence:
cnt[ord(c) - ord('a')] += 1
return all(x > 0 for x in cnt)提交代码评测得到：耗时36ms，占用内存14.3MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题坦率来说作为第二题有点过于简单了，只需要对雪糕按照价格进行排序即可。
然后按照价格从低到高进行购买，知道现金不够时即为可以购买的最多的雪糕的数目。
2. 代码实现
给出python代码实现如下：
class Solution:
def maxIceCream(self, costs: List[int], coins: int) -> int:
costs = sorted(costs)
res = 0
for c in costs:
if c > coins:
break
coins -= c
res += 1
return res提交代码评测得到：耗时712ms，占用内存28.1MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题事实上我觉得就编程而言是这次比赛中最难的一题了，但是整体上如果想清楚了就也还好。
这道题首先需要对所有的task按照入队列时间进行一个排序，表示按照原计划所有序列的发生时间。需要注意的是，当队列为空时入队操作就应该满足发生顺序，因此，我们除了以入队时间作为第一排序条件之外，还需要以持续时间以及原始序列作为第二第三排序条件。
然后，我们需要进行入队列操作，我们每次都维护当前任务的结束时间t，将所有开始时间在t之前的任务都加入到队列当中，然后弹出队列的第一个任务作为下一个需要执行的任务，并更新任务结束时间t。
如题目中所述，此时队列需要按照(duration, index, enqueuetime)进行排序维护。我们采用堆排序队列进行维护。
另外需要注意的是，如果当前队列为空且上一个任务的完成时间t在下一个任务的入队时间之前时，我们需要更新完成时间t到下一个任务的入队时间。不过这部分代码不加也无所谓，因为外部队列的排序已经保证了其执行任务的顺序不会出错，但是处于逻辑上的合理性还是建议加一下特殊处理。
2. 代码实现
给出python代码如下：
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
tasks = sorted([(t, d, idx) for idx, (t, d) in enumerate(tasks)])
n = len(tasks)
q = []
t = 0
idx = 0
res = []
while idx < n:
if q == [] and t < tasks[idx][0]:
t = tasks[idx][0]
while idx < n and t >= tasks[idx][0]:
enqueuetime, duration, index = tasks[idx]
heapq.heappush(q, (duration, index, enqueuetime))
idx += 1
duration, index, enqueuetime = heapq.heappop(q)
res.append(index)
t = max(t, enqueuetime) + duration
while q != []:
duration, index, enqueuetime = heapq.heappop(q)
res.append(index)
t = max(t, enqueuetime) + duration
return res 提交代码评测得到：耗时1936ms，占用内存62.3MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题与其说是一道编程题，不如说是一道数学题，关键就是看你熟不熟悉位操作的数学变换关系了。
这道题要求解的最终解可以写为：
ans = (a[1] & b[1]) ^ (a[1] & b[2]) ^ …… ^ (a[2] & b[1]) ^ (a[2] & b[2]) ^ ……
最暴力的方法就是一个两层循环就能搞定，但是显而易见的时间复杂度必然会爆炸。
因此，一种直观的想法就是这里必然会有一些变换方法能够使得运算简便。
这事实上就是考察了如下定理：
(a & b) ^ (a & c) ^ (a & d) ^ …… = a & (b ^ c ^ d ^ ……)
这个定理的证明事实上也是比较简单的，可以使用数学归纳法进行证明。
显然的，使用枚举法就能够证明：(a & b_1) ^ (a & b_2) = a & (b_1 ^ b_2)。
假设(a & b_1) ^ …… ^ (a & b_n) = a & (b_1 ^ …… ^ b_n)，考察n+1的情况，显然有：
(a & b_1) ^ …… ^ (a & b_n) ^ (a & b_{n+1}) = (a & (b_1 ^ …… ^ b_n)) ^ (a & b_{n+1}) = a & (b_1 ^ …… ^ b_n ^ b_{n+1})，证毕。
因此，我们就可以快速地将求解关系简化至：
ans = (a[1] & (b[1] ^ b[2] ^ ……)) ^ (a[2] & (b[1] ^ b[2] ^ ……)) ^ …… ^ (a[n] & (b[1] ^ b[2] ^ ……))
即：
ans = (a[1] ^ a[2] ^ ……) & (b[1] ^ b[2] ^ ……)
由此，上述题目的代码编写难度就基本变成了一道easy的题目了……
2. 代码实现
给出python代码实现如下：
class Solution:
def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
s1 = 0
for c in arr1:
s1 = s1 ^ c
s2 = 0
for c in arr2:
s2 = s2 ^ c
return s1 & s2提交代码评测得到：耗时908ms，占用内存30.6MB。