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

All problems solved by python

2023-12-01

🟡 2661. First Completely Painted Row or Column 1503

題意

給定一個 $arr$ 和 $m * n$ 的矩陣 $mat$ ， $arr$ 和 $mat$ 都包含 $[1, m*n]$ 的所有整數
依照 $arr$ 的順序，對矩陣中值為 $arr[i]$ 的位置 $(x_i, y_i)$ 著色，即 $mat[x_i][y_i] = arr[i]$ 。若 $(x_i, y_i)$ 所在的row和col都已經全部著色，返回下標 $i$ 。

思路：Hash Table + 模擬

因為每個元素都是唯一的(洽出現一次)，所以可以用 Hash Table 來記錄每個元素出現的位置
再來就模擬過程就好了，用 $rows$ 和 $cols$ 紀錄過程中每個 row 和 col 的塗色狀況

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        tbl = {} # 紀錄這個元素出現的位置
        for i in range(m):
            for j in range(n):
                tbl[mat[i][j]] = (i, j)
        rows, cols = [0]*m, [0]*n # 紀錄每個 row 和 col 的塗色狀況
        for i, val in enumerate(arr):
            x, y = tbl[val]
            rows[x] += 1
            cols[y] += 1
            if rows[x] == n or cols[y] == m: # 如果這個 row 或 col 已經塗滿了，就回傳
                return i
        return -1

🟢 1662. Check If Two String Arrays are Equivalent 1217

題意

給定 $words1$ 和 $words2$ ，求兩者組成的字串是否相等。

思路：Build-in function / 逐字模擬

令 $i$ , $j$ 分別表示當前是 $word1$ 和 $word2$ 中第 $i$ 和第 $j$ 個字串， $ii$ , $jj$ 表示 $word1[i]$ 和 $word2[j]$ 中第 $ii$ 和第 $jj$ 個字元，逐字模擬，超過當前字串長度則檢查下一個字串，最後檢查是否已經檢查完所有字串即可。

class Solution:
    def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        # return "".join(word1) == "".join(word2)
        i = j = ii = jj = 0
        while i < len(word1) and j < len(word2):
            if word1[i][ii] != word2[j][jj]: # 檢查字元是否相等
                return False
            ii += 1
            jj += 1
            if ii == len(word1[i]): # 換word1的下一個字串
                ii = 0
                i += 1
            if jj == len(word2[j]): # 換word2的下一個字串
                jj = 0
                j += 1
        return i == len(word1) and j == len(word2) # 是否已經檢查完所有字串

2023-12-02

🟡 1094. Car Pooling 1441

題意

車上有 $capacity$ 個座位，車在一條直線上行駛，且只能往前不能調頭。
給定 $trips$ ， $trip[i] = [numPassengers_i, from_i, to_i]$ 表示有 $numPassengers_i$ 名乘客要從 $from_i$ 搭車到 $to_i$
若可以接送所有乘客，則返回 $True$ ，否則返回 $False$

思路：模擬 + 差分陣列

用一個 Arrray $diff$ 紀錄在 $pos$ 的上車或下車人數，正數表示上車，負數表示下車。從起點一直開到旅途終點，在每個位置檢查車上人數有沒有超載。

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        MAX_TO = max([trip[2] for trip in trips])

        diff = [0] * (MAX_TO + 1)
        for num, x, y in trips:
            diff[x] += num # from 
            diff[y] -= num # to
        
        cnt = 0 # 當前車上的人數
        for i in range(MAX_TO + 1):
            cnt += diff[i]
            if cnt > capacity: # 超載
                return False
        return True

🟢 1160. Find Words That Can Be Formed by Characters 1206

題意

給定一份「單字表」 $words$ 和一張「字母表」 $chars$ ，計算可以由 $chars$ 中的字母組合出的所有 $words[i]$ 的總長度。
每次構建一個 $words[i]$ 時， $chars$ 中的所有字母都只能使用一次。

思路：Counter

根據範例，若一個字母 $ch$ 在 $chars$ 中的出現次數 $\geq$ 在 $words[i]$ 中的出現次數，則被認為可以被構建的。
用兩個Counter分別記錄 $ch$ 在 $chars$ 和 $words[i]$ 中的出現次數，檢查是否滿足條件即可

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        cnt = Counter(chars)
        ans = 0
        for word in words:
            cnt_w = Counter(word)
            if all(cnt_w[ch] <= cnt[ch] for ch in cnt_w):
                ans += len(word)
        return ans

2023-12-03

🟡 1423. Maximum Points You Can Obtain from Cards 1574

題意

給定 $n$ 張卡片， $cardPoints[i]$ 表示卡片對應的點數，每次可以從牌組的頂端或尾端抽一張卡，最後必需有 $k$ 張手牌，求可以獲得最好的手牌點數總和，即手牌點數的最大值。

思路：轉化 + 滑動窗口 / 前綴和

將問題轉化為：求長度為n-k的連續子陣列的最小和，此時就能用滑動窗口或前綴和解決了。

class Solution:
    """
        將問題轉化為：求長度為n-k的連續子陣列的最小和
        1. Prefix Sum
        2. Sliding Window
    """
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        # return self.solve1(cardPoints, k)
        return self.solve2(cardPoints, k)

    def solve1(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        pre_sum = list(accumulate(cardPoints, initial=0))
        mn = float('inf')
        for i in range(k+1):
            mn = min(mn, pre_sum[i+(n-k)] - pre_sum[i])
        return sum(cardPoints) - mn
    
    def solve2(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        left, right = 0, n - k
        ans = cur = sum(cardPoints[left:right])
        for _out, _in in zip(cardPoints, cardPoints[right:]):
            cur += _in - _out
            ans = min(ans, cur)
        return sum(cardPoints) - ans

🟢 1266. Minimum Time Visiting All Points 1303

題意

給定 $n$ 個平面上的點 $points[i] = [x_i, y_i]$ ，座標為整數。計算訪問所有點所需要的「最小時間」，必需按照給定的順序訪問。
移動方式為：
- 沿水平方向移動一個單位長度
- 沿垂直方向移動一個單位長度
- 沿對角線移動 $sqrt(2)$ 個單位長度

思路：模擬

根據題目，從 $[x_i, y_i]$ 移動到 $[x_{i+1}, y_{i+1}]$ ，所需要的時間為 $max(abs(x_{i+1} - x_{i}), abs(y_{i+1} - y_{i}))$ ，直接模擬即可。

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        ans = 0
        n = len(points)
        cur = points[0]
        for i in range(1, n):
            nxt = points[i]
            ans += max(abs(nxt[0] - cur[0]), abs(nxt[1] - cur[1]))
            cur = nxt
        return ans

2023-12-04

🟡 1038. Binary Search Tree to Greater Sum Tree 1375

題意

給定一個 Binary Search Tree (BST) 的 $root$ ，將其每隔節點的值都替換成 $\geq$ 當前節點值的所有節點值之和。

思路

根據 BST 性質，右子樹的節點值皆大於當前節點，因此以DFS方式依次訪問右子樹、當前節點、左子樹，並且維護比當前節點大的值的和 $s$ 。

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        s = 0
        def dfs(node: TreeNode):
            nonlocal s
            if not node:
                return
            dfs(node.right)
            node.val += s
            s = node.val
            dfs(node.left)
        dfs(root)
        return root

類題

🟡 538. Convert BST to Greater Tree 1375

🟢 2264. Largest 3-Same-Digit Number in String 1309

題意

給定一個字串 $num$ ，求其中長度為 $3$ 的子字串所有字元皆相等的最大字典序。
$num$ 中只包含 $[0, 9]$ 的數字。

思路：Sliding window

窗口大小固定為 $3$ $3$ ，每次移動一格，並更新窗口內的數字出現次數。
- 若檢查所有數字的出現次數，則時間複雜度為 $O(10)$
- 若同時統計出現次數的出現次數，則不用逐個字檢查，時間複雜度為 $O(1)$

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        n = len(num)
        ans = ""

        cnt = [0] * 10 # 每個數字出現的次數
        cntcnt = [0] * (3 + 1) # 出現次數的出現次數為 0, 1, 2, 3

        for right in range(n):
            ch_in = ord(num[right]) - ord('0') # 入窗口
            cntcnt[cnt[ch_in]] -= 1
            cnt[ch_in] += 1
            cntcnt[cnt[ch_in]] += 1

            left = right - 3 + 1
            if left >= 0: # 窗口大小固定為3
                if cntcnt[3] > 0: # 窗口內有出現3次的數字，則更新答案
                    ans = num[left:right+1] if num[left:right+1] > ans else ans
                    
                ch_out = ord(num[left]) - ord('0') # 出窗口
                cntcnt[cnt[ch_out]] -= 1
                cnt[ch_out] -= 1
                cntcnt[cnt[ch_out]] += 1
        return ans

2023-12-05

🟡 2477. Minimum Fuel Cost to Report to the Capital 2012

一開始沒看到是tree，以為是graph卡了一陣子，後來看到是tree就簡單多了XD

題意

給定一個有 $n$ 個節點的樹，每個節點代表一個城市，其中下標為0的節點代表首都。
每個城市都有一輛車，每輛車可以載 $seats$ 位乘客，且每個城市都要派出 $1$ 名代表前往首都，中途中可以換乘別人城市的車，只要不要超載即可。
相鄰兩個城市間的 $cost$ 固定為 $1$ ，求使得所有代表都能到達首都的最小花費。

思路：DFS

因為是樹，所以任意兩節點的最短路徑是唯一的。
用DFS訪問每個節點，返回這個節點的子樹中所有節點的數量(包含自己)。也就是到首都數浪會經過當前城市的人數(包含當前城市的代表)，計算到前往上一個城市的花費即可。
小提醒：樹上的節點數量 $N$ 等於邊數 $E$ 加一， $N = E + 1$

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        n = len(roads) + 1 # N = E + 1
        ans = 0

        g = [[] for _ in range(n)]
        for u, v in roads: # Undirected graph
            g[u].append(v)
            g[v].append(u)
        
        ans = 0
        def dfs(u: int, fa: int) -> int: # 返回這個節點的子樹中所有節點的數量(包含自己)。
            nonlocal ans
            s = 1 # 自己
            for v in g[u]: # 訪問子節點，即除了父節點以外的所有節點
                if v != fa: 
                    s += dfs(v, u)
            if u != 0: # 除了首都以外的節點
                ans += ceil(s / seats) * 1 # 前往上一個城市的車輛數，向上取整，代價固定為1
            return s
        dfs(0, -1)
        return ans

🟢 1688. Count of Matches in Tournament 1203

題意

給定 $n$ 支隊伍，每場比賽都會淘汰一隊，若剩下偶數支隊伍，進行 $n//2$ 場比賽，，若剩下奇數支隊伍，則進行 $n//2$ 場比賽，並且其中1支隊伍直接輪空晉級，求比賽的數量。

思路：數學

每場比賽都會淘汰一隊，要淘汰 $n-1$ 隊，因此需要進行比賽的數量為 $n-1$ 。

1
2
3

class Solution:
    def numberOfMatches(self, n: int) -> int:
        return n - 1

2023-12-06

🔴 2646. Minimize the Total Price of the Trips 2238

這題剛好是我的 LeetCode 第500題，紀念一下XD

題意

給定一個有 $n$ 個節點的樹，每個節點代表一個城市，給定一個Array $price$ 表示每個城市的旅遊費用。給定 $trips$ 表示旅遊路線，其中 $trip[i] = [x_i, y_i]$ 該次旅遊從 $x$ 城市到 $y$ 城市，對所有經過的城市都要計算旅遊費用。
在開始旅行之前，可以選擇一些城市減半旅遊費用，但選擇的城市不能相鄰，求最小的旅遊費用。

思路：樹形DP + LCA + DFS

為方便思考與計算，令下標為 0 的節點代表樹根。
選/不選的問題，可以用樹形DP解決，令 $dp[i][0]$ 表示不選 $i$ 的最小花費， $dp[i][1]$ 表示選 $i$ 的最小花費。

$\left\{\begin{array}{l} dp[i][0] = cnt_{i} * price_i + \sum_{v \isin adj(i)} \left( \max \left(dp[v][0], dp[v][1] \right) \right) \\ dp[i][1] = cnt_i * price_i // 2 + \sum_{v \isin adj(i)} dp[v][0] \\ \end{array}\right.$
所以這題可以分成兩個部分：
1. 根據 $trips$ 的起點和終點，計算每個城市經過的次數
2. 用樹形DP判斷每個城市的選或不選
為計算樹形DP，需要先計算每個節點的經過次數。因為樹上任意兩點的最短路徑是唯一的，所以可以透過計算兩個節點的最近公共祖先（Lowest Common Ancestor，LCA），來計算每個節點經過的次數。
為了方便計算LCA，可以先用DFS計算每個節點的父節點和深度，再以此計算LCA。

class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)

        # 第一次DFS，計算每個城市在樹上的父節點和深度
        fat = [0] * n # 每個節點的父節點
        dep = [0] * n # 以0為根，每個節點的深度

        def dfs1(u, fa):
            fat[u] = fa
            if fa != -1: # 0為根，沒有父節點，但因為python的索引特性其實不影響，只是深度變成從1開始
                dep[u] = dep[fa] + 1
            for v in g[u]:
                if v != fa:
                    dfs1(v, u)
        dfs1(0, -1)
        
        # 根據trips，計算每個城市經過的次數，最近公共祖先
        cnt = [0] * n
        for u, v in trips:
            if dep[u] < dep[v]: # 保證u在的深度>=v在的深度
                u, v = v, u
            while dep[u] > dep[v]: # u一直往上找，直到深度相同
                cnt[u] += 1
                u = fat[u]
            while u != v: # 深度相同時仍未相遇，繼續一起往上找公共祖先
                cnt[u] += 1
                cnt[v] += 1
                u = fat[u]
                v = fat[v]
            cnt[u] += 1 # 最後相遇的點，也要計算

        # 樹形DP，計算每個城市的選或不選
        dp = [[float('inf')] * 2 for _ in range(n)]

        def dfs2(u, fa):
            dp[u][0] = price[u] * cnt[u] # 不選i，則i的花費為price[i]*cnt[i]
            dp[u][1] = price[u] // 2 * cnt[u] # 選i，則i的花費為price[i]//2*cnt[i]
            for v in g[u]:
                if v != fa:
                    dfs2(v, u)
                    dp[u][1] += dp[v][0] # 選u，則v必不選，所以取dp[v][0]
                    dp[u][0] += min(dp[v][0], dp[v][1]) # 不選u，則v可選可不選，所以取min(dp[v][0], dp[v][1])
        dfs2(0, -1)
        return min(dp[0])

類題

樹形DP

LCA

題單來自： @灵茶山艾府

🟢 1716. Calculate Money in Leetcode Bank 1295

題意

每周一存入 $1$ 塊錢，從周二到周日，每天都比前一天多存入 $1$ 塊錢。而在下一周，也會比上一周的同一天多存入 $1$ 塊錢。計算在 $n$ 天後，總共存了多少錢。

思路：簡單模擬

對每天算出當天是第幾周、是該周的第幾天，再計算出當天存入的錢即可。

class Solution:
    def totalMoney(self, n: int) -> int:
        ans = 0
        for d in range(n):
            ans += (d // 7 + 1) + (d % 7)
        return ans

2023-12-07

🟡 1466. Reorder Routes to Make All Paths Lead to the City Zero 1634

題意

給定一個有 $n$ 個節點的樹，每個節點代表一個城市，有 $n-1$ 條有向邊作為單向道路連接這些城市。
重新規劃道路方向，使得所有城市都能夠前往下標為 0 的城市，求最少需要改變的道路方向數量。

思路：DFS紀錄正向邊數量

為方便思考與計算，令下標為 0 的節點代表樹根。將正向邊定義為從父節點指向子節點的邊，反向邊定義為從子節點指向父節點的邊。
對根節點進行DFS，計算每個節點的正向邊數量，即為改變道路方向的數量。
題外話，除了在DFS時傳入 ${fa}_i$ 的父節點，也可以用 $visited_i$ 來記錄每個節點是否被訪問過

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        edges = set()
        for u, v in connections:
            g[u].append(v)
            g[v].append(u)
            edges.add((u, v))
        ans = 0
        def dfs(u, fa):
            nonlocal ans
            for v in g[u]:
                if v != fa:
                    if (u, v) in edges:
                        ans += 1
                    dfs(v, u)
        dfs(0, -1)
        return ans

🟢 1903. Largest Odd Number in String 1249

題意

給定一個字串 $num$ ，表示一個大整數，在 $num$ 的所有 非空子字串中 找出值最大的奇數，並以字串形式返回，若不存在奇數，則返回空字串。

思路

要使值最大，則前面的數要盡可能的多，所以找到最後一個奇數，返回前面的數字即可。

class Solution:
    def largestOddNumber(self, num: str) -> str:
        n = len(num)
        for i in range(n-1, -1, -1):
            if int(num[i]) % 2 == 1:
                return num[:i+1]
        return ""

2023-12-08

🟡 2008. Maximum Earnings From Taxi 1872

題意

給定一條道路的長度 $n$ ，從 $1$ 到 $n$ 編號，給定一個下標由 0 開始 $rides$ 表示 $m$ 個乘客的訂單，其中 $rides[i] = [start_i, end_i, tip_i]$ 表示第 $i$ 個乘客從 $start_i$ 到 $end_i$ ，願意支付 $tip_i$ 的小費，對於每個乘客的收益是 $end_i - start_i + tip_i$ ，以下用 $weight_i$ 表示。
你必需從 $1$ 開到 $n$ ，並且只能往右走，不能回頭，每次只能接受一位乘客，求最大的收益總和。
注意：你可以在一個地點放下一位乘客，並在同一個地點接上另一位乘客。

思路：DP + 二分搜尋

Weighted Job Scheduling / Weighted Interval Scheduling

這題可以對 $rides$ 做DP，也能對地點做DP，而對 $rides$ 做DP，本質上就是 Weighted Interval Scheduling 問題，可以將每個乘客的上下車地點視為區間。
令 $dp[i+1]$ $d p [i + 1]$ 表示只考慮前 $i$ $i$ 個乘客的最大收益，對於第 $i$ $i$ 個乘客(下標為i)，我們可以選擇接或不接。
- 若接的話則需要考慮上一個乘客是誰，目標是找到上一個相容(compatible) 的乘客(令其下標為j)，也就是說上一個乘客的結束時間要小於等於當前乘客的開始時間 ( $ed_j \leq st_i$ ) ，此種情況 $dp[i+1] = dp[j+1] + weight_j$
- 若不接的話，則 $dp[i+1] = dp[i]$ ，考慮兩種情況的最大值即可。
首先對 $rides$ 按照結束時間排序，確保若上一個相容相容(compatible) 的區間若存在，其下標必在當前區間的下標之前，因此具有單調性，可以用二分搜尋找到上一個相容的乘客。
這裡使用 bisect，其中
- bisect.bisect_right 回傳 $>x$ 的第一個下標 (相當於C++中的upper_bound)，
- bisect.bisect_left 回傳 $\geq x$ 第一個下標 (相當於C++中的lower_bound)。
- 使用 hi 參數，可以用來限制搜尋的範圍，因為 $rides$ 已經按照結束時間排序，所以只要限制在當前區間的下標之前即可。
上一個相容的乘客的下標 $j = bisect\_right() - 1$ ，即第一個滿足 $ed_{j+1} > st_i$ 的前一個下標。
舉個🌰，為方便理解，令 $p(i)$ $p (i)$ 表示與 $i$ $i$ 兼容的下標 $j$ $j$ 。對於範例2(已排序)： $rides$ $r i d es$ = [(1, 6, 1), (3, 10, 2), (10, 12, 3), (11, 12, 2), (12, 15, 2), (13, 18, 1)]
- $p(0) = -1$ ，表示在 $(1, 6)$ 之前，不存在和其相容的區間
- $p(1) = -1$ ，同上。
- $p(2) = 1$ ，表示在 $(10, 12)$ 之前，第一個和其相容的區間 $(3, 10)$
- $p(3) = 1$ ，表示在 $(11, 12)$ 之前，第一個和其相容的區間 $(3, 10)$
- $p(4) = 3$ ，表示在 $(12, 15)$ 之前，第一個和其相容的區間 $(11, 12)$
- $p(5) = 3$ ，表示在 $(13, 18)$ 之前，第一個和其相容的區間 $(11, 12)$

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        m = len(rides)
        rides.sort(key=lambda x: x[1]) # 按照結束時間由小到大排序，確保上一個相容(compatible)的區間若存在，其下標必在當前區間的下標之前
        dp = [0] * (m + 1) # m個區間
        for i, (st, ed, tip) in enumerate(rides):
            w = ed - st + tip # weight 
            j = bisect_right(rides, st, hi=i, key=lambda x: x[1]) - 1 # 找到「上一個」相容(compatible)的區間的下標
            dp[i+1] = max(dp[i], dp[j+1] + w)
        return dp[m]

類題

🟡 2830. Maximize the Profit as the Salesman 1851
🔴 1235. Maximum Profit in Job Scheduling 2023
🟡 435. Non-overlapping Intervals
🔴 1751. Maximum Number of Events That Can Be Attended II 2041
🟡 2054. Two Best Non-Overlapping Events 1883
🟢 1576. Replace All ?'s to Avoid Consecutive Repeating Characters 1368

題單來自：@小姜可和 @有人吗

參考資料

NTU Algorithm Design and Analysis 2022

🟢 606. Construct String from Binary Tree

題意

給定一個二元樹的樹根 $root$ ，用preorder traversal的方式，將二元樹轉換為一個由括號和整陣列成的字串。
若子節點為空，則用括號表示。轉換後需維持和二元樹的對應關係，並且需要省略字串中多餘的括號。

思路：Recursion

根據題意，需要維持對應關係。顯然的，當只有一個子節點時，需要加上括號，否則無法區分是左子樹還是右子樹。
由範例說明，若左子樹不為空、右子樹為空，可以省略右子樹的括號；若左子樹為空、右子樹不為空，左子樹的括號不能省略。
用DFS遍歷樹，判斷左右子樹是否為空，根據不同情況在不同位置加上括號。返回當前子樹的字串表示即可。

class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:
        def preOrder(root):
            if not root:
                return ''
            if not root.left and not root.right: # 左右子樹都為空
                return f"{root.val}"
            elif not root.right: # 左子樹不為空、右子樹為空
                return f"{ root.val }({ preOrder(root.left) })"
            else: # 左子樹為空、右子樹不為空 / 左右子樹都不為空
                return f"{ root.val }({ preOrder(root.left) })({ preOrder(root.right) })"
        return preOrder(root)

2023-12-09

🟡 2048. Next Greater Numerically Balanced Number 1734

題意

如果整數 $x$ 滿足：對於每個位數 $d$ ，恰好在 $x$ 中出現 $d$ 次。那麼整數 $x$ 就是一個 數值平衡數。
給定一個整數 $n$ ，返回 $>n$ 的 最小數值平衡數 。

思路：打表 / 枚舉 / 回溯 + 二分

枚舉出現了哪些數字，並且計算每個數字出現的次數，
- 對於1位數：1
- 對於2位數：22
- 對於3位數：122 / 333
- 對於4位數：1333 / 4444
- 對於5位數：14444 / 22333
- 對於6位數：122333 / 155555 / 224444
若出現4種數字，則位數至少為 $1 + 2 + 3 + 4 = 10$ ，超出題目範圍，故考慮最多出現3種數字即可
在 $l$ 位數中，必存在 $1$ 個 $1$ 和 $(l-1)$ 個 $(l-1)$ (對 $l \leq 10$ )，所以檢查 $n$ 的位數 $l$ 和所 $l+1$ 位數即可。

一些優化

重複物排列可以用 backtracking ，枚舉出現的數字也能用 backtracking 。
但還是打表快多了XD

class Solution:
    ANS = [1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]
    def nextBeautifulNumber(self, n: int) -> int:
        return self.ANS[bisect_right(self.ANS, n)]

class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        tmp = n
        l = 0 # 計算位數
        while tmp > 0: 
            l += 1
            tmp //= 10

        ans = set()
        for d in range(l, l+2):
            for i in range(10): 
                for j in range(i, 10):
                    k = d - i - j
                    if not (i<=j<=k): # 保證數字是遞增的，避免重複
                        break
                    if (i ==0 and j == 0) or (i != j and j != k): # 若該數字有出現，則不可重複
                        lst = [i]*i + [j]*j + [k]*k
                        if not lst:
                            continue
                        for p in permutations(lst):
                            ans.add(int(''.join(map(str, p))))
        ans = sorted(ans)
        return ans[bisect_right(ans, n)]

class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        l, tmp = 0, n
        while tmp > 0:
            l += 1
            tmp //= 10
        ans = []
        path1, path2 = [], []
        def perm(digits: dict): # 考慮重複物排列
            if all(v == 0 for v in digits.values()):
                ans.append(int(''.join(map(str, path2))))
                return
            for k, v in digits.items():
                if v <= 0:
                    continue
                path2.append(k)
                digits[k] -= 1
                perm(digits)
                digits[k] += 1
                path2.pop()

        def backtrack(d: int): # 符合題目的數字
            if sum(path1) > d: # 超過要求的位數
                return
            if sum(path1) == d: # 符合要求的位數
                cnt = {i:i for i in path1}
                perm(cnt)
                return
            last = path1[-1] if path1 else 0
            for i in range(last+1, 10):
                path1.append(i)
                backtrack(d)
                path1.pop()
        
        if l > 0:
            backtrack(l)
        backtrack(l+1)

        ans.sort()
        return ans[bisect_right(ans, n)]

🟢 94. Binary Tree Inorder Traversal

題意

給定一個Binary Tree的樹根 $root$ ，返回其Inorder Traversal的結果。

思路

就是DFS的中序遍歷，先遍歷左子樹，再遍歷根節點，最後遍歷右子樹。

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def inorder(root):
            if root:
                inorder(root.left)
                ans.append(root.val)
                inorder(root.right)
        inorder(root)
        return ans

2023-12-10

🟢 70. Climbing Stairs

題意

從第 $0$ 階爬到第 $n$ 階，每次只能爬 $1$ 階或 $2$ 階，求有幾種不同的爬法。

思路：DP

因為每次只能爬 $1$ 階或 $2$ 階，所以爬到第 $n$ 階的方法數，等於爬到第 $n-1$ 階的方法數加上爬到第 $n-2$ 階的方法數。轉移方程為 $dp[n] = dp[n-1] + dp[n-2]$ ，初始條件為 $dp[0] = dp[1] = 1$ 。

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[0] = dp[1] = 1
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

🟢 867. Transpose Matrix

題意

給定一個二維陣列 $matrix$ ，返回 $matrix$ 的轉置矩陣。

思路

直接模擬即可。

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        ans = [ [0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                ans[i][j] = matrix[j][i]
        return ans