LeetCode 2024/02/11-2024/02/20 每日一題

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

All problems solved by python

---

2024-02-11

🟢 144. Binary Tree Preorder Traversal

題意

• 給定一個Binary Tree的根節點 $root$ ，返回其 preorder traversal 的結果。

思路：遞迴(Recursion)

• 使用遞迴的方式進行中序遍歷，定義一個遞迴函數 preorder，並且返回遍歷的結果。
• 時間複雜度：$O(n)$，其中 $n$ 為二叉樹的節點數。
• 空間複雜度：$O(n)$。

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def preorder(root):
            if not root:
                return []
            return [root.val] + preorder(root.left) + preorder(root.right)
        return preorder(root)

---

🔴 1463. Cherry Pickup II 1957

題意

• 給定一個大小為 $rows \times cols$ 的矩陣 $grid$ 來表示一塊地。 $grid[i][j]$ 的值表示在 $(i, j)$ 位置可以獲得的櫻桃數目。
• 有兩個機器人幫忙收集櫻桃，機器人 1 從左上角格子 $(0,0)$ 出發，機器人 2 從右上角格子 $(0, cols-1)$ 出發，返回兩個機器人最多能收集的櫻桃數目。
  • 對於在 $(i, j)$ 位置的機器人，可以移動到 $(i+1, j-1)$，$(i+1, j)$ 或 $(i+1, j+1)$。
  • 當兩個機器人在同一個位置時，只有一個機器人可以收集櫻桃。
  • 機器人不能移動到 $grid$ 外面。
  • 機器人最後都要到達最底下一行。

思路：動態規劃(Dynamic Programming, DP)

• 令 $dp(i, j1, j2)$ 表示在第 $i$ 行，機器人 1 在 $j1$ 位置，機器人 2 在 $j2$ 位置時，能夠摘到的最大櫻桃數。
• 使用遞迴的方式進行狀態轉移，並且使用 @cache 進行記憶化搜索。
  • 由於機器人只能往下移動，所以對每個機器人都只需要考慮下一行的三個位置，因此總共有9種可能，且遞迴的終止條件為 $i == m$。
  • 由於兩個機器人都在同一個位置時，只有一個機器人可以收集櫻桃，此情況下的結果必小於兩個機器人分別在不同位置時的結果，所以不需要考慮這種情況。
  • $dp(0, 0, n-1)$ 即為答案。
• 時間複雜度：$O(m \times n^2)$。總共有 $m \times n^2$ 種狀態，每個狀態需要從 9 種可能中選擇最大值。
• 空間複雜度：$O(m \times n^2)$。

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        @cache # Memoization
        def dfs(i, j1, j2):
            if i == m: return 0
            res = -float("inf")
            for y1 in [j1 - 1, j1, j1 + 1]: # y1, y2 各有 3 種可能的位置
                for y2 in [j2 - 1, j2, j2 + 1]:
                    if 0 <= y1 < n and 0 <= y2 < n and y1 != y2: # 在範圍內且不重疊
                        res = max(res, dfs(i + 1, y1, y2))
            return grid[i][j1] + grid[i][j2] + res
        return dfs(0, 0, n - 1)

---

2024-02-12

🟢 145. Binary Tree Postorder Traversal

題意

• 給定一個Binary Tree的根節點 $root$ ，返回其 postorder traversal 的結果。

思路：遞迴(Recursion)

• 使用遞迴的方式進行中序遍歷，定義一個遞迴函數 postorder，並且返回遍歷的結果。
• 時間複雜度：$O(n)$，其中 $n$ 為二叉樹的節點數。
• 空間複雜度：$O(n)$。

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def postorder(root):
            if not root:
                return []
            return postorder(root.left) + postorder(root.right) + [root.val]
        return postorder(root)

---

🟢 169. Majority Element

題意

• 給定一個大小為 $n$ 的一維陣列 $nums$ ，返回其中的多數元素(Majority Element)。
  • __多數元素(Majority Element)++ 是指在陣列中出現次數 大於 $\lfloor \frac{n}{2} \rfloor$ 的元素。
• 給定的陣列是非空的，且總是存在多數元素。

思路：雜湊表(Hash Table) / Boyer-Moore Voting Algorithm

方法一：雜湊表(Hash Table)

• 統計每個元素出現的次數，若統計時發現某個元素出現次數大於 $\lfloor \frac{n}{2} \rfloor$，則返回該元素。
• 時間複雜度：$O(n)$，其中 $n$ 為陣列的長度。
• 空間複雜度：$O(n)$。

方法二：Boyer-Moore Voting Algorithm

• 如果把主要元素計為 $+1$，把其他元素計為 $-1$，將它們全部加起來，顯然和大於 $0$。
• 根據這個思路，我們可以維護一個主要元素的候選人 $candidate$ 和其出現的次數 $cnt$。
• 遍歷 $nums$ 中的所有元素，對於每個元素 $x$ ，若 $cnt$ 的值為 $0$，則將 $x$ 的值賦予 $candidate$ ，隨後判斷 $x$：
  • 若 $x$ 與 $candidate$ 相等，則計數器 $cnt$ 的值增加 $1$；
  • 若 $x$ 與 $candidate$ 不等，則計數器 $cnt$ 的值減少 $1$。
• 當 $cnt$ 的值為 $0$ 時，存在兩種情況：
  • $candidate$ 不是多數元素，則顯然需要嘗試選擇 $x$ 作為新的候選人；
  • $candidate$ 是多數元素，則捨去 $x$ 之前的所有元素，$candidate$ 仍然是多數元素，最終仍會被選為候選人，不影響結果。
• 最終的 $candidate$ 即為整個陣列的多數元素。
• 時間複雜度：$O(n)$，其中 $n$ 為陣列的長度。
• 空間複雜度：$O(1)$。

Hash TableBoyer-Moore

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = defaultdict(int)
        for num in nums:
            cnt[num] += 1
            if cnt[num] > len(nums) // 2:
                return num

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = 0
        candidate = None
        for num in nums:
            if cnt == 0:
                candidate = num
            cnt += 1 if num == candidate else -1
        return candidate

---

2024-02-13

🔴 987. Vertical Order Traversal of a Binary Tree 1676

題意

• 給定一個Binary Tree的根節點 $root$ ，返回其 垂序遍歷(Vertical Order Traversal) 。
• 令 $root$ 位於 $(0, 0)$ ，且對於每個位於 $(row, col)$ 的節點而言，其左右子節點分別位於 $(row + 1, col - 1)$ 和 $(row + 1, col + 1)$。
• 垂序遍歷(Vertical Order Traversal) 是從最左邊的column開始，至最右邊的column結束，從上到下的順序列表。
  • 相同位置上可能存在多個節點，在這種情況下，需要按照節點的值由小到大進行排序。

思路：BFS/DFS + 雜湊表(Hash Table)

• 首先以BFS或DFS紀錄每個節點的位置，並使用Hash Table將相同column的節點存放在同一個list中，保存 $(row, val)$ 的tuple，最後對每個column的list的節點進行排序即可。
• 時間複雜度：$O(n)$，其中 $n$ 為二叉樹的節點數。
• 空間複雜度：$O(n)$。

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = defaultdict(list)

        def bfs():
            q = deque([(root, 0, 0)])
            while q:
                node, x, y = q.popleft()
                if node:
                    ans[y].append((x, node.val))
                    q.append((node.left, x+1, y-1))
                    q.append((node.right, x+1, y+1))

        def dfs(node, x, y):
            if node:
                ans[y].append((x, node.val))
                dfs(node.left, x+1, y-1)
                dfs(node.right, x+1, y+1)

        # bfs()
        dfs(root, 0, 0)
        return [[val for _, val in sorted(ans[x])] for x in sorted(ans)]

---

🟢 2108. Find First Palindromic String in the Array 1216

題意

• 給定一個二維字串陣列 $words$ ，返回陣列中的 第一個回文(Palindromic)字串。如果不存在滿足要求的字串，則返回一個空字串 ""。

思路

• 定義一個函數 isPalindrome 來判斷字串是否為回文字串，並對每個字串進行判斷即可。
• 時間複雜度：$O(n \cdot m)$，其中 $n$ 為陣列的長度，$m$ 為陣列中字串的平均長度。
• 空間複雜度：$O(1)$。

class Solution:
    def firstPalindrome(self, words: List[str]) -> str:
        def isPalindrome(s):
            n = len(s)
            for i in range(n//2):
                if s[i] != s[n-1-i]:
                    return False
            return True
        for word in words:
            if isPalindrome(word):
                return word
        return ""

---

2024-02-14

🟡 102. Binary Tree Level Order Traversal

題意

• 給定一個Binary Tree的根節點 $root$ ，返回其 層序遍歷(Level Order Traversal) (即逐層地，從左到右訪問所有節點) 的結果。

思路：BFS

• level order traversal 即使用BFS進行遍歷，維護一個 queue 來存放每一層的節點，並且記錄每一層的節點的值。
• 時間複雜度：$O(n)$，其中 $n$ 為二叉樹的節點數。
• 空間複雜度：$O(n)$。

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        if not root: return ans
        q = deque([root])
        while q:
            cur = []
            for _ in range(len(q)):
                node = q.popleft()
                cur.append(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            ans.append(cur)
        return ans

---

🟡 2149. Rearrange Array Elements by Sign 1236

題意

• 給定一個下標從 $0$ 開始的整數陣列 $nums$ ，陣列長度為 偶數 ，由數目相等的正整數和負整陣列成。
• 重新排列 $nums$ 中的元素，使修改後的陣列滿足以下性質：
  1. 相鄰 的兩個整數 符號相反
  2. 對於符號相同的所有整數，保留 它們在 $nums$ 中原本的 順序 。
  3. 重新排列後，陣列的第一個元素為正整數。
• 返回修改後的陣列。

思路：雙指標(Two pointers)

• 由於要維持原本的順序，所以可以使用兩個 pointer $pos$ 和 $neg$ 分別指向正整數和負整數的位置。
• 在找到下一個正整數和負整數時，將它們分別放到答案陣列中。
• 時間複雜度：$O(n)$，其中 $n$ 為陣列的長度。
• 空間複雜度：$O(1)$，不計 $ans$ 使用的空間。

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        pos, neg = 0, 0 # Two pointers
        for i in range(n//2):
            while pos < n and nums[pos] < 0:
                pos += 1
            while neg < n and nums[neg] > 0:
                neg += 1
            ans[i*2] = nums[pos]
            ans[i*2+1] = nums[neg]
            pos += 1
            neg += 1
        return ans

---

2024-02-15

🟡 107. Binary Tree Level Order Traversal II

題意

• 給定一個Binary Tree的根節點 $root$ ，返回其 自底向上的層序遍歷(bottom-up level order traversal) 的結果。

思路：BFS

• level order traversal 即使用BFS進行遍歷，維護一個 queue 來存放每一層的節點，並且記錄每一層的節點的值。
• 和 102. Binary Tree Level Order Traversal 的 差別只在於最後需將結果反轉 。
• 時間複雜度：$O(n)$，其中 $n$ 為二叉樹的節點數。
• 空間複雜度：$O(n)$。

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        if not root: return ans
        q = deque([root])
        while q:
            cur = []
            for _ in range(len(q)):
                node = q.popleft()
                cur.append(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            ans.append(cur)
        return ans[::-1] 

---

🟡 2971. Find Polygon With the Largest Perimeter 1521

LeetCode Biweekly Contest 120 解題紀錄

題意

• 給定一個長度為 $n$ 的正整數陣列 $nums$，表示可以選擇的邊長。
• 多邊形(Polygon)是一個至少有 $3$ 個邊的封閉平面圖形，且多邊形的最長邊小於其其他邊的總和。
• 如果有 $k$ ($k \geq 3$) 個正整數 $a_1$, $a_2$, $a_3$, …, $a_k$，其中 $a_1 \leq a_2 \leq a_3 \leq ... \leq a_k$ 且 $a_1 + a_2 + a_3 + ... + a_{k-1} > a_k$，那麼 必存在 一個具有 $k$ 邊的多邊形，其邊長為 $a_1$, $a_2$, $a_3$, …, $a_k$。
• 若 $nums$ 中的數字可以形成一個多邊形，返回能構造出的多邊形之 最大周長。若無法構造任何多邊形，返回 $-1$。

思路：排序(Sorting) + 枚舉(Enumeration)

• 由於題目已經說明了構成多邊形的條件，因此只要枚舉多邊形中最大的邊長，然後檢查是否能構成多邊形即可。我們可以先將 $nums$ 由小到大排序，然後從最大的邊長開始枚舉。
• 賽時用了前綴和來檢查是否大於其他邊的總和，但其實不需要，只需要先計算出所有邊的總和 $s$，然後檢查 $s - nums[i] > nums[i]$ ，再扣除當前邊長即可。
• 時間複雜度 $O(n \log n)$ ，排序的時間複雜度為 $O(n \log n)$，枚舉的時間複雜度為 $O(n)$。
• 空間複雜度 $O(1)$。

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        # pre = list(accumulate(nums, initial=0))
        s = sum(nums)
        for i in range(n - 1, 1, -1):
            # if pre[i] > nums[i]:
            #     return pre[i] + nums[i]
            if s  > 2 * nums[i]: # s - nums[i] > nums[i]
                return s
            s -= nums[i]
        return -1

---

2024-02-16

🟡 103. Binary Tree Zigzag Level Order Traversal

題意

• 給定一個Binary Tree的根節點 $root$ ，返回其 鋸齒形層序遍歷(zigzag level order traversal) （即先從左往右，再從右往左進行下一層遍歷）的結果。

思路：BFS

• 以 $root$ 節點為 $0$ 層，所求即為在level order traversal的基礎上，另外維護 $lvl$，對於奇數層的結果進行反轉即可。
• 時間複雜度：$O(n)$，其中 $n$ 為二叉樹的節點數。
• 空間複雜度：$O(n)$。

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        if not root:
            return ans
        lvl = 0 # level
        q = deque([root])
        while q:
            cur = []
            for _ in range(len(q)):
                node = q.popleft()
                cur.append(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            if lvl & 1: # if lvl % 2 != 0
                cur.reverse()
            ans.append(cur)
            lvl += 1
        return ans

---

🟡 1481. Least Number of Unique Integers after K Removals 1284

題意

• 給定一個整數陣列 $arr$ 和一個整數 $k$ ，從陣列中移除恰好 $k$ 個元素，返回移除後陣列中不同整數的最少數目。

思路：貪心(Greedy) + Counter

• 為使移除後陣列中不同整數的數量最少，可以基於 Greedy 的思想，先使用 Counter 計算每個整數出現的次數，依次移除出現次數最小的整數。
• 時間複雜度：$O(n \log n)$，其中 $n$ 為陣列的長度。
• 空間複雜度：$O(n)$。

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = Counter(arr) 
        keys = sorted(cnt.keys(), key=cnt.get)
        i = 0
        while k:
            if k >= cnt[keys[i]]:
                k -= cnt[keys[i]]
                i += 1
            else:
                break
        return len(keys) - i

---

2024-02-17

🟡 429. N-ary Tree Level Order Traversal

題意

• 給定一個 n-ary tree，返回其 層序遍歷(level order traversal) （即由左至右，逐層遍歷）的結果。

思路：BFS

• 和Binary Tree的level order traversal相同，差別在需考慮每個節點的所有子節點。

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []
        ans = []
        q = deque([root])
        while q:
            cur = []
            for _ in range(len(q)):
                node = q.popleft()
                cur.append(node.val)
                for child in node.children:
                    q.append(child)
            ans.append(cur)
        return ans

---

🟡 1642. Furthest Building You Can Reach 1962

題意

• 給定一個整數陣列 $heights$ （下標從 0 開始），表示建築物的高度；給定 $bricks$ 和 $ladders$ ，表示磚頭和梯子的數量。
• 從下標為 $0$ 的建築物開始，不斷向後面的建築物移動，期間可能會用到磚頭或梯子。
• 當從建築物 $i$ 移動到建築物 $i+1$ 時：
  • 若目前建築物的高度 大於或等於 下一棟建築物的高度，則不需要梯子或磚頭；
  • 若目前建築的高度 小於 下一個建築物的高度，則可以使用 一架梯子 或 (h[i+1] - h[i]) 個磚頭。
• 返回你可以到達的最遠建築物的下標。（注意下標從 0 開始）

思路：Greedy + Heap (Priority Queue)

• 令 $delta_h = h[i+1] - h[i]$ 表示相鄰建築物的高度差，我們可以使用梯子來無條件地到達下一個建築物，而使用磚頭則需要消耗 $delta_h$ 個磚頭。
• 基於 Greedy 的思想，因為使用梯子可以無條件地到達下一個建築物，所以我們應該儘量在相差較大的建築物之間使用梯子，而在相差較小的建築物之間使用磚頭。
• 在考慮的時候可以優先使用梯子，當梯子用完後再把 $delta_h$ 最小的地方用磚頭代替，也就是當 $hp$ 的大小超過 $ladders$ 時，我們需要把最小的 $delta_h$ 用磚頭代替，因此我們可以使用 Min Heap 來維護需要使用梯子的 $delta_h$ 。
• 此外，我們也需使用 $sum_h$ 來維護使用磚頭的總數，當 $sum_h > bricks$ 時，表示磚頭不夠用，不能到達下一個建築物，此時返回當前的下標。
• 時間複雜度：$O(n \log ladders)$，其中 $n$ 為陣列的長度。
• 空間複雜度：$O(ladders)$，即 $hp$ 的大小。

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        n = len(heights)
        hp = [] # min heap
        sum_h = 0 # sum of bricks
        for i in range(1, n):
            d = heights[i] - heights[i - 1] # delta_h
            if d > 0:
                heappush(hp, d)
                if len(hp) > ladders: # 最小的 delta_h 不用 ladder，改用 brick 代替
                    sum_h += heappop(hp)
                if sum_h > bricks: # bricks 不夠用
                    return i - 1 # 不能到達第 i 個建築物，即可以到達 i - 1 個建築物
        return n - 1 # 可以到達最後一個建築物

---

2024-02-18

🟢 589. N-ary Tree Preorder Traversal

題意

• 給定一個 n-ary tree，返回其 前序遍歷(preorder traversal) 的結果。

思路：DFS

• 和Binary Tree的preorder traversal相同，差別在遞迴時需考慮每個節點的所有子節點。
• 時間複雜度：$O(n)$，其中 $n$ 為二叉樹的節點數。
• 空間複雜度：$O(n)$。

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        def dfs(node):
            res = []
            if node is None:
                return res
            res = [node.val]
            for child in node.children:
                res += dfs(child)
            return res
        return dfs(root)

---

🔴 2402. Meeting Rooms III 2093

題意

• 給定一個整數 $n$ ，表示有編號從 $0$ 到 $n - 1$ 的 $n$ 個會議室。
• 給定一個二維整數陣列 $meetings$ ，其中 $meetings[i] = [start_i, end_i]$ 表示一場會議將會在左閉右開 時間區間 $[start_i, end_i)$ 舉辦，其中所有 $start_i$ 的值 互不相同 。
• 分配會議室的規則如下：
  1. 每場會議都會在未佔用且 編號最小 的會議室舉行。
  2. 如果沒有可用的會議室，會議將會延期，直到有空閒的會議室。 延期會議的持續時間和原會議持續時間相同 。
  3. 當會議室處於未佔用狀態時，將會優先提供給原 開始時間更早 的會議。
• 返回舉辦最多會議的 會議室編號 ，如果存在多個會議室符合此條件，則返回 編號最小 的會議室。

思路：Simulation + Heap (Priority Queue)

• 基於規則3，我們可以從開始時間最早的會議開始進行模擬，而根據題意，沒有兩場會議的開始時間相同，因此我們可以直接將會議 按照開始時間進行排序
• 根據規則1，我們需要找到可用會議室中 編號最小 的會議室，而根據規則2，我們需要找到 最早結束 的會議室，因此我們可以使用 Heap (Priority Queue) 來維護每個會議室的結束時間和編號。
• 由開始時間由小到大遍歷每個會議，當到某個會議開始時間 $start_i$ 時，會有以下兩種情況：
  1. 若不存在可用會議室，即最早結束的會議室的結束時間 $> start_i$，則需要延期會議，直到有空閒的會議室，也就是取出 最早結束 的會議室即可。
  2. 若有可用會議室，即最早結束的會議室的結束時間 $< start_i$，為滿足規則1，可將該會議室的結束時間更新為當前會議的開始時間 ，此時取出的將會是編號最小的會議室。
• 在上述操作後，不管遇到哪種情況，都可以直接令該會議的結束時間 $ed = t + d$ ，其中 $d$ 為會議持續時間，$t$ 為最早結束的會議室的結束時間。
• 最後，我們只需遍歷每個會議室的使用次數，找到使用次數最多的會議室即可。
• 時間複雜度：$O(m \log m)$，其中 $m$ 為 $meetings$ 的長度，為排序的時間複雜度。
• 空間複雜度：$O(n)$。

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort() # 依照會議開始時間排序
        cnt = [0] * (n) # 每個會議室的使用次數
        hp = [(0, i) for i in range(n)] # 維護每個會議室的結束時間，初始化為0，表示每個會議室在時間0時都是可用的
        for st, ed in meetings:
            d = ed - st # 會議持續時間
            while hp and hp[0][0] < st: # 為滿足規則1，可將該會議室的結束時間更新為當前會議的開始時間
                _, tmp_idx = heappop(hp)
                heappush(hp, (st, tmp_idx))
            t, idx = heappop(hp) # 取出最早結束的會議室編號
            ed = t + d # 更新該會議室的結束時間
            heappush(hp, (ed, idx)) # 將該會議的結束時間和使用的會議室編號加入heap
            cnt[idx] += 1
        ans = 0
        for i, v in enumerate(cnt):
            if v > cnt[ans]:
                ans = i
        return ans

---

2024-02-19

🟢 590. N-ary Tree Postorder Traversal

題意

• 給定一個 n-ary tree，返回其 後序遍歷(postorder traversal) 的結果。

思路：DFS

• 和Binary Tree的postorder traversal相同，差別在遞迴時需考慮每個節點的所有子節點。
• 時間複雜度：$O(n)$，其中 $n$ 為二叉樹的節點數。
• 空間複雜度：$O(n)$。

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        def dfs(node):
            res = []
            if node is None:
                return res
            res = []
            for child in node.children:
                res += dfs(child)
            res.append(node.val)
            return res
        return dfs(root)

---

🟢 231. Power of Two

題意

• 給定一個整數 $n$ ，判斷其是否是 $2$ 的冪次方。 如果是，返回 true ；否則，返回 false 。
• 如果存在一個整數 $x$ 使得 $n == 2^x$ ，則認為 $n$ 是 $2$ 的冪次方。

思路：位運算(Bit Manipulation)

• 在二進制表示中，$2$ 的冪次方的數字只有一個 $1$ ，例如 $2^3 = 8$ 的二進制表示為 1000 ，$2^4 = 16$ 的二進制表示為 10000 。
• 因此我們可以判斷最低位的 $1$ 是否為唯一的 $1$ 即可，可以使用以下兩種方法：
  • $n \And (n-1)$ 可以消除最低位的 $1$ ，如果 $n$ 是 $2$ 的冪次方，則 $n \And (n-1) = 0$ 。
  • $n \And -n$ 可以得到最低位的 $1$ ，如果 $n$ 是 $2$ 的冪次方，則 $n \And -n = n$ 。
• 時間複雜度：$O(1)$。
• 空間複雜度：$O(1)$。

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0
        # return n > 0 and (n & -n) == n  

參考資料

• 分享｜从集合论到位运算，常见位运算技巧分类总结！

---

2024-02-20

🟡 105. Construct Binary Tree from Preorder and Inorder Traversal

題意

• 給定兩個整數陣列 $preorder$ 和 $inorder$ ，其中 $preorder$ 是二元樹的 前序(preorder)遍歷， $inorder$ 是同一棵樹的中序(inorder)遍歷。
• 依照給定的 $preorder$ 和 $inorder$ ，構造出二元樹並返回其根節點 $root$ 。

思路：遞迴(Recursion)

• preorder 和 inorder 可以構建出唯一 的Binary Tree，preorder 的第一個元素 為根節點，並且它將 inorder 分為左右兩個子樹。
• 對於給定的 $preorder$ 和 $inorder$ ，我們可以使用遞迴的方式來構建二叉樹，具體步驟如下：
  1. $root$ 是 $preorder$ 的第一個元素，並且它將 $inorder$ 分為左右兩個子樹。
  2. 因此可以找到 $root$ 在 $inorder$ 中的位置 $idx$ ，且 $idx$ 同時也是左子樹的大小。
  3. 遞迴構建左右子樹。
     • 左子樹：$preorder[1:idx+1]$ 和 $inorder[:idx]$
     • 右子樹：$preorder[idx+1:]$ 和 $inorder[idx+1:]$
• 時間複雜度：$O(n^2)$，其中 $n$ 為二叉樹的節點數，每次查找 $root$ 在 $inorder$ 中的位置需要 $O(n)$ 的時間。
• 空間複雜度：$O(n^2)$，最壞情況下，每次遞迴都需要 $O(n)$ 的空間。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if len(preorder) == 0:
            return None
        root = TreeNode(preorder[0])
        idx = inorder.index(preorder[0]) # let idx be the index of root in inorder, which is also the size of left subtree
        root.left = self.buildTree(preorder[1:idx+1], inorder[:idx])
        root.right = self.buildTree(preorder[idx+1:], inorder[idx+1:])
        return root

---

🟢 268. Missing Number

題意

• 給定一個包含 $[0, n]$ 中 $n$ 個數的陣列 $nums$ ，返回 $[0, n]$ 這個範圍內 沒有出現 在陣列中的那個數。

思路：數學(Math) / 排序(Sorting) / 雜湊表(Hash Table) / 位運算(Bit Manipulation)

方法一：數學(Math)

• 計算出 $[0, n]$ 的總和，然後減去陣列中所有數的總和，即可得到缺失的數。
• 時間複雜度：$O(n)$。
• 空間複雜度：$O(1)$。

方法二：排序(Sorting)

• 將陣列排序，然後遍歷陣列，找到缺失的數。
• 時間複雜度：$O(n \log n)$。
• 空間複雜度：$O(1)$。

方法三：雜湊表(Hash Table)

• 使用雜湊表來記錄陣列中的所有數，然後遍歷 $[0, n]$ ，找到缺失的數。
• 時間複雜度：$O(n)$。
• 空間複雜度：$O(n)$。

方法四：位運算(Bit Manipulation)

• 利用 $XOR$ 運算的性質，即 $a \oplus a = 0$ 且 $a \oplus 0 = a$ 。
• 將 $[0, n]$ 和陣列中的所有數進行 XOR 運算，最後的結果即為缺失的數。
• 時間複雜度：$O(n)$。
• 空間複雜度：$O(1)$。

數學排序雜湊表位運算

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        return n * (n + 1) // 2 - sum(nums)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        if nums[0] != 0:
            return 0
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1] + 1:
                return nums[i] - 1
        return nums[-1] + 1

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        s = set(nums)
        for x in range(len(nums) + 1):
            if x not in s:
                return x

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = len(nums)
        for i in range(len(nums)):
            res ^= i ^ nums[i]
        return res

---