LeetCode筆記：Biweekly Contest 42 比賽記錄

• 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)

可以看到，上述演算法的演算法復雜度為 O ( N 2 ) O(N^2) O(N2)，

提交代碼評測得到：耗時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)

顯然，這一演算法的演算法復雜度只有 O ( N ) O(N) O(N)而已，

提交代碼評測得到：耗時952ms，占用記憶體55.2MB，

當前最優的代碼實作耗時896ms，但是看了一下本質思路上和我們是完全一致的，因此就不過多展開了，

3. 題目三

給出題目三的試題鏈接如下：

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

1. 解題思路

這一題，事實上我感覺包括下面一道題，都是考驗智商的題目，這一題的關鍵點就在于是否能夠看出以下兩個推論：

1. 對于任何一個二進制字串，我們都能夠通過有限次操作，將所有的0全部聚集到一起，且第一個0的位置就是原字串中第一個0的位置；
2. 對于任何一串連續的0，事實上我們都能夠通過有限次操作，將除了最后一個0之外的其他所有的0轉換為1；

通過以上兩點，事實上我們很簡單就能看出，最優解事實上就是：

• 統計所有的0的個數 k k k以及第一個0的位置 i i i，最終解就是除了 i + k ? 1 i+k-1 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)

上述演算法的演算法復雜度為 O ( N ) O(N) 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. 題目四

給出題目四的試題鏈接如下：

• 5624. 得到連續 K 個 1 的最少相鄰交換次數

1. 解題思路

這一題隔了一天倒是終于自己把這道題目給做出來了，但是怎么說呢，多少算是先蒙再證的吧，

如前所述，個人覺得，這一題事實上考察的是數學證明題的功底，或者說某種意義上也就是智商，

這道題整體的思路還算是比較清晰，就是找出原陣列中所有的1的位置，然后要獲取k個連續的1，那么要做的必然就是將取某連續的k個1進行團聚操作，然后獲取其中的最小值，

顯然我們只需要考慮對連續的k個1進行團聚操作就行了，這個結論應該不用過多說明，也就是說，假設有n個1，我們只需要考慮所有的ones[i:i+k]中團聚操作所需要的最小值即可，

那么，剩下的問題就在于，當我們給出了k個1時，要讓他們團聚起來，所需要的最少操作次數是多少呢？

這里，我們給出一個很強的假設：

• 對于任意k個位置元素，要使他們團聚到一起所需要的最少操作次數一定是將他們團聚到中心元素時所進行的操作次數，

我們基于此寫代碼進行了考察，發現上述假設是正確的，下面，我們嘗試來證明上述假設的正確性，

假設 i i i為 k k k個元素的中心元素，將所有的元素全部向元素i進行靠攏時所經歷的總的操作次數為 n n n，那么顯然的，所有 i i i左側的元素都是向右側靠攏的，所有 i i i右側的元素都是向左側靠攏的，

我們考慮當以 i ? 1 i-1 i?1作為錨點元素進行靠攏時的情況，假設第 i ? 1 i-1 i?1個點與第 i i i個點的位置距離為 w w 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 i i不大于 n + 2 2 \frac{n+2}{2} 2n+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

可以看到，上述代碼的演算法復雜度為 O ( N ) O(N) O(N)，

提交代碼評測得到：耗時1356ms，占用記憶體25.5MB，

當前的最優演算法耗時1308ms，感覺差不多，因此就不過多展開了，有興趣的讀者可以自行去閱讀他們的解法，