一個地球人在臺北

2026年8月1日星期六

LeetCode 解題筆記：486. Predict the Winner

作者：王一哲
日期：2026年8月1日

LeetCode 題目連結：486. Predict the Winner

解題想法

中等難度題。題目給一個陣列 $nums$，兩個玩家 A、B 每次行動時可以從 $nums$ 兩端選取並移除一個數字，獲得這個數字的分數，玩家 A 先行動，如果玩家 A 總分大於等於玩家 B，回傳 True。這題很適合用動態規畫解題，建立一個 $n \times n$ 的二維陣列 $dp[i][j]$ 代表可選數字剩下 $nums[i]$ ~ $nums[j]$ 時目前行動玩家與另一人的最大分差。更新狀態時有 2 種選擇：

行動1，選 $nums[i]$，新的區間為 $nums[i+1]$ ~ $nums[j]$，最大分差為 $nums[i] - dp[i+1][j]$
行動2，選 $nums[j]$，新的區間為 $nums[i] ~ nums[j-1]$，最大分差為 $nums[j] - dp[i][j-1]$

玩家採用最佳策略，從行動1、2之中選分數高的，因此 $$ dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) $$ 當 $i = j$ 時，只能選擇一個數字，$dp[i][j] = nums[i]$。更新 $dp$ 時，要從長度 $2$ 開始，直到長度等於 $n$ 為止，因為長度較長的狀態，是基於長度較短的狀態更新數值。更新完畢之後，如果 $dp[0][n-1] \geq 0$，玩家 A 獲勝，回傳 True。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.11 MB, beats 94.32%.

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        # 初始化 dp
        dp = [[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = nums[i]
        # 由長度 2 開始填表格，直到長度 n 為止
        for length in range(2, n+1):
            for i in range(n - length + 1):  # 起點
                j = i + length - 1  # 終點
                dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
        # 回傳答案
        return dp[0][n-1] >= 0

2026年7月31日星期五

LeetCode 解題筆記：3016. Minimum Number of Pushes to Type Word II

作者：王一哲
日期：2026年7月31日

LeetCode 題目連結：3016. Minimum Number of Pushes to Type Word II

解題想法

中等難度題，3014. Minimum Number of Pushes to Type Word I 的加強版，但是這題 $word$ 之中可以有相同的字母，需要修改一下程式碼。如果要求最低的次數，原則上是先處理 $word$ 之中數量多的字母，數量最多的前 8 個字母按 1 下，第二多的 8 個字母按 2 下，其餘依此類推。我在計算相異字母的數量時使用了，Python collections 函式庫的 Counter，這是專門用來計數的容器，速度很快；於 C++ 則是用 unordered_map，速度比較慢，改用表格計數快很多。

Python 程式碼

字典計數。Runtime: 91 ms, beats 89.97%. Memory: 19.91 MB, beats 77.26%.

class Solution:
    def minimumPushes(self, word: str) -> int:
        cnt = Counter(word)  # 計數器
        vals = sorted(cnt.values(), reverse=True)  # 各相異字母對應的數量
        n = len(vals)  # 相異字母數量
        idx = 0  # 從 vals 讀取資料的索引值
        ans = 0  # 答案
        cof = 1  # 要按幾下才能輸入一個字母
        while idx < n:
            m = 0  # 按 cof 下才能輸入的字母數量
            while idx < n and m < 8:  # 最多 8 個字母
                ans += cof * vals[idx]  # 答案加上 cof * 數量
                idx += 1  # 索引值加 1
                m += 1  # m 加 1
            cof += 1  # cof 加 1
        return ans

表格計數。Runtime: 175 ms, beats 39.47%. Memory: 19.86 MB, beats 93.65%.

class Solution:
    def minimumPushes(self, word: str) -> int:
        cnt = [0] * 26  # 計數器
        for c in word:
            cnt[ord(c) - ord('a')] += 1
        vals = sorted([val for val in cnt if val > 0], reverse=True)  # 各相異字母對應的數量
        n = len(vals)  # 相異字母數量
        idx = 0  # 從 vals 讀取資料的索引值
        ans = 0  # 答案
        cof = 1  # 要按幾下才能輸入一個字母
        while idx < n:
            m = 0  # 按 cof 下才能輸入的字母數量
            while idx < n and m < 8:  # 最多 8 個字母
                ans += cof * vals[idx]  # 答案加上 cof * 數量
                idx += 1  # 索引值加 1
                m += 1  # m 加 1
            cof += 1  # cof 加 1
        return ans

2026年7月30日星期四

LeetCode 解題筆記：3014. Minimum Number of Pushes to Type Word I

作者：王一哲
日期：2026年7月30日

LeetCode 題目連結：3014. Minimum Number of Pushes to Type Word I

解題想法

簡單題。題目給一個字串 $word$，仿照用電話按鈕輸入字母的方式，但可以重新分配數字按鈕對應的字母，要計算輸入入 $word$ 至少要按幾下。共有 8 個按鈕可以對應到字母，如果 $word$ 的長度 $n \leq 8$，可以將 $n$ 個字母分配給不同的按鈕，各按 1 下即可；如果 $n > 8$，先處理 8 個字母，$n$ 更新為 $n-8$，下一步最多處理 8 個字母，各按 2 下即可輸入；重複以上的過程直到沒有字母需要輸入為止。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.18 MB, beats 83.33%.

class Solution:
    def minimumPushes(self, word: str) -> int:
        n = len(word)  # 字串長度
        ans, cof = 0, 1  # 答案，要按幾下才能輸入一個字母
        while n > 0:
            if n > 8:  # 剩下超過 8 個字母
                ans += 8 * cof  # 答案加上 8 * cof
                cof += 1  # cof 加 1
                n -= 8  # 字母數量減 8
            else:  # 剩下不到 8 個字母
                ans += n * cof  # 答案加上 n * cof
                n = 0  # 歸零
        return ans

2026年7月29日星期三

LeetCode 解題筆記：6. Zigzag Conversion

作者：王一哲
日期：2026年7月29日

LeetCode 題目連結：6. Zigzag Conversion

解題想法

中等難度題。題目給一個字串 $s$、列數 $numRows$，要找出共有 $numRows$ 列的之字形排列字串。我先用一個 $numRows$ 列的陣列儲存每一列的字串內容，最後再把陣列內容接成一個很長的字串後回傳，主要的工作是在計算目前這個字元應該填在陣列中的哪一列。

Python 程式碼

Runtime: 7 ms, beats 84.25%. Memory: 19.24 MB, beats 79.60%.

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # 特例，只有一列，直接輸出 s
        if numRows == 1: return s
        # 一般狀況
        n = len(s)  # 長度
        grid = [""] * numRows  # 儲存答案用的串列
        r, d = 0, 0  # 目前所在的列，方向
        for ch in s:  # 依序讀取字元
            grid[r] += ch  # 加入字元 ch
            if d == 0:  # 向下移動
                r += 1
                if r == numRows - 1: d = 1  # 走到最下方，改成向上走
            else:  # 向上移動
                r -= 1
                if r == 0: d = 0  # 走到最上方，改成向下走
        # 從 grid 讀取字串，組合成字串 t 再回傳
        return "".join(grid)

2026年7月28日星期二

LeetCode 解題筆記：3517. Smallest Palindromic Rearrangement I

作者：王一哲
日期：2026年7月28日

LeetCode 題目連結：3517. Smallest Palindromic Rearrangement I

解題想法

中等難度題，題目給一個迴文字串 $s$，要將 $s$ 重新排列成字典序最小的迴文字串。我一開始想到的寫法，是先計算各個字母的數量，如果字串 $s$ 長度 $n$ 為奇數，則所有的字母之中只有一個字母的數量是奇數。接下來依照字典序及數量産生需要使用的字母，開一個長度為 $n$ 的串列 $arr$ 儲存答案，由串列兩端向中央依序填入字母。如果 $n$ 是奇數，則 $arr$ 中央再填入唯一的奇數數量字母。最後將 $arr$ 組成字串後回傳。不過這樣寫實在太慢。

後來想到題目給的字串 $s$ 本身就是迴文字串，只要取 $s$ 的左半邊子字串 $left$ 再排序，答案的右半邊 $right$ 就是 $left$ 反序。如果 $s$ 的長度 $n$ 是奇數，$left$ 及 $right$ 之中再加上 $s[n/2]$ 即可。這個寫法的速度快很多。

Python 程式碼

Runtime: 375 ms, beats 21.66%. Memory: 22.32 MB, beats 5.07%.

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        n = len(s)
        cnt = Counter(s)
        chars = []
        odd = ""  # 奇數數量字母
        # 依照字母順序取出數量為偶數的字母
        for ch, val in sorted(cnt.items()):
            if val % 2 == 1:
                chars += [ch] * (val - 1)
                odd = ch
            else:
                chars += [ch] * val
        # 由兩側向中央填入字母
        arr = [""] * n
        for i in range(n//2):
            arr[i] = arr[n-i-1] = chars[i*2]
        # 奇數長度，中間放唯一一個奇數數量的字母
        if n%2 == 1:  
            arr[n//2] = odd
        # 組成字串再回傳
        return "".join(arr)

Runtime: 247 ms, beats 59.91%. Memory: 20.66 MB, beats 91.71%.

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        n = len(s)
        left = "".join(sorted(s[:n//2]))  # 取左半邊字母並排序
        if n%2 == 1:  # 奇數長度
            return left + s[n//2] + left[::-1]  # 右半邊字母為左半邊字母反序，加上中間的字母
        else:
            return left + left[::-1]  # 右半邊字母為左半邊字母反序

2026年7月27日星期一

LeetCode 解題筆記：1464. Maximum Product of Two Elements in an Array

作者：王一哲
日期：2026年7月17日

LeetCode 題目連結：1464. Maximum Product of Two Elements in an Array

解題想法

簡單題。題目給一個陣列 $nums$，取出其中 2 個數字 $nums[i], nums[j]$，回傳 $(nums[i] - 1) \times (nums[j] - 1)$ 的最大值。由於這題的數值範圍是 $1 \leq nums[i] \leq 1000$，不需要考慮兩個負數相乘的狀況，只要用一個 for 迴圈掃過 $nums$，取出 2 個最大的數字 $a, b$，回傳 $(a-1) \times (b-1)$ 即可。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.20 MB, beats 68.04%.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        a, b = -1, -1
        for num in nums:
            if num > a:
                a, b = num, a
            elif num > b:
                b = num
        return (a-1) * (b-1)

2026年7月26日星期日

LeetCode 解題筆記：628. Maximum Product of Three Numbers

作者：王一哲
日期：2026年7月26日

LeetCode 題目連結：628. Maximum Product of Three Numbers

解題想法

簡單題。題目給一個陣列 $nums$，且 $-1000 \leq nums[i] \leq 1000$，從 $nums$ 之中選取 3 個數字相乘，回傳乘積最大值。先將 $nums$ 由小到大排序，答案可能是選最大的 3 個正整數相乘，或是選 1 個最大的正整數及2 個最小的負整數相乘，回傳兩種選擇的最大值。但是排序的時間複雜度為 $O(n \log n)$，如果想要將時間複雜度降到 $O(n)$ 就不能排序，改用 for 迴圈掃過 $nums$，用 if 更新最大的 3 個數字及最小的 2 個數字，最後再計算乘積最大值。

Python 程式碼

排序。Runtime: 19 ms, beats 64.08%. Memory: 20.50 MB, beats 17.11%.

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        return max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[-1])

for 迴圈。Runtime: 4 ms, beats 95.92%. Memory: 20.28 MB, beats 78.13%.

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        a = b = c = float('-inf')  # 最大的 3 個數字
        d = e = float('inf')  # 最小的 2 個數字
        for num in nums:
            if num >= a:  # 新的最大值
                a, b, c = num, a, b
            elif num >= b:  # 新的第二大
                b, c = num, b
            elif num > c:  # 新的第三大
                c = num
            if num <= e:  # 新的最小值
                e, d = num, e
            elif num < d:  # 新的第二小
                d = num
        return max(a*b*c, a*d*e)

2026年7月25日星期六

LeetCode 解題筆記：3536. Maximum Product of Two Digits

作者：王一哲
日期：2026年7月25日

LeetCode 題目連結：3536. Maximum Product of Two Digits

解題想法

簡單題。題目給一個數字 $n$，取出 $n$ 之中任意兩個數字相乘，回傳乘積最大值。基本上就是要找出最大的兩個數字相乘，我是用變數 $a$ 儲存最大的數字，變數 $b$ 儲存第二大的數字，用一個 while 迴圈檢查 $n$ 的每個數字，找出 $a, b$ 的乘，最後回傳 $a \times b$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.40 MB, beats 22.61%.

class Solution:
    def maxProduct(self, n: int) -> int:
        a, b = 0, 0  # 最大、第二大的數字
        while n > 0:
            d = n % 10
            n //= 10
            if d > a:  # 新的最大值
                a, b = d, a
            elif d > b:  # 新的第二大
                b = d
        return a*b

2026年7月24日星期五

LeetCode 解題筆記：3514. Number of Unique XOR Triplets II

作者：王一哲
日期：2026年7月24日

LeetCode 題目連結：3514. Number of Unique XOR Triplets II

解題想法

中等難度題。題目給一個陣列 $nums$，要找出從 $nums$ 之中任意取 3 個數字計算 XOR 的結果共有幾個，取的數字可以重複。由於答案只要不重複的計算結果數量，很適合用集合儲存計算結果。這題基本上就是硬算，大約分成以下的步驟：

將 $nums$ 轉成集合，移除重複的數字，存入 uni_nums。
由 uni_nums 任意取兩個數字計算 XOR，存入 uni_pairs。
由 uni_pairs 取一個數字，由 uni_nums 取一個數字，計算 XOR，存入 uni_triplets。
回傳 uni_triplets 的長度。

Python 程式碼

Runtime: 5873 ms, beats 64.81%. Memory: 19.72 MB, beats 22.22%.

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        uni_nums = set(nums)  # 不重複的數字
        # 由提示2、3，任意選兩個數字計算 XOR
        uni_pairs = {x^y for x in uni_nums for y in uni_nums}
        # 取出 uni_pairs 之中一個數字與 uni_nums 之中一個數字計算 XOR
        uni_triplets = {p^z for p in uni_pairs for z in uni_nums}
        # 回傳答案
        return len(uni_triplets)

Runtime: 6679 ms, beats 61.11%. Memory: 19.70 MB, beats 46.30%.

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        uni_nums = set(nums)  # 不重複的數字
        # 由提示2、3，任意選兩個數字計算 XOR
        uni_pairs = set()
        for y in uni_nums:
            for x in uni_nums:
                uni_pairs.add(x^y)
        # 取出 uni_pairs 之中一個數字與 uni_nums 之中一個數字計算 XOR
        uni_triplets = set()
        for p in uni_pairs:
            for z in uni_nums:
                uni_triplets.add(p^z)
        # 回傳答案
        return len(uni_triplets)

2026年7月23日星期四

LeetCode 解題筆記：3513. Number of Unique XOR Triplets I

作者：王一哲
日期：2026年7月23日

LeetCode 題目連結：3513. Number of Unique XOR Triplets I

解題想法

中等難度題。這題考數學，題目給一個長度為 $n$ 的陣列 $nums$，且 $nums$ 的內容為任意排列的 $1$ 到 $n$，可以從 $nums$ 之中任取 3 個數字求 XOR，數字可以重複，求總共有幾個計算結果。這題如果用 3 層迴圈硬算一定會超時，要找出數學關係後直接輸出答案。如果 $n = 1$，只有 1 個計算結果 1^1^1 = 1。如果 $n = 2$，只有 2 個計算結果，例如 01^01^01 = 01, 01^01^10 = 10。如果 $n = 3$，最大值為 001^001^111 = 111，不可能超過 $111_2 = 8$，計算結果在 $0$ 到 $2^n - 1$ 之間，答案等於 $2^n$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 31.84 MB, beats 91.53%.

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        n = len(nums)
        # 特例，n = 1，1位數，只有 1^1^1 = 1
        if n == 1: return 1
        # 特例，n = 2，2位數，只有 01^01^01 = 1, 01^01^10 = 2
        if n == 2: return 2
        # 一般狀況，n >= 3，最大值為 n 個 1，即 2**n - 1，共有 2**n 個答案
        bits = n.bit_length()
        return 1 << bits

訂閱：文章 (Atom)

置頂

熱門文章

2026年8月1日 星期六

解題想法

Python 程式碼

2026年7月31日 星期五

解題想法

Python 程式碼

2026年7月30日 星期四

解題想法

Python 程式碼

2026年7月29日 星期三

解題想法

Python 程式碼

2026年7月28日 星期二

解題想法

Python 程式碼

2026年7月27日 星期一

解題想法

Python 程式碼

2026年7月26日 星期日

解題想法

Python 程式碼

2026年7月25日 星期六

解題想法

Python 程式碼

2026年7月24日 星期五

解題想法

Python 程式碼

2026年7月23日 星期四

解題想法

Python 程式碼

2026年8月1日星期六

2026年7月31日星期五

2026年7月30日星期四

2026年7月29日星期三

2026年7月28日星期二

2026年7月27日星期一

2026年7月26日星期日

2026年7月25日星期六

2026年7月24日星期五

2026年7月23日星期四