LeetCode 2024/03/01-2024/03/10 每日一題

每日第1題為中文站(LCCN) ，第2題為英文站(LCUS) ，題目連結皆統一為英文站的題目連結。
Easy 、Medium 、Hard 難度的題目分別用🟢🟡🔴表示。
若為周賽題目會額外標註由 @zreotrac 零神計算的rating分數。

All problems solved by python

---

2024-03-01

🟡 2369. Check if There is a Valid Partition For The Array 1780

題意

• 給定一個下標從 $0$ 開始的整數陣列 $nums$，你必須將陣列分成一個或多個 連續 子陣列。
• 如果分割後的每個子陣列滿足以下條件之一，則可以稱其為陣列的一種 有效分割(Valid Partition)：
  1. 子陣列 恰好 由 $2$ 個相等元素組成，例如，子陣列 $[2,2]$ 是有效的。
  2. 子陣列 恰好 由 $3$ 個相等元素組成，例如，子陣列 $[4,4,4]$ 是有效的。
  3. 子陣列 恰好 由 $3$ 個連續遞增元素組成，且相鄰元素之間的差值為 $1$。例如，子陣列 $[3,4,5]$ 是有效的，但是子陣列 $[1,3,5]$ 不是。
• 如果陣列 至少 存在一種有效分割，則傳回 $true$，否則，傳回 $false$。

思路：動態規劃(DP)

• 令 $dp[i]$ 表示 $nums[:i]$ 是否存在Valid Partition，則有以下情況：
  1. 如果 $i > 0$ 且 $dp[i-1]$ 且 $nums[i] == nums[i-1]$，則 $dp[i+1] = True$，即情況1。
  2. 如果 $i > 1$ 且 $dp[i-2]$ 且 $nums[i] == nums[i-1] == nums[i-2]$ 或 $nums[i] == nums[i-1] + 1 == nums[i-2] + 2$，則 $dp[i+1] = True$，即情況2和情況3。
• 最後回傳 $dp[n]$ 即可。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [True] + [False] * n

        for i, x in enumerate(nums):
            if i > 0 and dp[i - 1] and x == nums[i - 1]: # 情況1
                dp[i + 1] = True
            elif i > 1 and dp[i - 2]: # 情況2/3
                if (x == nums[i - 1] == nums[i - 2]) or (x == nums[i - 1] + 1 == nums[i - 2] + 2):
                    dp[i + 1] = True
        return dp[n]

---

🟢 2864. Maximum Odd Binary Number 1238

題意

• 給定一個二進位字串 $s$，其中至少包含一個 ‘1’。
• 重新排列 字串中的位元，使得到的二進位數字是可以由該組合產生的 最大二進位奇數。
• 返回所得的數字，以二進位字串形式表示。
• 注意：返回的字串可以含有前導零。

思路：貪婪(Greedy)

• 由於要找最大 奇數 ，所以最後一位一定是 $1$ ，且為使得數字最大，可以基於貪婪思路，使得前面的 $1$ 越多越好。
• 因此，只要計算 $s$ 中 $1$ 的個數 $cnt_1$，將前 $cnt_1 - 1$ 個位置設為 $1$，其餘位置設為 $0$，最後一位設為 $1$ 即可。
• 時間複雜度：$O(n)$，其中 $n$ 為 $s$ 的長度。
• 空間複雜度：$O(1)$

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        n = len(s)
        cnt_1 = s.count('1')
        return '1' * (cnt_1 - 1) + '0' * (n - cnt_1) + '1'

---

2024-03-02

🟡 2368. Reachable Nodes With Restrictions 1477

題意

• 有一棵由 $n$ 個節點組成的無向樹，節點編號從 $0$ 到 $n - 1$ ，共有 $n - 1$ 條邊。
• 給定一個長度為 $n - 1$ 的二維整數陣列 $edges$ ，其中 $edges[i] = [a_i, b_i]$ 表示樹中節點 $a_i$ 和 $b_i$ 之間存在一條邊。 另給定一個整數陣列 $restricted$ 表示 受限 節點。
• 在不訪問受限節點的前提下，返回可以從節點 $0$ 到達的 最多 節點數目。
• 注意：節點 $0$ 不會 被標記為受限節點。

思路：BFS/DFS

• 首先根據題意，由於不能訪問受限節點，所以在建圖時可以直接略過兩個端點中有受限節點的邊。
• 然後可以使用BFS或DFS進行遍歷，計算可以到達的節點數目即可。

方法一：BFS

• 使用BFS進行遍歷，計算可以到達的節點數目，將 $(0, -1)$ 加入queue中，表示從節點 $0$ 開始遍歷，並且父節點為 $-1$。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        restricted = set(restricted)
        g = [[] for _ in range(n)]
        for u, v in edges:
            if u in restricted or v in restricted: # 略過受限節點
                continue
            g[u].append(v)
            g[v].append(u)
        
        ans = 0
        q = deque([(0, -1)]) # (u, fa)
        while q:
            u, fa = q.popleft()
            ans += 1
            for v in g[u]:
                if v == fa:
                    continue
                q.append((v, u))
        return ans

方法二：DFS

• 使用DFS進行遍歷，計算可以到達的節點數目，dfs函數中的參數 $fa$ 表示父節點。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        restricted = set(restricted)
        g = [[] for _ in range(n)]
        for u, v in edges:
            if u in restricted or v in restricted: # 略過受限節點
                continue
            g[u].append(v)
            g[v].append(u)
        
        ans = 0
        def dfs(u, fa):
            nonlocal ans
            ans += 1
            for v in g[u]:
                if v == fa:
                    continue
                dfs(v, u)
        dfs(0, -1)
        return ans

---

🟢 977. Squares of a Sorted Array 1130

題意

• 給定一個按照 非遞減順序 排序的整數陣列 $nums$，返回一個由 每個數字的平方 組成的新陣列，且同樣按照 非遞減順序 排序。

思路：雙指標(Two Pointers) 中的左右指標(相向雙指標)

• 由於陣列是按照非遞減順序排列的，所以可以使用雙指標的方法，分別指向陣列的左右兩端，然後比較兩端的絕對值大小，將較大的平方放入 $ans$ 陣列的尾部。
• 可以使用一個整數 $idx$ 來紀錄 $ans$ 陣列的下一個位置，但由於 $idx$ 被初始化為 $n-1$ ，且每次移動指標時，會使$left + 1$ 或 $right - 1$，所以可以使用 $idx = right - left$ 來代替。
• 時間複雜度：$O(n)$，其中 $n$ 為 $nums$ 的長度。
• 空間複雜度：$O(n)$

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [-1] * n
        left, right = 0, n - 1
        while (left <= right):
            if abs(nums[left]) < abs(nums[right]):
                ans[right - left] = nums[right] ** 2
                right -= 1
            else:
                ans[right - left] = nums[left] ** 2
                left += 1
        return ans

---

2024-03-03

🟢 225. Implement Stack using Queues

先前的文章在 HackMd 上，寫每日一題的時候發現這題在研究所考試的考古題寫過，就把所有思路都記錄下來了，不過考試時可能還要注意 $isFull()$ 的情況。 _[112交大]

題意

使用兩個佇列(queue)實作一個後入先出(LIFO)的堆疊(stack)，並支援普通堆疊的全部四種操作（push、top、pop 和 empty）。

實作 MyStack 類別：

• void push(int x) 將元素 x 壓入堆疊頂端。
• int pop() 移除並傳回堆疊頂端元素。
• int top() 傳回堆疊頂端元素。
• boolean empty() 如果堆疊是空的，則回傳 $true$ ；否則，回傳 $false$ 。

註：

• 只能使用佇列(queue)的標準操作，這代表只有以下四個將元素推送到後端 (pushright)、從前端查看/彈出(popleft)、大小(size) 和是否為空(isEmpty)操作是有效的。
• 由於語言的不同，可能不會原生支持佇列(queue)。可以使用 列表(List) 或 雙端佇列(deque) 模擬佇列，只要僅使用佇列的標準操作即可。

思路

• 根據題意，只能使用佇列(queue)的標準操作，也就是若使用Python中的 雙端佇列(deque) 的話，只能使用 append 和 popleft，不能使用 appendleft 和 pop。

方法一：使用兩個queue，在push時調整

• 目的為 使queue1維持stack的性質 (即 $queue1[0]$ 為stack上最頂端的元素，以此類推)， $queue2$ 用來在調整時暫存 $queue1$ 的元素
• 在上述的前提下，可以發現在stack的4個操作裡面，只有push()會破壞這個性質 ，因此我們要在 $push()$ 的時候做調整。
• 在 $push()$ 時，因為 $queue1$ 本身就具stack的性質，為了繼續維持stack性質，可以先把新的元素push到 $queue2$ ，這樣新的元素在 $queue2$ 中就會是stack最頂層的元素。
• 之後再把原本 $queue1$ 內的元素依次加入 $queue2$ 中 (pop出來後push進 $queue2$ )， $queue2$ 就會維持stack的性質，最後再把 $queue1$ 和 $queue2$ 兩者交換，讓 $queue1$ 繼續維持stack的性質即可。
• 時間複雜度：
  • $push()$: $O(n)$
  • $pop()$: $O(1)$
  • $top()$: $O(1)$
  • $empty()$: $O(1)$
• 空間複雜度：$O(n)$

from collections import deque

class MyStack:
    def __init__(self):
        self.queue1 = deque()
        self.queue2 = deque()

    def push(self, x: int) -> None:
        """
        因為queue1要保持stack的性質，所以要把queue1的元素都移到queue2
        那麼queue2的元素就會維持stack的性質，最後再把兩者交換，讓queue1維持stack的性質
        """
        self.queue2.append(x)
        while self.queue1:
            self.queue2.append(self.queue1.popleft())
        self.queue1, self.queue2 = self.queue2, self.queue1

    def pop(self) -> int:
        """
        在某些語言中的pop()可能不能處理size為0的情況，考試時要注意
        """
        return self.queue1.popleft() if self.queue1 else None

    def top(self) -> int:
        """
        Python的deque沒有top()，直接取[0]就好，另外和pop()相同，在某些語言中的top()可能不能處理size為0的情況，考試時要注意
        """
        return self.queue1[0] if self.queue1 else None

    def empty(self) -> bool:
        return not self.queue1

方法二：使用兩個queue，在pop時調整

• 目的為 使queue1維持queue的性質 ，而 $queue2$ 用來在調整時暫存 $queue1$ 的元素。
• 在上述的前提下，可以發現在stack的4個操作裡面，其實都不會破壞這個性質。
• 但在 $pop()$ 時因為我們不能直接取出和刪除最後一個元素，所以我們要利用暫存用的 $queue2$ ，先對 $queue1$ 做 $n-1$ 次pop，同時把元素push到 $queue2$ 後，再對 $queue1$ 做 $1$ 次pop把最後一個元素pop出來，這個元素就是stack頂端的元素。最後再把兩個queue交換，讓queue1維持原本的性質。
• 在做 $top()$ 時我們同樣不能直接取出最後一個元素，但我們可以利用已經寫好的 $pop()$ ，把頂端的元素pop出來，再把它push回去就好。
• 有些題解在取 $top()$ 時的的方法是用了 $back()$ ，但是這樣可能就不是queue了，不符合題目要求。
• 時間複雜度：
  • $push()$: $O(1)$
  • $pop()$: $O(n)$
  • $top()$: $O(n)$
  • $empty()$: $O(1)$
• 空間複雜度：$O(n)$

class MyStack:
    def __init__(self):
        self.queue1 = deque()
        self.queue2 = deque()

    def push(self, x: int) -> None:
        self.queue1.append(x)

    def pop(self) -> int:
        if not self.queue1:
            return -1
        size = len(self.queue1)
        while size > 1: # n-1 次 pop 出來後 push 到 queue2
            self.queue2.append(self.queue1.popleft())
            size -= 1
        self.queue1, self.queue2 = self.queue2, self.queue1
        return self.queue2.popleft()

    def top(self) -> int:
        """
        這裡可以用上述的pop()方法把top的元素pop出來，再把它push回去就好了
        """
        if not self.queue1:
            return -1
        top = self.pop()
        self.push(top)
        return top

    def empty(self) -> bool:
        return not self.queue1

方法三：使用一個queue

• 和方法二類似，但是不用兩個queue，而是只用一個queue 就能完成
• 使queue1還是維持queue的性質，但不使用queue2暫存queue1的元素，而是直接push回queue1即可 。
• 時間複雜度：
  • $push()$: $O(1)$
  • $pop()$: $O(n)$
  • $top()$: $O(n)$
  • $empty()$: $O(1)$
• 空間複雜度：$O(n)$

class MyStack:
    def __init__(self):
        self.queue = deque()

    def push(self, x: int) -> None:
        self.queue.append(x)

    def pop(self) -> int:
        if not self.queue:
            return None
        size = len(self.queue)
        while size > 1:
            self.queue.append(self.queue.popleft())
            size -= 1
        return self.queue.popleft()

    def top(self) -> int:
        """
        這裡可以用上述的pop()方法把top的元素pop出來，再把它push回去就好了
        """
        if not self.queue:
            return None
        top = self.pop()
        self.push(top)
        return top

    def empty(self) -> bool:
        return not self.queue

---

🟡 19. Remove Nth Node From End of List

題意

• 給定一個 鏈結串列(Linked List) 的頭節點 $head$，從尾部刪除第 $n$ 個節點並返回新的 $head$。

思路：雙指標(Two Pointers)中的快慢指標(同向雙指標)

• 由於我們要找到倒數第 $n$ 個節點，所以可以使用快慢指標的方法，讓快指標先走 $n$ 步，然後快慢指標同時走，當快指標走到結尾時，慢指標就會走到倒數第 $n$ 個節點。
• 但為了要刪除倒數第 $n$ 個節點，我們需要知道倒數第 $n+1$ 個節點，所以我們可以在head前面加一個 $dummy$ 節點，並且令慢指針從 $dummy$ 開始走，這樣當快指標走到結尾時，慢指標就會走到倒數第 $n+1$ 個節點。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        p1 = head
        for _ in range(n):
            p1 = p1.next
        p2 = dummy
        while p1: # 迴圈結束時，p1走到結尾(None)，p2走到倒數第n+1個節點
            p1 = p1.next
            p2 = p2.next
        p2.next = p2.next.next # 刪除倒數第n個節點
        return dummy.next

---

2024-03-04

🟢 232. Implement Queue using Stacks

題意

使用兩個 堆疊(Stack) 實作 先進先出(FIFO) 佇列(queue)。實作的佇列應該支援一般佇列的所有功能（push、pop、peek、empty）。

實作 MyQueue 類別:

• void push(int x) 將元素 $x$ 推入佇列尾部。
• int pop() 從佇列前端移除並返回元素。
• int peek() 返回佇列前端的元素。
• boolean empty() 如果佇列為空，則返回 $true$；否則，返回 $false$。

注意:

• 你必須只使用堆疊的標準操作,即只能往頂端推入、從頂端檢視/取出、大小檢查、空檢查等操作。
• 由於語言的不同，可能不會原生支持堆疊(stack)。你可以使用列表或雙端佇列模擬堆疊,只要使用堆疊的標準操作即可。

備註:

• 您只能使用堆疊的 標準 操作，即只能使用「將元素推入堆疊頂部」、「從堆疊頂部檢視/移除頂部元素」、「確認堆疊大小」和「檢查堆疊是否為空」等操作。
• 根據您的程式語言，堆疊可能不被原生支援。您可以使用 列表(List) 或 雙端佇列(deque) 來模擬堆疊,只要僅使用堆疊的標準操作即可。

思路：使用兩個堆疊(Stack)

• 使用兩個堆疊，使st1用來暫存插入(push)的元素，使st2維持佇列(queue)的性質 (即 $st2[-1]$ 為 queue 最前方的元素，以此類推)。
• 首先必須知道 stack 具有FILO的性質，因此將一些元素 $push()$ 到 $st1$ 中，再從 $st1$ 中 $pop()$ 出來到 $st2$ 中，這樣 $st2$ 就會維持佇列的性質。但需注意，在進行這些操作時，要先判斷 $st2$ 是否為空，若 $st2$ 非空則不用進行搬移，否則會破壞佇列的性質。
• 時間複雜度：
  • $push()$: $O(1)$
  • $pop()$: $O(n)$
  • $top()$: $O(n)$
  • $empty()$: $O(1)$
• 空間複雜度：$O(n)$

class MyQueue:

    def __init__(self):
        self.st1 = []
        self.st2 = []

    def push(self, x: int) -> None:
        self.st1.append(x)

    def pop(self) -> int:
        if not self.st2:
            if not self.st1: # queue is empty
                return -1
            while self.st1:
                self.st2.append(self.st1.pop())
        return self.st2.pop()

    def peek(self) -> int:
        if not self.st2:
            if not self.st1: # queue is empty
                return -1
            while self.st1:
                self.st2.append(self.st1.pop())
        return self.st2[-1]

    def empty(self) -> bool:
        return not self.st1 and not self.st2

---

🟡 948. Bag of Tokens 1762

題意

• 給定初始能量 $power$ 和一組代幣 $tokens$，其中 $tokens[i]$ 是第 $i$ 個代幣的值 (下標從 $0$ 開始)。
• 初始分數為 $0$，目標是通過有策略地使用這些代幣以 最大化 總 分數 。在每次操作中，可以使用以下兩種方式中的一種來使用一個 未被使用的 代幣（但對同一個代幣只能使用其中一種方式）：
  • 朝上：如果你當前 至少 有 $tokens[i]$ 點 能量，可以使用代幣 $i$，失去 $tokens[i]$ 點 能量，並得到 $1$ 分。
  • 朝下：如果你當前至少有 $1$ 分，可以使用代幣 $i$，獲得 $tokens[i]$ 點 能量，並失去 $1$ 分。
• 在使用 任意 數量的代幣後，返回我們可以得到的最大 分數。

思路：貪婪(Greedy) + 排序(Sorting) + 雙指標(Two Pointers)

• 基於貪婪思路，在正面朝上使用代幣時，我們應該選擇 能量最小 的代幣，而在反面朝下使用代幣時，我們應該選擇 能量最大 的代幣。
• 因此，我們可以對代幣進行排序，然後使用 雙指標 來維護當前應該使用的代幣。
• 只要能量足夠，我們就朝上使用代幣，否則我們朝下使用代幣嘗試恢復能量。而答案只有在朝上使用代幣時才有可能更新。
• 時間複雜度：$O(n\log n)$ ，其中 $n$ 為代幣的數量。
• 空間複雜度：$O(n)$ ，排序需要額外的空間。

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        n = len(tokens)
        if n == 0:
            return 0
        tokens.sort()
        if power < tokens[0]: # 不能使用代幣
            return 0
        left, right = 0, n - 1
        ans = score = 0
        while left <= right:
            if power < tokens[left]: # 能量不夠朝上使用代幣，則嘗試朝下使用代幣恢復能量
                if score > 0:
                    score -= 1
                    power += tokens[right]
                    right -= 1
                else:
                    break
            else: # 可以朝上使用代幣
                score += 1
                power -= tokens[left]
                left += 1
                ans = max(ans, score)
        return ans

---

2024-03-05

🟡 1976. Number of Ways to Arrive at Destination 2095

題意

• 給定一個無向圖，圖中有 $n$ 個節點，從節點 $0$ 出發，目標是到達節點 $n-1$。
• 給定一個整數 $n$ 和二維整數陣列 $roads$，其中 $roads[i] = [u_i, v_i, time_i]$ 表示節點 $u_i$ 和 $v_i$ 之間有一條需要花費 $time_i$ 時間才能通過的道路。
• 求花費 最少時間 到達目的地的 方法數，答案對 $10^9 + 7$ 取模後返回。

思路：Dijsktra + Priority Queue (Heap) + DP

• 用 $dist[i]$ 表示從節點 $0$ 到節點 $i$ 的最短路徑長度。以Dijkstra演算法求出最短路徑，同時用優先佇列(Heap)來維護最短路徑。
• 在求最短路徑的同時，我們可以用DP的方式計算到達每個節點的方法數。用 $ans[i]$ 表示到達節點 $i$ 的方法數。
  • 在遇到長度更短的路徑時，即 $dist[u] + g[u][v] < dist[v]$ 時，代表到達 $v$ 的最短路徑必需經過 $u$，且方法數等於到達 $u$ 的方法數。
  • 如果 $dist[u] + g[u][v] = dist[v]$，則 $ans[v] += ans[u]$，代表到達 $v$ 的最短路徑也能經過 $u$，故累加方法數。
• 最後返回 $ans[n-1]$ 即可。
• 時間複雜度：$O(m \log m)$，其中 $m$ 為邊的數量。
• 空間複雜度：$O(m)$

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        g = [[float("inf") for _ in range(n)] for _ in range(n)]
        adj = [[] for _ in range(n)]
        for u, v, w in roads:
            g[u][v] = g[v][u] = w
            adj[u].append(v)
            adj[v].append(u)
        for i in range(n):
            g[i][i] = 0
        dist = [float("inf")] * n
        dist[0] = 0
        ans = [0] * n # ans[i] 表示以最短路到達 i 的方案數
        ans[0] = 1
        hp = [(0, 0)] # dist, node
        while hp:
            d, u = heappop(hp)
            if d > dist[u]:
                continue
            for v in adj[u]:
                t = d + g[u][v]
                if t < dist[v]: # 長度更短，從來源轉移
                    dist[v] = t
                    ans[v] = ans[u]
                    heappush(hp, (t, v))
                elif t == dist[v]: # 長度相同，累加
                    ans[v] = (ans[u] + ans[v]) % MOD
        return ans[-1]

---

🟡 1750. Minimum Length of String After Deleting Similar Ends 1502

Now only code is provided, no explanation is given temporarily.

題意

• 給定一個只包含字元 'a'、'b' 和 'c' 的字串 $s$，你可以執行以下操作任意次：
  1. 選擇字串 s 一個 非空 的前綴，這個前綴的所有字元都相同。
  2. 選擇字串 s 一個 非空 的後綴，這個後綴的所有字元都相同。
  3. 前綴和後綴在字串中任何位置都不能有交集。
  4. 前綴和後綴包含的所有字元都要相同。
  5. 同時刪除前綴和後綴。
• 返回執行上述操作任意次數（可能為0次）後字串 s 的 最小長度 。

思路：雙指標(Two Pointers)

• 由於目標是由相同字元的前綴和後綴，所以我們可以從頭尾開始枚舉，每次刪除相同的字元，直到遇到不同的字元為止。
• 用兩個指標 $left$ 和 $right$ 分別指向頭尾，當 $s[left] == s[right]$ 時，則 $left$ 往右移動， $right$ 往左移動，直到 $s[left] \neq s[right]$ 為止，最後答案為剩餘長度 $right - left + 1$。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$

class Solution:
    def minimumLength(self, s: str) -> int:
        n = len(s)
        left, right = 0, n - 1
        while left < right and s[left] == s[right]: # 存在由相同字元構成的前綴和後綴
            ch = s[left]
            while left <= right and s[left] == ch: # 刪除由 ch 構成的前綴
                left += 1
            while left <= right and s[right] == ch: # 刪除由 ch 構成的後綴
                right -= 1
        return right - left + 1

---

2024-03-06

🟢 2917. Find the K-or of an Array 1389

題意

• 給定一個下標從 $0$ 開始的整數陣列 $nums$ 和一個整數 $k$ 。
• 定義 $nums$ 的 K-or 是滿足以下條件的非負整數：
  • 只有在 $nums$ 中，至少存在 $k$ 個元素的第 $i$ 位值為 $1$ ，那麼 $K-or$ 中的第 $i$ 位的值才是 $1$ 。
• 返回 $nums$ 的 $K-or$ 值。

思路：位運算(Bit Manipulation)

• 逐位遍歷所有位元，計算每個位元的 $1$ 的個數，如果大於等於 $k$ ，則將答案的該位元設為 $1$ 。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$

class Solution:
    def findKOr(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = 0
        for i in range(31):
            mask = 1 << i
            cnt = 0
            for x in nums:
                if x & mask:
                    cnt += 1
            if cnt >= k:
                ans |= mask
        return ans

---

🟢 141. Linked List Cycle

題意

• 給定一個 鏈結串列(Linked List) 的頭節點 $head$ ，判斷鏈結串列中是否有 環(cycle) 。
• 如果鏈結串列中有某個節點，可以透過連續追蹤 next 指標再次到達，則鏈結串列中存在環(cycle)。
• 如果鏈結串列中存在環，則返回 $true$ ；否則，返回 $false$ 。

思路：雙指標(Two Pointers)中的快慢指標

• 將 $slow$ 和 $fast$ 兩個指標初始化為 $head$ ，當 $slow$ 每次走一步時，$fast$ 每次走兩步。
• 若 $fast$ 可以走到結尾，則表示沒有環；若 $slow$ 和 $fast$ 相遇，則表示有環。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if (slow == fast): # 相遇
                return True
        return False

---

2024-03-07

🟡 2575. Find the Divisibility Array of a String 1541

題意

• 給定一個長度為 $n$ ，下標從 $0$ 開始的字串 $word$ ，由 $0$ 到 $9$ 的數字組成，以及一個正整數 $m$ 。
• $word$ 的 可整除陣列(Divisibility Array) $div$ 是一個長度為 $n$ 的整數陣列，並滿足：
  • 如果 $word[0,...,i]$ 所表示的 數值 能被 $m$ 整除，$div[i] = 1$
  • 否則，$div[i] = 0$
• 返回 $word$ 的可整除陣列。

思路：數學(Math)、取模運算(Modulo Operation)

• 考慮 $word$ 的第 $1$ 個字元所表示的整數 $a$，以及第 $2$ 個字元所表示的整數 $b$，則 $word$ 的前 $2$ 個字元所表示的整數為 $a \times 10 + b$。
• 而基於取模運算的性質， $(a \times 10 + b) \mod m$ 等同為 $(a \mod m \times 10 + b) \mod m$。
• 故我們可以使用遞迴式計算 $word$ 的可整除陣列。令 $cur = 0$ 表示目前的數值取模 $m$ 後的結果，且 $cur = (cur \times 10 + \text{int}(word[i])) \mod m$，則 $div[i] = 1$ 若 $cur = 0$。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$

class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        n = len(word)
        ans = [0] * n
        cur = 0
        for i, ch in enumerate(word):
            cur = (cur * 10 + int(ch)) % m
            ans[i] = 1 if cur == 0 else 0
        return ans

---

🟢 876. Middle of the Linked List 1232

題意

• 給定 鏈結串列(Linked List) 的頭節點 $head$，返回該鏈結串列的中間節點。
• 如果有兩個中間節點，則返回第二個中間節點。

思路：雙指標(Two Pointers)中的快慢指標

• 為找到中間節點，可以使用快慢指標的方法，讓快指標每次走兩步，慢指標每次走一步，當快指標走到結尾時，慢指標就會走到中間節點。
• 但需要注意的是，當鏈結串列的長度為偶數時，慢指標需要走到第二個中間節點，因此迴圈成立條件為 while fast and fast.next。
• 可以將範例加上最後的 NULL 節點後，畫圖會更容易理解，也可以參考下面的參考資料。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

參考資料

• 快慢指针（注意链表长度为偶数时，返回第 2 个结点的细节）

---

2024-03-08

🟡 2834. Find the Minimum Possible Sum of a Beautiful Array 1409

題意

• 給定兩個正整數 $n$ 和 $target$ 。
• 如果陣列 $nums$ 滿足以下條件，則稱其為 美麗的 ：
  • $nums.length == n$。
  • $nums$ 由兩兩互不相同的正整陣列成。
  • 在範圍 $[0, n-1]$ 內，不存在 兩個 不同 下標 $i$ 和 $j$ ，使得 $nums[i] + nums[j] == target$ 。
• 返回符合條件的美麗陣列所可能具備的 最小 和，並對 $10^9 + 7$ 取模。

思路：貪婪(Greedy) + 數學(Math)

• 這題在周賽時原本可以用模擬的方式使用 雜湊表(Hash Table) 解決，但是在調整測資的數據範圍後會 TLE ，故必需從數學的角度來解決。
• 題目要求構建一個正整數陣列、陣列中的數字兩兩不相等，且任兩個相加不等於 $target$。
• 由於要使得陣列中的和最小，因此基於貪婪的思想，我們應該優先將最小的數字放入陣列中。但若使用 $1$ 則不能使用 $target - 1$，因此對於小於 $target$ 的數字 $i$ ，只能添加到 $i = \text{floor}(target / 2)$，$[\text{floor}(target / 2) + 1, target - 1]$ 這個範圍的數字都不能使用。
• 為方便表示，令 $m = \text{floor}(target / 2)$
  • 若 $n \leq m$，則答案為 $1 + 2 + ... + n$；
  • 若 $n > m$，則答案為 $(1 + 2 + ... + m) + (target + (target + 1) + ... + (target + n - m - 1))$。
• 最後記得對 $10^9 + 7$ 取模即可。
• 時間複雜度：$O(1)$
• 空間複雜度：$O(1)$

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        MOD = 10 ** 9 + 7
        m = target // 2
        if n <= m:
            ans = n * (n + 1) // 2
        else:
            ans = m * (m + 1) // 2 + (target + target + n - m - 1) * (n - m) // 2
        return ans % MOD

---

🟢 3005. Count Elements With Maximum Frequency 1217

題意

• 給定一個由 正整數 組成的陣列 $nums$。返回 $nums$ 中 所有 具有 最大 頻率的元素的 總頻率。
• 元素的 頻率 是指該元素在陣列中出現的次數。

思路：雜湊表(Hash Table) 計數 兩次遍歷/一次遍歷

• 題意有點繞，舉例來看會比較好理解。若 $nums$ 中有兩個元素 $1$ 和 $2$ 的頻率都是 $3$，且 $3$ 為最高頻率，則答案為 $3 + 3 = 6$。
• 這題可以使用 雜湊表(Hash Table) $cnt$ 來計算每個元素的頻率，並找出最大頻率。再遍歷一次 $cnt$ ，將所有頻率等於最大頻率的元素的頻率相加即可。
• 也可以在計算頻率時同時維護最大頻率 $max_f$ 和答案 $ans$ ，這樣只需遍歷一次 $nums$ 。
• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        # return self.solve1(nums)
        return self.solve2(nums)
    def solve1(self, nums: List[int]) -> int: # 兩次遍歷
        cnt = Counter(nums)
        maxCnt = max(cnt.values())
        return sum([v for k, v in cnt.items() if v == maxCnt])
    def solve2(self, nums: List[int]) -> int: # 一次遍歷
        cnt = Counter()
        ans = max_f = 0
        for x in nums:
            cnt[x] += 1
            if cnt[x] > max_f:
                ans = max_f = cnt[x]
            elif cnt[x] == max_f:
                ans += cnt[x]
        return ans

---

2024-03-09

🔴 2386. Find the K-Sum of an Array 2648

看到 2648 分就知道自己高攀不起，果斷直接看題解。

題意

• 給定一個整數陣列 $nums$ 和一個 正 整數 $k$ 。你可以選擇陣列的任一 子序列 並對其全部元素求和。
• 定義陣列的 第 k 大和(K-Sum) 為：可以獲得的第 $k$ 個 最大 子序列和（子序列和允許出現重複）。
• 返回陣列的 第 k 大和 。
• 子序列是可以從另一個陣列中刪除一些或不刪除元素而得到的陣列，順序保持不變。
• 請 注意 ，空子序列的和視為 $0$ 。

思路：貪婪(Greedy) + 最小堆(Min Heap)

• 首先從 base cacse 開始思考，當 $k = 1$ 時，答案就是 $nums$ 中的非負數元素的總和 $s$ 。而為求出更小的答案，我們可以在 $s$ 的基礎上加上負數或是減去正數。為方便操作，在計算 $s$ 時，將負數變成正數，使得後面可以統一用減法。
• 再來思考 $k = 2$ 時，顯然是減去 $nums$ 中的最小的數字 (已經轉換成正數)，而 $k = 3$時，可以考慮直接在 $k = 2$ 的基礎上再減去第二小的數字，或是在 $k = 1$ 的基礎上減去第二小的數字，即在 $k = 2$ 的基礎上補回第一小的數字，再減去第二小的數字，從兩者中選擇最小的。
• 為使每次操作時都可以取到最小的元素和，可以對 $nums$ 做排序，並維護一個最小堆 $hp$，每次取出堆頂元素，即最小需刪除的元素和以及已經考慮到的元素下標，並根據取出的元素和進行操作，這個過程類似於 Dijkstra 演算法 。
• 時間複雜度：$O(n \log n + k \log k)$，其中 $n$ 為陣列 $nums$ 的長度，開銷在排序和堆操作上。
• 空間複雜度：$O(k)$，堆的大小。

class Solution:
    def kSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        s = 0 # 紀錄非負數的總和，即第1大和
        for i, x in enumerate(nums):
            if x >= 0:
                s += x
            else: # 使負數變成正數，要使第1大和變小可以加上負數或減去正數，這裡讓負數變成正數，使後面可以統一用減法
                nums[i] = -x
        nums.sort() # 由小到大排序

        ret = 0 # 要去除的元素和，初始化為0
        hp = [(nums[0], 0)] # (要去除的元素和, 已經考慮到的元素下標)，第一個考慮要去除的元素顯然是最小的元素
        for _ in range(2, k + 1):
            t, i = heappop(hp)
            ret = t
            if i == n - 1:
                continue
            heappush(hp, (t + nums[i + 1], i + 1)) # 保留nums[i]，加入nums[i+1]
            heappush(hp, (t - nums[i] + nums[i + 1], i + 1)) # 去除nums[i]，加入nums[i+1]
        return s - ret

類題

第 K 大 / 小

• 🟡 378. Kth Smallest Element in a Sorted Matrix
• 🔴 668. Kth Smallest Number in Multiplication Table
• 🟡 373. Find K Pairs with Smallest Sums
• 🔴 719. Find K-th Smallest Pair Distance
• 🟡 1201. Ugly Number III 2039
• 🔴 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows 2134
• 🟡 786. K-th Smallest Prime Fraction 2169
• 🔴 2040. Kth Smallest Product of Two Sorted Arrays 2518
• 1918. Kth Smallest Subarray Sum (Premium)

題單來自：@灵茶山艾府

參考資料

• 两种方法：二分答案+爆搜/最小堆（Python/Java/C++/Go/JS/Rust）

---

🟢 2540. Minimum Common Value 1250

題意

• 給定兩個整數陣列 $nums1$ 和 $nums2$，已按照 非遞減 順序排列，返回兩個陣列的 最小公共整數 。如果 $nums1$ 和 $nums2$ 中沒有共同的整數，則返回 $-1$。
• 如果一個整數在兩個陣列中都 至少出現一次，則該整數被視為 $nums1$ 和 $nums2$ 的 公共整數。

思路：集合(Set) / 雙指標(Two Pointers)

方法一：集合(Set)

• 直接將 $nums1$ 和 $nums2$ 轉換成集合，然後取交集，返回最小值即可，可以一行解決。
• 但上述解法沒有利用到 $nums1$ 和 $nums2$ 已經按照 非遞減 順序排列的性質，因此可以只將 $nums1$ 轉換成集合，然後遍歷 $nums2$，如果 $nums2$ 中的元素在 $nums1$ 中，則返回該元素，否則返回 $-1$。由於 $nums2$ 已經按照 非遞減 順序排列，因此第一個公共整數即為最小公共整數。
• 時間複雜度：$O(n + m)$，其中 $n$ 和 $m$ 分別為 $nums1$ 和 $nums2$ 的長度。
• 空間複雜度：$O(n)$

class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        # return min(set(nums1) & set(nums2), default=-1)
        nums1 = set(nums1)
        for x in nums2:
            if x in nums1:
                return x
        return -1

方法二：雙指標(Two Pointers)

• 若更加有效的利用 $nums1$ 和 $nums2$ 已經按照 非遞減 順序排列的性質，可以使用 雙指標 的方法，將空間複雜度降低到 $O(1)$。
• 用 $i$ 和 $j$ 分別指向 $nums1$ 和 $nums2$ 的開頭，遍歷 $nums2$ ，如果 $nums2[j] < nums1[i]$，則 $j$ 往右移動，否則如果 $nums2[j] > nums1[i]$，則 $i$ 往右移動，直到找到 $nums1[i] = nums2[j]$ ，或是 $i$ 或 $j$ 超出範圍。
• 時間複雜度：$O(n + m)$，其中 $n$ 和 $m$ 分別為 $nums1$ 和 $nums2$ 的長度。
• 空間複雜度：$O(1)$

class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        i, n = 0, len(nums1)
        for y in nums2:
            while i < n and nums1[i] < y: # 找到nums1[i] >= y
                i += 1
            if i < n and nums1[i] == y:
                return y
        return -1

---

2024-03-10

🟡 299. Bulls and Cows

題意

你正在和朋友玩 猜數字（Bulls and Cows） 遊戲，遊戲規則如下：

• 你寫下一個秘密數字，並要求你的朋友猜出這個數字是什麼。當你的朋友猜測時，你會提供一個包含下述信息的提示：
  • 猜測數字中有多少位屬於數字和確切位置都猜對了（稱為 Bulls(公牛) ）。
  • 有多少位屬於數字猜對了但是位置不對（稱為 Cows(奶牛) ）。也就是說，這次猜測中有多少位非公牛數字可以通過重新排列轉換成公牛數字。
• 給定一個秘密數字 $secret$ 和朋友猜測的數字 $guess$ ，請你根據 Bulls 和 Cows 的提示返回詳細信息。
• 提示應格式化成 "xAyB" ，其中 x 是 Bulls 的數量， y 是 Cows 的數量。
• 請注意，秘密數字和朋友猜測的數字可能包含重複的數字。

思路：計數(Counter)

• 遍歷 $secret$ 和 $guess$ ，計算 Bulls 的數量，即 $secret[i] == guess[i]$ 的數量；若 $secret[i] \neq guess[i]$，則將 $secret[i]$ 和 $guess[i]$ 的數量分別記錄在 $cnt_s$ 和 $cnt_g$ 中，其中 $cnt_s$ 和 $cnt_g$ 分別為 $secret$ 和 $guess$ 中每個數字的出現次數。
• 若 $cnt_s[i] < cnt_g[i]$ 則代表 $secret$ 中的 $i$ 出現次數小於 $guess$ 中的 $i$ 出現次數，則對於 $i$ 的 Cows 數量為 $cnt_s[i]$；否則對於 $i$ 的 Cows 數量為 $cnt_g[i]$。即對於每個數字 $i$，取 $cnt_s[i]$ 和 $cnt_g[i]$ 的最小值。將所有數字的 Cows 數量相加即為 $cows$ 的數量。
• 時間複雜度：$O(n)$，其中 $n$ 為 $secret$ 和 $guess$ 的長度。
• 空間複雜度：$O(1)$，由於數字的範圍固定為 $0$ 到 $9$ ，故為常數空間。

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        cnt_s = [0] * 10 # 每個數字應該出現的次數
        cnt_g = [0] * 10 # 每個數字實際出現的次數
        x = 0
        for s, g in zip(secret, guess):
            if s == g:
                x += 1
            else:
                cnt_s[int(s)] += 1
                cnt_g[int(g)] += 1
        y = sum([min(cnt_s[i], cnt_g[i]) for i in range(10)])
        return f'{x}A{y}B'

---

🟢 349. Intersection of Two Arrays

題意

• 給定兩個整數陣列 $nums1$ 和 $nums2$ ，返回它們的 交集 。結果中的每個元素必須是 唯一 的，可以按 任意順序 返回。

思路：集合(Set)

• 將 $nums1$ 和 $nums2$ 轉換成集合，取交集即可。
• 時間複雜度：$O(n + m)$，其中 $n$ 和 $m$ 分別為 $nums1$ 和 $nums2$ 的長度。
• 空間複雜度：$O(n + m)$

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

---