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

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

All problems solved by python

---

2024-03-11

🟢 2129. Capitalize the Title 1275

題意

• 給定一個字串 $title$，由一個或多個單詞組成，每個單詞之間由一個空格隔開，每個單詞只包含英文字母。請你按照以下規則將每個單詞的 首字母大寫 ：
  • 如果單詞的長度為 $1$ 或 $2$，則所有字母變成小寫。
  • 否則，將單詞的首字母大寫，其餘字母變成小寫。
• 請你返回 大寫化後 的 $title$。

思路：簡單模擬(Simulation)

• 首先將 $title$ 以空格切割成單詞，再檢查每個單詞的長度，根據長度進行大寫化，最後將處理完的單詞以空格連接起來即可。
• 這裡使用 str.title() 方法來將單詞的首字母大寫，其餘字母小寫。
• 時間複雜度 $O(n)$，$n$ 為 $title$ 的長度。
• 空間複雜度 $O(n)$。

class Solution:
    def capitalizeTitle(self, title: str) -> str:
        words = title.split()
        for i, w in enumerate(words):
            if len(w) > 2:
                words[i] = w.title()
            else:
                words[i] = w.lower()
        return ' '.join(words)

---

🟡 791. Custom Sort String 1424

題意

• 給定兩個字串 $order$ 和 $s$。$order$ 的所有字元都是 唯一 的，並且已經按照一些自定義的順序排序。
• 重新排列 $s$ 中的字元，使其符合 $order$ 的排序順序。也就是說，如果字元 $x$ 在 $order$ 中出現在字元 $y$ 之前，那麼在重新排列的字串中，$x$ 也應該出現在 $y$ 之前。
• 返回任何符合這個條件的 $s$ 的排列。

思路

• 首先注意題目中提到滿足條件的排列可能有多個，這代表 $order$ 並不會包含 $s$ 中的所有字元，為了處理這種情況，我們可以將 $s$ 中不在 $order$ 中的字元放在最後。
• 為了滿足 $order$ 的排序順序，我們可以先計算 $s$ 中每個字元的出現次數，再根據 $order$ 的順序來構建新的字串。優先按照 $order$ 的順序來處理，最後再將 $s$ 中不在 $order$ 中的字元加到最後即可。
• 時間複雜度 $O(n)$，$n$ 為 $s$ 的長度。
• 空間複雜度 $O(1)$，不計算答案使用的空間。

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        cnt = [0] * 26
        for ch in s:
            cnt[ord(ch) - ord('a')] += 1
        ans = ''
        for ch in order:
            ans += ch * cnt[ord(ch) - ord('a')]
            cnt[ord(ch) - ord('a')] = 0
        for i in range(26):
            ans += chr(i + ord('a')) * cnt[i]
        return ans

---

2024-03-12

🟡 1261. Find Elements in a Contaminated Binary Tree 1440

解法二用到了Binary Tree的 Array Representation ，很有趣的一道題目。

題意

• 給定一個滿足以下規則的二元樹：
  1. $root.val = 0$
  2. 如果 $treeNode.val = x$ 且 $treeNode.left \neq null$，那麼 $treeNode.left.val = 2 * x + 1$
  3. 如果 $treeNode.val = x$ 且 $treeNode.right \neq null$，那麼 $treeNode.right.val = 2 * x + 2$
• 現在這個二元樹受到「污染」，所有的 $treeNode.val$ 都變成 $-1$。
• 請你先還原二元樹，然後實現 FindElements 類別：
  • FindElements(TreeNode* root) 用受污染的二元樹初始化對象，你需要先把它還原。
  • bool find(int target) 判斷目標值 $target$ 是否存在於還原後的二元樹中並返回結果。

思路：DFS + Hash Table / Bitwise Operation

解法一：DFS + Hash Table

• 首先進行 DFS 還原二元樹，並使用 set 來記錄所有在還原過程中出現過的值。
• find 函數只需要判斷目標值是否在 set 中即可。
• 時間複雜度：
  • __init__ 函數的時間複雜度 $O(n)$，$n$ 為二元樹的節點數。
  • find 函數的時間複雜度 $O(1)$。
• 空間複雜度 $O(n)$，為 set 使用的空間。

class FindElements:

    def __init__(self, root: Optional[TreeNode]):
        self.root = root
        self.root.val = 0
        self.vals = set([0])
        def dfs(node: TreeNode, val: int):
            if node.left:
                node.left.val = 2 * val + 1
                self.vals.add(node.left.val)
                dfs(node.left, node.left.val)
            if node.right:
                node.right.val = 2 * val + 2
                self.vals.add(node.right.val)
                dfs(node.right, node.right.val)
        dfs(self.root, 0)

    def find(self, target: int) -> bool:
        return target in self.vals

解法二：DFS + Bitwise Operation

• 如果閱讀過 Horowitz 的《Fundamentals of Data Structures》一書，應該對能夠輕易發現題目中的定義，與二元樹的 Array Representation 方式非常類似。但差別在這裡的根節點是 $0$，而不是 $1$，不過我們可以透過對所有節點的值加上 $1$ 來解決這個問題。修改後的二元樹的根節點為 $1$，左子節點為 $2 * x$，右子節點為 $2 * x + 1$。
• 再來將所有節點的值轉換成二進位，不難發現，對於任意節點的值 $x$，其左子節點的值為 $x << 1$，右子節點的值為 $(x << 1) + 1$，因此可以忽略最高位的 $1$ ，從高位到低位訪問，若遇到 $0$，則表示為左子節點，若遇到 $1$，則表示為右子節點。
• 這樣我們就可以不用額外的空間來記錄所有節點的值，只需要對目標值進行轉換，再根據轉換後的值來判斷是否存在於二元樹中。
• 時間複雜度：
  • __init__ 函數的時間複雜度 $O(1)$ ；
  • find 函數的時間複雜度 $O(min(h, \log target))$ 。
• 空間複雜度 $O(1)$ 。

class FindElements:

    def __init__(self, root: Optional[TreeNode]):
        self.root = root

    def find(self, target: int) -> bool:
        target += 1 # 由於將所有節點的值加1，所以查找的值也要加1
        cur = self.root  
        for i in range(target.bit_length() - 2, -1, -1): # 從第二位開始，因為第一位必定是1
            b = target & (1 << i) # 取出第i位的值
            cur = cur.right if b else cur.left # 如果第i位是1，就往右走，否則往左走
            if cur is None: # 走到空節點，說明目標值存在，返回False
                return False
        return True

---

🟡 1171. Remove Zero Sum Consecutive Nodes from Linked List 1782

題意

• 給定一個 鏈結串列 (Linked list) 的頭節點 $head$，反覆刪除Linked List中由 總和 值為 $0$ 的連續節點組成的序列，直到不存在這樣的序列為止。
• 刪除完畢後，請你返回最終結果Linked List的頭節點，可能有多種答案，返回任意一個滿足要求的答案即可。

思路：前綴和(Prefix Sum) + 雜湊表(Hash Table)

• 首先將Linked List序列化成一個陣列，來思考如何刪除連續節點總和為 $0$ 的序列。這裡需要一點前綴和的先備知識，前綴和是指從序列的開頭到某個位置的總和，如果有前綴和 $s_i$ 和 $s_j$，且 $s_i = s_j$，則說明 $s_{i+1} + s_{i+2} + \cdots + s_j = 0$，根據題意，我們可以刪除這兩個前綴和之間的節點。
• 再來考試如何在Linked List中實現前綴和並刪除節點，我們可以使用雜湊表來記錄前綴和對應的節點，而我們只要保存每個前綴和和對應的最後一個節點即可，因為若存在多個前綴和和相同的節點，分段刪除和將這些節點視為一段合併刪除是等價的。
• 因此可以分成兩個步驟：
  1. 第一次遍歷Linked List，計算前綴和，並將前綴和對應的最後一個節點保存到雜湊表中。
  2. 第二次遍歷Linked List，根據前綴和刪除節點。
• 時間複雜度 $O(n)$，$n$ 為Linked List的節點數。
• 空間複雜度 $O(n)$，為雜湊表使用的空間。

class Solution:
    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(val=0, next=head)
        last = dict() # last[s] = node, the last node with prefix sum s
        s = 0 # prefix sum
        cur = dummy
        while cur: # get the last node with prefix sum s
            s += cur.val
            last[s] = cur
            cur = cur.next
        s, cur = 0, dummy
        while cur: # remove the nodes between last[s] and cur
            s += cur.val
            cur.next = last[s].next
            cur = cur.next
        return dummy.next

---

2024-03-13

同 2024-03-01 LCUS

🟢 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'

🟢 2485. Find the Pivot Integer 1207

題意

• 給定一個正整數 $n$，找到 樞軸整數(Pivot Integer) $x$ 使得：
  • $1$ 到 $x$ 之間所有元素的總和等於 $x$ 到 $n$ 之間所有元素的總和。
• 返回樞軸整數 $x$。如果不存在這樣的整數，返回 $-1$。保證對於給定的輸入最多只有一個樞軸整數。

思路：二分搜尋(Binary Search) / 數學(Math)

• 為方便表示，定義 $sum(a, b) = a + (a + 1) + \cdots + b = \frac{(a + b) \times (b - a + 1)}{2}$
• 則題目的目標是找到 $x$ 使得 $sum(1, x) = sum(x, n)$。

解法一：二分搜尋(Binary Search)

• 若目標 $x$ 存在，則增加 $x$ 的值，$sum(1, x)$ 會增加，$sum(x, n)$ 會減少，反之亦然。因此可以用二分搜尋來找到目標 $x$。
• 時間複雜度 $O(\log n)$。
• 空間複雜度 $O(1)$。

class Solution:
    def pivotInteger(self, n: int) -> int:
        s = (1 + n) * n // 2
        left, right = 1, n
        while left <= right:
            mid = (left + right) // 2
            s1 = (1 + mid) * mid // 2
            s2 = s - s1 + mid
            if s1 == s2:
                return mid
            elif s1 < s2:
                left = mid + 1
            else:
                right = mid - 1
        return -1

解法二：數學(Math)

• 進一步化簡為 $sum(1, x) = sum(1, n) - sum(1, x - 1)$ 即 $\frac{x \times (x + 1)}{2} = \frac{n \times (n + 1)}{2} - \frac{x \times (x - 1)}{2}$，整理後得到 $x^2 = \frac{n \times (n + 1)}{2}$ ，解出 $x = \sqrt{\frac{n \times (n + 1)}{2}}$。
• 若 $x$ 為整數，則返回 $x$，否則返回 $-1$。
• 時間複雜度 $O(1)$。
• 空間複雜度 $O(1)$。

class Solution:
    def pivotInteger(self, n: int) -> int:
        s = n * (n + 1) // 2
        # x = math.isqrt(s)
        # return x if x * x == s else -1
        x = math.sqrt(s)
        return int(x) if x == int(x) else -1

---

2024-03-14

🟡 2789. Largest Element in an Array after Merge Operations 1485

題意

<++>

思路

<++>

---

🟡 930. Binary Subarrays With Sum 1592

題意

<++>

思路

<++>

---

2024-03-15