LeetCode笔记：Biweekly Contest 42 比赛记录_值k聚集到一起最少次数

• LeetCode笔记：Biweekly Contest 42
  • 0. 赛后总结
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

0. 赛后总结

唉，前两周刚和同学吹牛说现在leetcode的比赛基本都能在前10%，发挥好的话能争国内前100，然后这周转头就被打脸，打得啪啪响，国内320/1578，世界1023/6631，连前20%都没卡进去，真的是惨遭滑铁卢。。。

当然借口总是能找的，中午没休息，晚上打比赛太累什么的，但是这就没意思了，本质上来说，这次还是因为智商问题，这次的题目感觉都是数学问题，需要想清楚里面的本质数学关系，然后比赛的时候没能想清楚，说白了就是这么回事，a.k.a，智商不够，唉。。。

这时候说啥都没用了，吃一堑长一智，沉下心来，慢慢努力吧！

1. 题目一

给出题目一的试题链接如下：

• 5621. 无法吃午餐的学生数量

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)
1
2
3
4
5
6
7
8

可以看到，上述算法的算法复杂度为$O(N^2)$。

提交代码评测得到：耗时40ms，占用内存14.3MB。

当前最优的算法实现耗时36ms，但是算法思路本身没啥差别，因此就不过多展开了。

当然，如果有读者能够想明白里面本质的数学关系然后能够直接给出答案的话，请务必在评论区留言告知一下，感激不尽！

2. 题目二

给出题目二的试题链接如下：

• 5622. 平均等待时间

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)
1
2
3
4
5
6
7
8
9
10
11
12

显然，这一算法的算法复杂度只有$O(N)$而已。

提交代码评测得到：耗时952ms，占用内存55.2MB。

当前最优的代码实现耗时896ms，但是看了一下本质思路上和我们是完全一致的，因此就不过多展开了。

3. 题目三

给出题目三的试题链接如下：

• 5623. 修改后的最大二进制字符串

1. 解题思路

这一题，事实上我感觉包括下面一道题，都是考验智商的题目，这一题的关键点就在于是否能够看出以下两个推论：

1. 对于任何一个二进制字符串，我们都能够通过有限次操作，将所有的0全部聚集到一起，且第一个0的位置就是原字符串中第一个0的位置；
2. 对于任何一串连续的0，事实上我们都能够通过有限次操作，将除了最后一个0之外的其他所有的0转换为1；

通过以上两点，事实上我们很简单就能看出，最优解事实上就是：

• 统计所有的0的个数$k$以及第一个0的位置$i$，最终解就是除了$i+k-1$之外所有的位置上都是1的一个二进制字符串。

可惜我们比赛的时候一开始没有想的非常清楚，先将所有的连续的0进行了转换，导致有效的0的个数减少了，导致0推移的位置被往前挪了，最终导致了失败，唉，智商啊。。。

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

上述算法的算法复杂度为$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)
1
2
3
4
5
6
7
8

可以看到，本质上是完全相同的，但是实现上更为优雅。

4. 题目四

给出题目四的试题链接如下：

• 5624. 得到连续 K 个 1 的最少相邻交换次数

1. 解题思路

这一题隔了一天倒是终于自己把这道题目给做出来了，但是怎么说呢，多少算是先蒙再证的吧。

如前所述，个人觉得，这一题事实上考察的是数学证明题的功底，或者说某种意义上也就是智商。

这道题整体的思路还算是比较清晰，就是找出原数组中所有的1的位置。然后要获取k个连续的1，那么要做的必然就是将取某连续的k个1进行团聚操作，然后获取其中的最小值。

显然我们只需要考虑对连续的k个1进行团聚操作就行了，这个结论应该不用过多说明，也就是说，假设有n个1，我们只需要考虑所有的ones[i:i+k]中团聚操作所需要的最小值即可。

那么，剩下的问题就在于，当我们给出了k个1时，要让他们团聚起来，所需要的最少操作次数是多少呢？

这里，我们给出一个很强的假设：

• 对于任意k个位置元素，要使他们团聚到一起所需要的最少操作次数一定是将他们团聚到中心元素时所进行的操作次数。

我们基于此写代码进行了考察，发现上述假设是正确的，下面，我们尝试来证明上述假设的正确性。

假设$i$为$k$个元素的中心元素，将所有的元素全部向元素i进行靠拢时所经历的总的操作次数为$n$，那么显然的，所有$i$左侧的元素都是向右侧靠拢的，所有$i$右侧的元素都是向左侧靠拢的。

我们考虑当以$i-1$作为锚点元素进行靠拢时的情况，假设第$i-1$个点与第$i$个点的位置距离为$w$，此时变动的操作次数为：
δ ( d i s t a n c e ) = ( n − i ) ⋅ ( w − 1 ) − ( i − 2 ) ⋅ ( w − 1 ) = ( n + 2 − 2 ⋅ i ) × ( w − 1 ) ≥ 0

$$\begin{aligned} \delta(distance) &= (n-i)\cdot (w-1) - (i-2)\cdot (w-1) \\ &= (n+2-2\cdot i) \times (w-1) \\ &\geq 0 \end{aligned}$$ δ(distance)​=(n−i)⋅(w−1)−(i−2)⋅(w−1)=(n+2−2⋅i)×(w−1)≥0​

从上式可以看到，事实上，当$i$不大于$\frac{n+2}{2}$时，恒有结论：

• 锚点靠左时的团聚所需要进行的操作次数用于不少于锚点靠右时的操作次数。

同理我们可以证明从中点向右移动时的结论。

综上，我们可以论证，上述假设是正确的，即永远当取中点为团聚锚点时，所需要经过的移动次数最少。

此时我们就可以快速地给出团聚所需要的最少操作次数如下：

s = ∑ j = 1 i − 1 ( ( l i − l j ) − ( i − j ) ) + ∑ j = i + 1 n ( ( l j − l i ) − ( j − i ) ) = ∑ j = i + 1 n l j − ∑ j = 1 i − 1 l j + ( n + 1 − 2 ⋅ i ) ⋅ l i − i ⋅ ( i − 1 ) 2 − ( n − i ) ( n − i + 1 ) 2

$$\begin{aligned} s &= \sum_{j=1}^{i-1}{((l_i - l_j) - (i-j))} + \sum_{j=i+1}^{n}((l_j-l_i) - (j-i)) \\ &= \sum_{j=i+1}^{n}{l_j}-\sum_{j=1}^{i-1}{l_j} + (n+1-2\cdot i) \cdot l_i - \frac{i\cdot (i-1)}{2} - \frac{(n-i)(n-i+1)}{2} \end{aligned}$$ s​=j=1∑i−1​((li​−lj​)−(i−j))+j=i+1∑n​((lj​−li​)−(j−i))=j=i+1∑n​lj​−j=1∑i−1​lj​+(n+1−2⋅i)⋅li​−2i⋅(i−1)​−2(n−i)(n−i+1)​​

这部分的计算事实上我们又可以通过事先算出累积和的方式进行算法优化，这部分就不必细讲了，有兴趣的读者直接看代码就行了。

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

可以看到，上述代码的算法复杂度为$O(N)$。

提交代码评测得到：耗时1356ms，占用内存25.5MB。

当前的最优算法耗时1308ms，感觉差不多，因此就不过多展开了，有兴趣的读者可以自行去阅读他们的解法。