LeetCode筆記：Weekly Contest 223 比賽記錄

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

0. 賽后總結

這次的比賽總算是久違的把全部題目都做出來了，雖然耗時還是蠻多的，但是能做出來就是好事，唉，總算不像是前兩周那么憋屈了，，，

結果來說，這次國內是147/3870，世界356/10671，都是前3%左右，挺好的，所以晚上獎勵自己吃頓好的吧😂

1. 題目一

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

• 5649. 解碼異或后的陣列

1. 解題思路

這道題其實就是考了一下異或的特征，無非就是a^a == 0，所以我們不斷地求異或就能夠反推出原先的全部元素，

2. 代碼實作

給出python代碼實作如下：

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        n = len(encoded)
        res = [first for _ in range(n+1)]
        for i in range(n):
            res[i+1] = first ^ encoded[i]
            first = res[i+1]
        return res

整體的演算法復雜度為 O ( N ) O(N) O(N)，提交代碼評測得到：耗時64ms，占用記憶體16MB，

2. 題目二

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

• 5652. 交換鏈表中的節點

1. 解題思路

這一題的思路就更加簡單了，把鏈表中的兩個節點進行定位之后然后交換一下他們的值就行了，

2. 代碼實作

給出python代碼實作如下：

class Solution:
    def swapNodes(self, head: ListNode, k: int) -> ListNode:
        def count_len(head):
            l = 0
            while head:
                l += 1
                head = head.next
            return l
        n = count_len(head)
        i, j = k, n-k+1
        if i == j:
            return head
        p = head
        for k in range(1, n+1):
            if k == i:
                nodei = p
            if k == j:
                nodej = p
            if k > max(i, j):
                break
            p = p.next
        nodei.val, nodej.val = nodej.val, nodei.val
        return head

可以看到，整體的演算法復雜度同樣為 O ( N ) O(N) O(N)，提交代碼評測得到：耗時1144ms，占用記憶體48.9MB，

3. 題目三

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

• 5650. 執行交換操作后的最小漢明距離

1. 解題思路

這一題的考察點應該是有兩部分，分別為：

1. 當一些元素是相互連接的情況時，我們總能夠通過有限次操作將他們的順序任意重排；
2. 如何快速得到元素間的相互連接關系，

其中，前者可以通過數學歸納法進行證明，后者則可以通過DSU結構進行實作，

有關DSU相關的內容可以參考我之前的博客：Python筆記：并查集（DSU）結構簡介，

2. 代碼實作

給出python代碼實作如下：

class DSU:
    def __init__(self, n):
        self.dsu = [i for i in range(n)]
        
    def find(self, x):
        if x != self.dsu[x]:
            self.dsu[x] = self.find(self.dsu[x])
        return self.dsu[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.dsu[x] = y
        return
        
class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        n = len(source)
        dsu = DSU(n)
        for x, y in allowedSwaps:
            dsu.union(x, y)
        groups = defaultdict(list)
        for i in range(n):
            groups[dsu.find(i)].append(i)
        res = 0
        for group in groups.values():
            counter = defaultdict(int)
            for idx in group:
                counter[source[idx]] += 1
                counter[target[idx]] -= 1
            res += sum(x for x in counter.values() if x > 0)
        return res

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

4. 題目四

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

• 5639. 完成所有作業的最短時間

1. 解題思路

這一題最直接的思路就是采用迭代演算法，然后我們可以使用快取的方式構建一個偽動態規劃演算法來優化實行效率，

我們給出迭代的思路如下：

1. 每一次操作，都找到當前的第一個元素，將其和后面的某一個元素進行合并，然后迭代進行下一次操作；
2. 如果某一次操作之后元素總數目剛好為工人數目，則回傳當前堆中的最大值作為這一策略下的結果，然后求取最小值即可，

2. 代碼實作

我們給出python代碼實作如下：

class Solution:
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
        n = len(jobs)
        if k == n:
            return max(jobs)
        elif k == 1:
            return sum(jobs)
        jobs = sorted(jobs)
        if k == n-1:
            return max(jobs[-1], jobs[0] + jobs[1])
        
        @lru_cache(None)
        def dp(work):
            if len(work) == k:
                return max(work)
            m = len(work)
            res = math.inf
            work = list(work)
            for i in range(1, m):
                work[i] += work[0]
                res = min(dp(tuple(work[1:])), res)
                work[i] -= work[0]
            return res

        return dp(tuple(jobs))

評測得到結果如下：耗時2060ms，占用記憶體83.5MB，屬于當前最優解法，