LeetCode筆記：Weekly Contest 219 比賽記錄

• LeetCode筆記：Weekly Contest 219
  • 0. 賽后總結
  • 1. 題目一
    • 1. 解題思路
    • 2. 代碼實作
  • 2. 題目二
    • 1. 解題思路
    • 2. 代碼實作
  • 3. 題目三
    • 1. 解題思路
    • 2. 代碼實作
  • 4. 題目四
    • 1. 解題思路
    • 2. 代碼實作

0. 賽后總結

這一次的比賽怎么說呢，感覺有點不尷不尬的，

要說吧，4道題也都做出來了，耗時老實說也沒有特別長，不算錯誤懲罰的話其實也就56分鐘，不到1個小時，整體雖然沒有擠進國內前100，好歹也有前4%（116/3682），世界排名也是311/9290，也屬于前4%，照說應該是一次不錯的發揮了，

但是吧，就是感覺不舒服，第三題第四題做的實在太糾結了，尤其是第三題，雖然說一次過了，但是用的是最暴力的迭代演算法，講道理能過完全是運氣好，我本來完全沒報希望的，只是因為實在想不到更好的演算法了，

第四題也是，雖說最后以兩次錯誤的代價提交成功了，但是看錯題目實在是硬傷，而且演算法也不算多少優雅，還是用的非常暴力的迭代求解的演算法，

唉，回頭等比賽結束之后好好地研究一下別人的解法學習一下吧，

1. 題目一

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

• 5625. 比賽中的配對次數

1. 解題思路

這一題思路很直接，就是直接按照規則一路往下就行了，

2. 代碼實作

給出python代碼實作如下：

class Solution:
    def numberOfMatches(self, n: int) -> int:
        res = 0
        while n != 1:
            res += n // 2
            n = (n+1) // 2
        return res

提交代碼評測得到：耗時20ms，占用記憶體14.3MB，屬于當前最優代碼實作，

2. 題目二

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

• 5626. 十-二進制數的最少數目

1. 解題思路

這一題乍看之下有點復雜，但其實仔細一想例外簡單，顯然，由于二進制數只能由1、0組成，因此，對于任意一個數，假設這個數字中最大的位元數為k，則至少需要k個十-二進制數才能夠分解這個數字，

而另一方面，如果我們采用如下規則進行數字拆解：

• 當且僅當數字中最大位數的位置取1，其他位置取0，構建一個十-二進制數，然后減去這個數字；

重復上述操作，可以看到，當k次操作之后，總能夠將這個數字變為0，

綜上，k就是最終的答案，

2. 代碼實作

因此，我們可以快速地給出python代碼實作如下：

class Solution:
    def minPartitions(self, n: str) -> int:
        return max(int(x) for x in n)

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

當前的最優代碼實作耗時僅52ms，但是本質來說演算法思路是完全一致的，不過他們沒有將每一個bit都進行整形轉換，而是利用了ascii碼中的順序關系簡化了代碼，

給出他們的代碼實作如下：

class Solution:
    def minPartitions(self, n: str) -> int:
        return ord(max(n)) - ord('0')

3. 題目三

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

• 5627. 石子游戲 VII

1. 解題思路

這一題比賽中我是用最為暴力地迭代方法進行求解的，因為遞推公式還是很好寫出來的，

假設在每一輪操作（Alice和Bob各自進行一次操作）當中，Alice選擇的元素為 a a a，Bob選擇的元素為 b b b，而在他們進行操作之前的元素總和為 s s s，則Alice得分為 s ? a s-a s?a，Bob的得分為 s ? a ? b s-a-b s?a?b，該輪操作導致的兩人的分差變化為 b b b

因此，我們可以快速地寫出每一次操作的遞推公式如下：

dp(i, j) = max(min(stones[j]+dp(i+1, j-1), stones[i+1] + dp(i+2, j)), min(stones[i]+dp(i+1, j-1), stones[j-1] + dp(i, j-2)))

其中，四種情況分別代表：

1. Alice優先取第i個元素：
   1. Bob取第j個元素；
   2. Bob取第i+1個元素；
2. Alice優先取第j個元素；
   1. Bob取第i個元素；
   2. Bob取第j-1個元素；

2. 代碼實作

給出python代碼實作如下：

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
      
        @lru_cache(None)
        def dp(st, ed):
            if st >= ed:
                return 0
            else:
                return max(min(stones[ed]+dp(st+1, ed-1), stones[st+1] + dp(st+2, ed)), min(stones[st]+dp(st+1, ed-1), stones[ed-1] + dp(st, ed-2)))
            
        return dp(0, len(stones)-1)

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

當前的最優代碼實作耗時4092ms，而且看他的實作也沒覺得多好，但是我總覺得應該有更加優雅的實作方法，唉，過兩天再看看有沒有更好的解法吧，

4. 題目四

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

• 5245. 堆疊長方體的最大高度

1. 解題思路

這一題坦率地說感覺也是應該有更好的解題方法的，可惜我這邊實在是沒想到什么更好更優雅的解題方法，只能用暴力求解的方法硬懟，

不過幸運的是，終究還是懟出來了就是了，

對于這一題，核心在于兩點：

1. 排序
2. 遞推關系

首先，由于題目限制說一個長方體 j j j要能夠疊放在另一個長方體 i i i的話，要求：
{ w i ≥ w j l i ≥ l j h i ≥ h j \left\{ \begin{aligned} w_i &\geq w_j \\ l_i &\geq l_j \\ h_i &\geq h_j \end{aligned} \right. ??????wi?li?hi??≥wj?≥lj?≥hj??

因此，我們對長方體按照邊長進行排序，顯然最終的結果必然是排序后結果的一個子序列，

另一方面，我們來討論遞推關系，他有以下一些情況：

1. 當前長方體不使用的情況；
2. 當前長方體使用的情況，此時根據長寬高的選擇又可以分為三種情況，

綜上，我們就可以給出最終的遞推關系，

2. 代碼實作

給出python的代碼實作如下：

class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        n = len(cuboids)
        cuboids = sorted([sorted(x, reverse=True) for x in cuboids], reverse=True)
        # print(cuboids)
        
        @lru_cache(None)
        def dp(idx, a, b, c):
            if idx >= n:
                return 0
            res = dp(idx+1, a, b, c)
            aa, bb, cc = cuboids[idx]
            if cc <= c and ((aa <= a and bb <= b) or (aa <= b and bb <= a)):
                res = max(res, cc + dp(idx+1, aa, bb, cc))
            if bb <= c and ((aa <= a and cc <= b) or (aa <= b and cc <= a)):
                res = max(res, bb + dp(idx+1, aa, cc, bb))
            if aa <= c and ((bb <= a and cc <= b) or (bb <= b and cc <= a)):
                res = max(res, aa + dp(idx+1, bb, cc, aa))
            return res
                
        return dp(0, 101, 101, 101)

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

當前最優的代碼實作耗時132ms，大致看了一下，感覺思路上和我們是一致的，不過細節實作上有所差別，感覺比我們的更加簡明一些，不過細節沒有細看，有興趣的讀者可以自行研究一下，