LeetCode筆記：Weekly Contest 229 比賽記錄

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

0. 賽后總結

這周的比賽整體都給跪了，兩場比賽都是不順的要死，昨天的比賽還能歸結到看錯題目，這次的比賽就真的是沒得洗了，第三題超時之后就沒有更好的思路了，第四題壓根沒有一個可行的思路，想到的解法實作出來之后發現都有系統性的bug，簡直了……

果然傲慢是原罪啊，明明自己還這么弱，還和人吹牛逼，flag一立，打臉立來，唉……

1. 題目一

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

• 5685. 交替合并字串

1. 解題思路

這一題倒是沒啥難度，直接按照題目意思交替組成新的字串即可，

2. 代碼實作

給出python代碼實作如下：

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        n, m = len(word1), len(word2)
        i, j = 0, 0
        res = ""
        while i<n and j<m:
            res += word1[i] + word2[j]
            i += 1
            j += 1
        if i < n:
            res += word1[i:]
        if j < m:
            res += word2[j:]
        return res

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

當前最有代碼實作耗時28ms，但是看了一下實作思路是完全相同的，就不過多展開了，

2. 題目二

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

• 5686. 移動所有球到每個盒子所需的最小運算元

1. 解題思路

這一題比賽的時候用暴力演算法直接強行解掉了，不過代碼實在是不夠優雅，賽后重新看了一下，其實可以將演算法復雜度退化至 O ( N ) O(N) O(N)，

首先，我們先算一下全部移動到第一個位置時的代價，

然后，我們假設已知全部移動到第 i i i個位置時的答案為 s i s_i si?，考察全部移動到第 i + 1 i+1 i+1時的所需的代價數顯然有：

s i + 1 = s i + c i ? ( t o t ? c i ) s_{i+1} = s_{i} + c_{i} - (tot - c_{i}) si+1?=si?+ci??(tot?ci?)

其中， c i c_i ci?為到第 i i i個位置為止所包含的小球的數目， t o t tot tot則是總的小球數目，

由此，通過數學歸納法的思路，我們就可以在 O ( N ) O(N) O(N)的演算法復雜度情況下獲取所有位置上的解，

2. 代碼實作

給出python代碼實作如下：

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        boxes = [int(x) for x in boxes]
        n = len(boxes)
        cumsum = list(accumulate(boxes))
        res = [0 for _ in range(n)]
        s = 0
        for i in range(n):
            s += i*boxes[i]
        res[0] = s
        for i in range(1, n):
            s += cumsum[i-1] - (cumsum[-1] - cumsum[i-1])
            res[i] = s
        return res

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

為當前最優代碼實作，

3. 題目三

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

• 5687. 執行乘法運算的最大分數

1. 解題思路

這一題比賽的時候因為超時一直沒能搞定，賽后看了一下別人的解法，然后就崩碎了我的三觀，因為他的演算法實作和我一模一樣，就是比我多了一行代碼，一行清理快取的代碼，然后就避免了超時的問題……

呵呵，這題真傻逼……

沒啥復雜的，暴力求解的話就是動態規劃，后面看看有沒有什么更好的解題思路吧……

2. 代碼實作

給出python代碼實作如下：

class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        n, m = len(nums), len(multipliers)
        
        @lru_cache(None)
        def dp(i, j, k):
            if k == m:
                return 0
            return max(nums[i]*multipliers[k] + dp(i+1, j, k+1), nums[j]*multipliers[k] + dp(i, j-1, k+1))
        
        res = dp(0, n-1, 0)
        dp.cache_clear()
        return res

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

當前最優的代碼實作耗時3336ms，并沒有量級上的差異，但是有將近3倍的效率提升，因此，有興趣的讀者后續可以自行研究一下他們的思路，

4. 題目四

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

• 5688. 由子序列構造的最長回文串的長度

1. 解題思路

這一題在比賽的時候完全沒有一個好的思路，直接的思路是先進行拼接之后對比正反兩個字串，考察公共子串相關的內容再進行考察，但是就是遇到了界限問題……

比賽結束之后失落了好久，然后今天看了一下答案之后發現就是一個動態規劃問題而已，和上一題基本是異曲同工，只要用兩個滑動指標分別從兩側向中心靠近即可，

2. 代碼實作

給出python代碼實作如下：

class Solution:
    def longestPalindrome(self, word1: str, word2: str) -> int:
        s = word1 + word2
        n, m = len(word1), len(word2)
        
        @lru_cache(None)
        def dp(i, j, s1, s2):
            if i >= n and not s1:
                return -10000
            if j < n and not s2:
                return -10000
            if i == j:
                return 1
            if i > j:
                return 0
            
            if s[i] == s[j]:
                return 2 + dp(i+1, j-1, True, True)
            else:
                return max(dp(i, j-1, s1, s2), dp(i+1, j, s1, s2))
            
        res = dp(0, n+m-1, False, False)
        dp.cache_clear()
        return max(res, 0)

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

當前最優的代碼實作耗時2536ms，用興趣的讀者可以自行研讀一下，這里暫時我就不多做展開了……