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

All problems solved by python

2024-02-01

題意

<++>

思路

<++>

1

🟡 2966. Divide Array Into Arrays With Max Difference 1396

題意

  • 給定一個長度為 nn 的整數陣列 numsnums，以及一個正整數 kk ，將這個陣列分成一個或多個長度為 33 的子陣列，並滿足以下條件：
    1. numsnums 中的 每個 元素都必須 恰好 存在於某個子陣列中。
    2. 子陣列中 任意 兩個元素的差必須小於或等於 kk 。
  • 傳回一個 二維陣列 ，包含所有的子陣列。 如果不可能滿足條件，就回傳一個空陣列。 如果有多個答案，返回 任一個 即可。

思路：排序

  • 由於條件1要求每個元素都要恰好存在於某個子陣列中，因此可以將答案視為將 nn 個數字分成 n/3n/3 個子陣列，每個子陣列長度為 33。
  • 為了滿足條件2，我們可以讓同一個子陣列中的元素盡量接近，因此我們可以先將 numsnums 排序後，每次取出 33 個數字，檢查是否滿足條件，如果滿足條件，就加入答案中，否則回傳空陣列。
  • 時間複雜度：O(nlog⁡n)O(n \log n) ，排序的時間複雜度為 O(nlog⁡n)O(n \log n) ，每次取出 33 個數字的時間複雜度為 O(1)O(1) ，因此總時間複雜度為 O(nlog⁡n)O(n \log n) 。
  • 空間複雜度：O(n)O(n) ，排序的空間複雜度為 O(n)O(n) ，答案的空間複雜度為 O(n)O(n) ，因此總空間複雜度為 O(n)O(n) 。
1
2
3
4
5
6
7
8
9
class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = [nums[i*3:i*3+3] for i in range(n // 3)]
        for row in ans:
            if row[2] - row[0] > k:
                return []
        return ans

2024-02-04

🟢 292. Nim Game

題意

  • 給定 nn 個石頭，你和你的朋友，兩個人一起玩 Nim 遊戲。兩個人輪流拿石頭，每次可以拿 1-3 個，最後一個拿到石頭的人贏。假設你和你的朋友都是最優解，請問你是否能贏得這場遊戲。如果可以贏，回傳 True；否則，回傳 False。

思路：博奕論

  • 先從 n=1n=1 開始，可以發現 n=1,2,3n=1,2,3 時，先手必勝；n=4n=4 時，先手必敗。且當 n=4k+1,4k+2,4k+3n=4k+1,4k+2,4k+3 時，先手可以拿走 1,2,31,2,3 個石頭，使得剩下的石頭數為 4k4k，這樣後手必敗。因此，我們可以推論出，當 nn 為 4 的倍數時，先手必敗；否則，先手必勝。故返回 n % 4 != 0 即可。
  • 時間複雜度：O(1)O(1)
1
2
3
class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

🔴 76. Minimum Window Substring

題意

  • 給定一個字串 ss、一個字串 tt 。 傳回 ss 中涵蓋 tt 所有字元的最小subarray。 如果 ss 中不存在涵蓋 tt 所有字元的subarray，則傳回空字串 "" 。

思路：滑動窗口

  • 使用兩個指針 leftleft 和 rightright ，分別指向窗口的左右邊界，若條件尚未滿足，則右指針向右移動擴大窗口，直到滿足條件；然後左指針向右移動，直到不滿足條件，重複此過程，直到右指針到達字串尾部。
  • 在檢查條件是否被滿足時，可以使用 Counter 來計算窗口中的字元數量，並使用 all 函數來檢查是否所有字元的數量都大於等於 tt 中的數量。但是這種方法會導致重複計算，因此可以使用 need 變數來計算需要的字元數量，並使用 need 變數來檢查是否所有字元的數量都大於等於 tt 中的數量。
  • 時間複雜度：優化前為 O(n×m)O(n \times m) ，優化後為 O(n)O(n) ，其中nn 為 ss 的長度、mm 為 tt 的長度。
  • 空間複雜度：優化前為 O(n)O(n) ，優化後為 O(m)O(m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ans = ""
        cnt = Counter()
        cnt_t = Counter(t)
        left = 0
        for right, ch in enumerate(s):
            cnt[ch] += 1
            while all(cnt[c] >= cnt_t[c] for c in cnt_t): # 符合條件，開始縮小窗口
                cnt[s[left]] -= 1
                if not ans or len(ans) > (right - left + 1): # 更新答案
                    ans = s[left:right+1]
                left += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = len(t) # need count
        cnt_t = Counter(t) 
        ans = ""
        left = 0
        for right, ch in enumerate(s):
            if ch in cnt_t.keys():
                if cnt_t[s[right]] > 0:
                    need -= 1
                cnt_t[s[right]] -= 1

            while need == 0: # 符合條件，開始縮小窗口
                if not ans or len(ans) > (right - left + 1): # 更新答案
                    ans = s[left:right+1]
                if s[left] in cnt_t:
                    cnt_t[s[left]] += 1
                    if cnt_t[s[left]] > 0:
                        need += 1
                left += 1
        return ans

2024-02-05

🟡 1696. Jump Game VI 1954

題意

  • 給定一個下標從 00 開始的整數陣列 numsnums 和一個整數 kk
  • 起始點在下標為 00 的位置，每次最多可以往前跳 kk 步，但不能跳出陣列的邊界。也就是說，可以從下標 ii 跳到 [i+1,min⁡(n−1,i+k)][i+1, \min(n-1, i+k)] 包含兩個端點的任意位置。
  • 目標是到達陣列最後一個位置（下標為 n−1n-1 ），得分為經過的所有數字之和。返回能得到的 最大得分。

思路：DP + Max Heap

  • 由DP思路可知，當前位置的最大得分為前 kk 個位置的最大得分加上當前位置的值。但每次都考慮前 kk 個位置的最大得分，會導致時間複雜度過高，導致 TLE
  • 因此可以使用Max Heap來維護前 kk 個位置的最大得分，每次取出最大得分，加上當前位置的值，並將新的最大得分加入Max Heap中。若取出的最大得分的位置與當前位置的距離超過 kk ，則將其丟棄。
  • 時間複雜度：O(nlog⁡n)O(n \log n) ，其中nn 為 numsnums 的長度。
  • 空間複雜度：O(n)O(n)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        hp = [] # max heap
        ans = nums[0]
        heappush(hp, (-nums[0], 0)) # (value, index)
        for i in range(1, n):
            while hp and i - hp[0][1] > k: # index distance is too large
                heappop(hp)
            ans = -hp[0][0] + nums[i]
            heappush(hp, (-ans, i))
        return ans

🟢 387. First Unique Character in a String

題意

給定一個字串 ss ，找到 第一個不重複的字元，並返回它的索引，如果不存在，則傳回 -1 。

思路：Counter

  • 使用Counter計算每個字元的出現次數，然後掃過一次字串，找到第一個出現次數為 11 的字元，並返回其索引。
  • 時間複雜度：O(n)O(n) ，其中nn 為 ss 的長度。
  • 空間複雜度：O(n)O(n)
1
2
3
4
5
6
7
class Solution:
    def firstUniqChar(self, s: str) -> int:
        cnt = Counter(s)
        for i, ch in enumerate(s):
            if cnt[ch] == 1:
                return i
        return -1

2024-02-06

🟡 LCP 30. 魔塔游戏

題意

  • 給定 NN 個房間，編號為 0 N−10 ~ N-1。給定一個陣列 numsnums ， nums[i]nums[i] 表示第 ii 個房間對於血量的影響。
  • 初始血量為 11，且沒有上限。原訂需以房間編號升序造訪所有房間，為保證血量始終為正值，需對房間訪問順序進行調整，每次僅能將房間調整至訪問順序末尾。
  • 返回最少需要調整幾次，才能順利訪問所有房間。若調整順序也無法訪問完全部房間，則返回 −1-1 。

思路：Simulation + Greedy + Heap

  • 先檢查總和是否小於 00 ，若小於 00 ，則無法通過所有房間，返回 −1-1 。
  • 按照題目要求的過程模擬，遇到血量小於 00 的時候，可以基於貪心原則，把前面的負數中最小的那個調整到後面去。
  • 由於前面已經檢查過總和是否小於 00 ，因此不需要紀錄調整過的房間的累計血量，只需要紀錄當前玩家血量即可。
  • 時間複雜度：O(nlog⁡n)O(n \log n) ，其中nn 為 numsnums 的長度。
  • 空間複雜度：O(n)O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def magicTower(self, nums: List[int]) -> int:
        if sum(nums) < 0: # 先處理總和小於0的情況
            return -1
        
        cur, ans = 1, 0 # 當前血量、調整次數
        hp = [] # Min Heap

        for x in nums:
            cur += x
            if x < 0: # 負數進堆
                heappush(hp, x)
            if cur <= 0: # 血量不夠
                cur -= heappop(hp) # 選擇一個負數扔到最後
                ans += 1
        return ans

🟡 49. Group Anagrams

題意

  • anagrams(字母異位詞) 是重新排列來源單字的所有字母，所得到的一個新單字。
  • 給定一個字串陣列 strsstrs ，將 anagrams(字母異位詞) 組合在一起。 可以以任意順序傳回結果。

思路：Hash Table

  • 若兩個單字的anagrams相同，則其排序後的字串也相同。因此可以使用排序後的字串作為key，將所有anagrams放入同一個list中。
  • 時間複雜度：O(n×mlog⁡m)O(n \times m \log m) ，其中nn 為 strsstrs 的長度、mm 為 strsstrs 中最長字串的長度。
  • 空間複雜度：O(n×m)O(n \times m)
1
2
3
4
5
6
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        cnt = defaultdict(list)
        for str in strs:
            cnt["".join(sorted(str))].append(str)
        return list(cnt.values())

2024-02-07

🟡 2641. Cousins in Binary Tree II 1677

題意

  • 給定一棵Binary Tree的根節點 rootroot ，將每個節點的值替換成該節點的所有 Cousins(堂兄弟)節點值的和 。
  • 如果兩個節點在樹中有相同的深度且它們的父節點不同，那麼它們互為 Cousins(堂兄弟) 。
  • 返回修改後的樹的根節點 rootroot 。

思路：Level-order traversal (BFS)

  • 使用BFS進行level-order traversal，並且先計算下個level的所有節點的值的和 ss。
  • 然後再進行一次BFS，考慮當前節點是否存在左右子節點：
    • 若左右子節點皆存在，則將 ss 減去左右子節點的值後，替換掉左右子節點的值，並將左右子節點加入queue中進行下一輪的BFS
    • 若只存在左子節點或右子節點，則需要減去其本身的值。
    • 若左右子節點不存在，則不需要進行任何操作。
  • 時間複雜度：O(n)O(n) ，其中nn 為 rootroot 的節點數量。
  • 空間複雜度：O(n)O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        root.val = 0
        q = deque([root])
        while q:
            n = len(q)
            s = 0 # sum of values in "next" level
            for node in q: 
                if node.left:
                    s += node.left.val
                if node.right:
                    s += node.right.val
            for _ in range(n):
                node = q.popleft()
                sub = (node.left.val if node.left else 0) + (node.right.val if node.right else 0) # 扣除自己和兄弟節點的值
                if node.left:
                    node.left.val = s - sub
                    q.append(node.left)
                if node.right:
                    node.right.val = s - sub
                    q.append(node.right)
        return root

🟡 451. Sort Characters By Frequency

題意

  • 給定一個字串 ss ，根據字元出現的 頻率 對其進行 降序排序 。
  • 一個字元出現的 頻率 是它出現在字串中的次數。
  • 返回排序後的字串，若有多個答案，則可以返回其中任何一個。

思路：Counter + Sort

  • 使用Counter計算每個字元的出現次數，然後根據出現次數進行降序排序。
  • 時間複雜度：O(nlog⁡n)O(n \log n) ，其中nn 為 ss 的長度。
  • 空間複雜度：O(n)O(n)
1
2
3
4
5
6
7
class Solution:
    def frequencySort(self, s: str) -> str:
        cnt = Counter(s)
        ans = ""
        for k, v in sorted(cnt.items(), key=lambda x: -x[1]):
            ans += k * v
        return ans

2024-02-08

🟢 993. Cousins in Binary Tree 1288

題意

  • 如果Binary Tree的兩個節點深度相同，但父節點不同，則它們是 Cousins(堂兄弟)節點 。
  • 給定一棵Binary Tree的根節點 rootroot ，以及兩個節點的值 xx 和 yy ，請確定它們是否是 Cousins(堂兄弟)節點 。如果是，則返回 truetrue ；否則，返回 falsefalse 。

思路：Level-order traversal (BFS)

  • 以 depth1depth1 和 depth2depth2 分別記錄 xx 和 yy 的深度，以 parent1parent1 和 parent2parent2 分別記錄 xx 和 yy 的父節點。
  • 使用BFS進行level-order traversal，並且在每一層的BFS中，檢查是否存在 xx 和 yy ，直到找到 xx 和 yy 的深度和父節點為止。
  • 最後檢查 xx 和 yy 的深度是否相同，且父節點是否不同。
  • 時間複雜度：O(n)O(n) ，其中nn 為 rootroot 的節點數量。
  • 空間複雜度：O(n)O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        depth1, depth2 = -1, -1
        parent1, parent2 = None, None
        q = deque([(root, 0, None)])
        while (depth1 == -1 or depth2 == -1):
            node, depth, parent = q.popleft()
            if node.val == x:
                depth1, parent1 = depth, parent
            if node.val == y:
                depth2, parent2 = depth, parent
            if node.left:
                q.append((node.left, depth+1, node))
            if node.right:
                q.append((node.right, depth+1, node))
        return (depth1 == depth2 and parent1 != parent2)

🟡 279. Perfect Squares

題意

  • 給定一個整數 nn ，找到和為 nn 的 完全平方數 的最少數量。

思路：DP

  • 令 dp[i]dp[i] 表示和為i的完全平方數的最小個數，則 dp[i]=min⁡(dp[i],dp[i−j∗j]+1)dp[i] = \min(dp[i], dp[i-j*j]+1) ，其中 j∗j≤ij*j \leq i 。
  • 時間複雜度：O(nn)O(n \sqrt{n})
  • 空間複雜度：O(n)O(n)
1
2
3
4
5
6
7
8
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] * (n+1)
        for i in range(1, n+1):
            dp[i] = i # i = (1^2) * i
            for j in range(1, math.isqrt(i)+1): # j*j <= i
                dp[i] = min(dp[i], dp[i-j*j]+1)
        return dp[n]

2024-02-09

🟡 236. Lowest Common Ancestor of a Binary Tree

題意

  • 給定一個Binary Tree，以及兩個節點 pp 和 qq ，找到它們的 最近公共祖先(Lowest Common Ancestor, LCA)。
  • 最近公共祖先(Lowest Common Ancestor, LCA) 定義為：「對於Binary Tree的兩個節點p、q，最近公共祖先表示為一個節點x，滿足x是p、q的祖先且x的深度盡可能大（一個節點也可以是它自己的祖先）」。

思路：DFS + Recursion/Hash Table

方法一：DFS + Recursion

  • 若 rootroot 是 pp, qq 的 最近共同祖先，則只可能為以下情況之一：
    1. pp 和 qq 分別在 rootroot 的 左子樹和右子樹中
    2. p=rootp = root，且 qq 在 rootroot 的 左子樹或右子樹中
    3. q=rootq = root，且 pp 在 rootroot 的 左子樹或右子樹中
  • 因此可以使用遞迴的方式進行檢查，在找到 pp 或 qq 時，就返回root，否則遞迴檢查左右子樹。
    • 若左右子樹都返回非空值，則表示 pp 和 qq 分別在左右子樹中，則返回 rootroot
    • 若只有一個子樹返回非空值，則表示 pp 和 qq 都在該子樹中，則返回該子樹的返回值
    • 若左右子樹都返回空值，則表示 pp 和 qq 都不在左右子樹中，則返回空值
  • 時間複雜度：O(n)O(n) ，其中nn 為 rootroot 的節點數量。
  • 空間複雜度：O(n)O(n)

方法二：DFS + Hash Table 紀錄父節點

  • 使用DFS遍歷整棵樹，並且在遍歷的同時，紀錄每個節點的父節點。
  • 對於節點 pp ，紀錄其所有的祖先節點，並且將其放入一個set visitedvisited 中。
  • 對於節點 qq ，進行同樣的操作，若其某個祖先節點已經存在於 visitedvisited 中，則代表該祖先節點為 pp 和 qq 的最近共同祖先。
  • 時間複雜度：O(n)O(n) ，其中nn 為 rootroot 的節點數量。
  • 空間複雜度：O(n)O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root: return None
        if p == root or q == root: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right: # p 和 q 分別在 root 的 左/右子樹中
            return root
        elif left:
            return left
        elif right:
            return right
        else: # p 和 q 都不在 root 的 左/右子樹中
            return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        fa = {root.val: None} # Recode the parent of each node
        visited = set()

        def dfs(root: 'TreeNode'):
            if root.left:
                fa[root.left.val] = root
                dfs(root.left)
            if root.right:
                fa[root.right.val] = root
                dfs(root.right)
        dfs(root)

        while p != None:
            visited.add(p.val)
            p = fa[p.val]

        while q != None:
            if q.val in visited:
                return q
            q = fa[q.val]

        return None

🟡 368. Largest Divisible Subset

題意

  • 給定一個相異正整陣列成的集合 numsnums ，找出並返回其中最大的 整除子集(Divisible Subset) answeranswer ，子集中每一元素對 (answer[i],answer[j])(answer[i], answer[j]) 都應滿足：
    • answer[i]mod  answer[j]=0answer[i] \mod answer[j] = 0 ，或
    • answer[j]mod  answer[i]=0answer[j] \mod answer[i] = 0
  • 若有多個答案，則可以返回其中任意一個。

思路：DP

  • 先將 numsnums 進行排序，如此我們只需要考慮 nums[i]mod  nums[j]=0nums[i] \mod nums[j] = 0 的情況。
  • 此問題可以轉換成類似於最長遞增子序列(LIS)的問題，可以使用DP來解決，對於每個 nums[i]nums[i] ，可以從 nums[0] 到 nums[i-1] 中的找到一個最大的整除子集來轉移，並且滿足加上 nums[i]nums[i] 後，可以得到一個更大的整除子集。
  • 令 dp[i]dp[i] 表示以 nums[i]nums[i] 結尾的最大整除子集的長度，則 dp[i]=max⁡(dp[i],dp[j]+1)dp[i] = \max(dp[i], dp[j]+1) ，其中 nums[i]mod  nums[j]=0nums[i] \mod nums[j] = 0 且 j<ij < i 。
  • 但所求的整除子集不僅是長度，還需要記錄整除子集的元素，因此可以改用一個hash table cntcnt 來記錄整除子集的元素。 cnt[num]cnt[num] 表示以 numnum 結尾的最大整除子集，最後返回 cntcnt 中最長的整除子集。
  • 時間複雜度：O(n2)O(n^2)
  • 空間複雜度：O(n)O(n)
1
2
3
4
5
6
7
8
9
10
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        cnt = defaultdict(list) # cnt[num] 表示以 num 結尾的最大整除子集
        for i, num in enumerate(nums):
            cnt[num] = [num] # 以 num 結尾最小整除子集為 [num]
            for j in range(i):
                if num % nums[j] == 0 and len(cnt[nums[j]]) + 1 > len(cnt[num]): # cnt[nums[j]] 加上 nums[i] 後能構成更長的整除子集
                    cnt[num] = cnt[nums[j]] + [num]
        return max(cnt.values(), key=len) # 返回最長的整除子集

2024-02-10

🟢 94. Binary Tree Inorder Traversal

題意

  • 給定一個Binary Tree的根節點 rootroot ，返回其 inorder traversal 的結果。

思路：遞迴(Recursion)

  • 使用遞迴的方式進行中序遍歷，定義一個遞迴函數 inorder，並且返回遍歷的結果。
1
2
3
4
5
6
7
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def inorder(root: Optional[TreeNode]) -> List[int]:
            if not root:
                return []
            return inorder(root.left) + [root.val] + inorder(root.right)
        return inorder(root)

🟡 647. Palindromic Substrings

題意

  • 給定一個字串 ss，返回 ss 中的 回文子字串(Palindromic Substring) 的數量。
  • 需注意，具有不同起始位置或結束位置的子字串，即使是由相同的字元組成，也會被視為不同的子字串。

思路：DP

  • 定義一個二維DP陣列 dp[i][j]dp[i][j] ，表示 s[i:j+1]s[i:j+1] 是否為回文子字串。
  • 考慮長度 kk 的回文子字串
    • 長度為 11 的子字串一定是回文子字串，初始化 dp[i][i]=Truedp[i][i] = True
    • 長度為 22 的子字串，若兩個字元相同，則是回文子字串，初始化 dp[i][i+1]=Truedp[i][i+1] = True 若 s[i]==s[i+1]s[i] == s[i+1]
    • 長度 ≥3\geq 3 的子字串，若 s[i]==s[j]s[i] == s[j] 且 dp[i+1][j−1]dp[i+1][j-1] 為True，則 s[i:j+1]s[i:j+1] 是回文子字串。
  • 時間複雜度：O(n2)O(n^2)
  • 空間複雜度：O(n2)O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = 0
        for i in range(n): # 長度為 1 的palindrome substring
            dp[i][i] = True
            ans += 1
        for i in range(n-1): # 長度為 2 的palindrome substring
            if s[i] == s[i+1]:
                dp[i][i+1] = True
                ans += 1
        for ln in range(3, n+1): # 長度>= 3 的palindrome substring
            for i in range(n-ln+1):
                j = i + ln - 1
                if s[i] == s[j] and dp[i+1][j-1]:
                    dp[i][j] = True
                    ans += 1
        return ans