LeetCode笔记：Biweekly Contest 42 比赛记录
LeetCode笔记：Biweekly Contest 42 比赛记录
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题要直接写出答案事实上感觉还是不太容易的，所幸学生的数目不会太多，最多也就100，因此，我们直接按照题目给出的排队规则来模拟一下过程就行了。
2. 代码实现
给出python的代码实现如下：
class Solution:
def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
while sandwiches != [] and any(x == sandwiches[0] for x in students):
while sandwiches[0] != students[0]:
students.append(students.pop(0))
students.pop(0)
sandwiches.pop(0)
return len(students)可以看到，上述算法的算法复杂度为O(N^2)。
提交代码评测得到：耗时40ms，占用内存14.3MB。
当前最优的算法实现耗时36ms，但是算法思路本身没啥差别，因此就不过多展开了。
当然，如果有读者能够想明白里面本质的数学关系然后能够直接给出答案的话，请务必在评论区留言告知一下，感激不尽！
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题事实上也是非常直接的，由于顾客本就是按到达时间排序的，然后厨师也只有一个，因此，我们只需要不断地更新厨师完成上一个顾客的点单的时间然后计算每一个顾客的等待时间即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def averageWaitingTime(self, customers: List[List[int]]) -> float:
wait_time = 0
time = 0
for a, t in customers:
if time >= a:
wait_time += time-a + t
time += t
else:
wait_time += t
time = a + t
return wait_time / len(customers)显然，这一算法的算法复杂度只有O(N)而已。
提交代码评测得到：耗时952ms，占用内存55.2MB。
当前最优的代码实现耗时896ms，但是看了一下本质思路上和我们是完全一致的，因此就不过多展开了。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题，事实上我感觉包括下面一道题，都是考验智商的题目，这一题的关键点就在于是否能够看出以下两个推论：
- 对于任何一个二进制字符串，我们都能够通过有限次操作，将所有的0全部聚集到一起，且第一个0的位置就是原字符串中第一个0的位置；
- 对于任何一串连续的0，事实上我们都能够通过有限次操作，将除了最后一个0之外的其他所有的0转换为1；
通过以上两点，事实上我们很简单就能看出，最优解事实上就是：
- 统计所有的0的个数k以及第一个0的位置i，最终解就是除了i+k?1之外所有的位置上都是1的一个二进制字符串。
2. 代码实现
给出最终的python代码实现如下：
class Solution:
def maximumBinaryString(self, binary: str) -> str:
n = len(binary)
cnt = 0
flag = -1
for idx, c in enumerate(binary):
if c == "0":
cnt += 1
if flag == -1:
flag = idx
if cnt == 0:
return binary
else:
flag = flag + cnt - 1
return "1" * flag + "0" + "1" * (n-flag-1)上述算法的算法复杂度为O(N)。
提交代码评测得到：耗时380ms，占用内存15.6MB。
当前最优的算法实现耗时56ms，但是他的本质思路和我们是完全一致的，唯一的区别在于具体的实现上，这里就不多做展开了，仅仅给出他们的实现代码如下：
class Solution:
def maximumBinaryString(self, binary: str) -> str:
n=len(binary)
idx=binary.find('0')
if idx==-1:
return binary
cnt=binary.count('0')
return "1"*(idx+cnt-1)+"0"+"1"*(n-idx-cnt)可以看到，本质上是完全相同的，但是实现上更为优雅。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题隔了一天倒是终于自己把这道题目给做出来了，但是怎么说呢，多少算是先蒙再证的吧。
如前所述，个人觉得，这一题事实上考察的是数学证明题的功底，或者说某种意义上也就是智商。
这道题整体的思路还算是比较清晰，就是找出原数组中所有的1的位置。然后要获取k个连续的1，那么要做的必然就是将取某连续的k个1进行团聚操作，然后获取其中的最小值。
显然我们只需要考虑对连续的k个1进行团聚操作就行了，这个结论应该不用过多说明，也就是说，假设有n个1，我们只需要考虑所有的ones[i:i+k]中团聚操作所需要的最小值即可。
那么，剩下的问题就在于，当我们给出了k个1时，要让他们团聚起来，所需要的最少操作次数是多少呢？
这里，我们给出一个很强的假设：
- 对于任意k个位置元素，要使他们团聚到一起所需要的最少操作次数一定是将他们团聚到中心元素时所进行的操作次数。
我们基于此写代码进行了考察，发现上述假设是正确的，下面，我们尝试来证明上述假设的正确性。
假设k个元素的中心元素，将所有的元素全部向元素i进行靠拢时所经历的总的操作次数为n，那么显然的，所有i左侧的元素都是向右侧靠拢的，所有i右侧的元素都是向左侧靠拢的。
我们考虑当以i?1作为锚点元素进行靠拢时的情况，假设第i?1个点与第i个点的位置距离为w，此时变动的操作次数为：
同理我们可以证明从中点向右移动时的结论。
综上，我们可以论证，上述假设是正确的，即永远当取中点为团聚锚点时，所需要经过的移动次数最少。
此时我们就可以快速地给出团聚所需要的最少操作次数如下：
这部分的计算事实上我们又可以通过事先算出累积和的方式进行算法优化，这部分就不必细讲了，有兴趣的读者直接看代码就行了。
2. 代码实现
给出python代码实现如下：
class Solution:
def minMoves(self, nums: List[int], k: int) -> int:
ones = [idx for idx, i in enumerate(nums) if i == 1]
cumsum = [0] + list(accumulate(ones))
def cal_delta(k):
t1 = k // 2
t2 = k-1-t1
return t1*(t1+1) // 2 + t2*(t2+1) // 2
n = len(ones)
delta = cal_delta(k)
idx = 0
res = math.inf
while idx + k <= n:
mid = idx+(k-1)//2
dis = (cumsum[idx+k] - cumsum[mid+1]) - (cumsum[mid] - cumsum[idx]) - delta
dis = dis if k % 2 == 1 else dis - ones[mid]
res = min(dis, res)
idx += 1
return res可以看到，上述代码的算法复杂度为O(N)。
提交代码评测得到：耗时1356ms，占用内存25.5MB。
当前的最优算法耗时1308ms，感觉差不多，因此就不过多展开了，有兴趣的读者可以自行去阅读他们的解法。