置頂

我的 VPython 教學文件 (HackMD 版本)

VPython 教學文件目錄 安裝及測試 基本語法 等速度直線運動 自由落下 終端速度 水平抛射 使用For迴圈計算水平抛射資料 斜向抛射 圓周運動 簡諧運動 單擺 木塊彈簧系統分離 重力及簡諧 行星運動 相疊木塊 雙重簡諧運動 一維彈性碰撞 ...

熱門文章

2026年9月28日 星期一

ZeroJudge 解題筆記:c381.聖經密碼

作者:王一哲
日期:2026年9月28日


ZeroJudge 題目連結:c381.聖經密碼

解題想法


題目是多筆測資。每組測資第一行是兩個整數 $n, m$,如果 $n, m$ 皆為 $0$ 代表測資結束。接下來用 $n$ 行,每行一個字串,要將這些字串接成一個很長的字串 $s$。下一行有 $m$ 個整數,代表從 $s$ 之中取出字元的位置,這些位置由 $1$ 開始計算,轉成索引值要 $-1$。將取出的字元接成一個字串 $t$,最後印出 $t$。

這題我最早是在2024年10月2日寫過的,最近看到題目更新了,才在2026年9月28日回來重寫,但是原來可以 AC 的 Python 程式碼卻會吃 TLE,後來改用 sys 加速輸入、輸出才 AC,可能題目更新後測資量變很大吧!

Python 程式碼


2024年10月2日測試,解題時間約為 0.2 s,使用記憶體約為 12.9 MB。但是2026年9月28日題目更新後測試,TLE。
while True:
    n, m = map(int, input().split())  # 字串數量 n,索引值數量 m
    if n == 0 and m == 0: break  # 中止程式的條件
    s = ""  # 字串內容
    for _ in range(n): s += input()  # 讀取 n 行字串
    t = ""  # 答案
    indices = list(map(int, input().split()))  # 索引值,1-indexed
    for idx in indices: t += s[idx - 1]  # 組合答案
    print(t)


2026年9月28日題目更新後測試,解題時間約為 71 ms,使用記憶體約為 26.4 MB。
def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield part
    
    data = get_tokens()
    
    while True:
        n = int(next(data))  # 字串數量 n
        m = int(next(data))  # 索引值數量 m
        
        if n == 0 and m == 0: break  # 中止程式的條件
        
        s = "".join(next(data) for _ in range(n))  # 字串內容
        
        t = [s[int(next(data)) - 1] for _ in range(m)]  # 組合答案
            
        sys.stdout.write(f"{"".join(t)}\n")
    
if __name__ == "__main__":
    solve()


LeetCode 解題筆記:1614. Maximum Nesting Depth of the Parentheses

作者:王一哲
日期:2026年9月28日


LeetCode 題目連結:1614. Maximum Nesting Depth of the Parentheses

解題想法


簡單題。題目給一個字串 $s$,長度為 1 到 100,內容只有數字 0 到 9、+-*/(),計算括號的最大深度。雖然看起來字串內容很複雜,但實際上只要數括號數量即可,不需要管算式內容。假設左括號數量為 $left$、最大深度為 $imax$,用一個 for 迴圈依序讀取字串的字元 $c$,如果 $c$ 是 (,$left$ 加 1,更新 $imax$;如果 $c$ 是 ),$left$ 減 1。

Python 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 19.24 MB, beats 50.40%.
class Solution:
    def maxDepth(self, s: str) -> int:
        left, imax = 0, 0
        for c in s:
            if c == '(':
                left += 1
                imax = max(imax, left)
            elif c == ')':
                left -= 1
        return imax


C++ 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 8.42 MB, beats 24.11%.
class Solution {
public:
    int maxDepth(string s) {
        int left = 0, imax = 0;
        for(char c : s) {
            if (c == '(') {
                left++;
                imax = max(imax, left);
            } else if (c == ')') {
                left--;
            }
        }
        return imax;
    }
};


2026年9月27日 星期日

LeetCode 解題筆記:1190. Reverse Substrings Between Each Pair of Parentheses

作者:王一哲
日期:2026年9月27日


LeetCode 題目連結:1190. Reverse Substrings Between Each Pair of Parentheses

解題想法


中等難度題。題目給一個字串 $s$,$s$ 之中只有小寫英文字母及 (、),括號一定成對,有巢狀結構,也就是左、右括號之間有其它的括號。要將每一對括號之間的子字串反序,回傳處理完的字串。以 (u(love)i) 為例,先處理最裡面的括號,將 love 反序後變成 evol;再處理外面的括號,原來的字串為 uevoli,反序後變成 iloveu。

這題很適合用堆疊 (stack) 處理。先建一個堆疊 $st$ 並放入空字串。用一個 for 迴圈依序讀取 $s$ 的字元 $c$,依照 $c$ 的值分為 3 種狀況:
  1. 左括號,新的區段,$st$ 加入空字串。
  2. 右括號,結算最後一個區段。移除 $st$ 最後一項,暫存到 $t$。$t$ 反序後接到 $st$ 最後一項。
  3. 字母,$c$ 接到 st 最後一項。
答案會在 $st$ 首項。

Python 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 19.26 MB, beats 69.70%.
class Solution:
    def reverseParentheses(self, s: str) -> str:
        st = [""]  # 儲存每一對括號內容的堆疊,先放入空字串

        for c in s:  # 依序讀取 s 的字元 c
            if c == '(':  # 左括號
                st.append("")  # 新的區段,st 加入空字串
            elif c == ')':  # 右括號,結算最後一個區段
                t = st.pop()  # 移除 st 最後一項,暫存到 t
                st[-1] += t[::-1]  # t 反序後接到 st 最後一項
            else:  # 字母
                st[-1] += c  # 接到 st 最後一項
        return st[0]  # 答案會在 st 首項


2026年9月26日 星期六

LeetCode 解題筆記:1807. Evaluate the Bracket Pairs of a String

作者:王一哲
日期:2026年9月26日


LeetCode 題目連結:1807. Evaluate the Bracket Pairs of a String

解題想法


中等難度題,如果會使用 Python dict 或是 C++ map、unordered_map 物件,這題算相對簡單。題目給一個字串 $s$,$s$ 之中只有小寫英文字母及 (、),括號一定成對,而且沒有巢狀結構,也就是左、右括號之間不會有其它的括號,這樣程式碼會很好寫。再給一個二維陣列 $knowledge$,每一組有兩個字串 $key, value$。檢查 $s$ 的內容,將一組括號之間的子字串 $sub$ 替換成 $knowledge$ 之中對應的字串,如果沒有對應的字串則替換成 ?。回傳替換後的字串。

首先為了便於查詢 $knowledge$ 之中 $key$ 對應的 $value$,建立一個字典物件 $words$,儲存 $key: value$。用變數 $pre$ 記錄目前已找到的左括號索引值,$-1$ 代表目前沒有左括號。替換後的答案存到 $res$。用一個 for 迴圈掃過字串 $s$,假設字元 $c = s[i]$,接下來有 3 種狀況:
  1. 如果 $c$ 是左括號,更新 $pre = i$。
  2. 如果 $c$ 是右括號,切下子字串 $sub = s[pre + 1 : i]$。如果 $sub$ 不在 $words$ 之中,將 ? 加入 $res$。如果 $sub$ 在 $words$ 之中,將對應的字串加入 $res$。
  3. 如果 $c$ 是字母,而且 $pre = -1$,將 $c$ 加入 $res$。
如果不想用 Python 的字串切片或是 C++ 的 substr,也可以修改以上第3種狀況的處理方式,如果 $c$ 是字母,再分成 $pre = -1$ 的將況,將 $c$ 加入 $res$;$pre \neq -1$,$c$ 加入 $sub$。同時要修改第2種狀況,結算完 $sub$ 之後要重設 $sub$,才能正確地處理下一個子字串。

Python 程式碼


Runtime: 47 ms, beats 69.16%. Memory: 51.39 MB, beats 81.62%.
class Solution:
    def evaluate(self, s: str, knowledge: list[list[str]]) -> str:
        words = {key: val for key, val in knowledge}  # knowledge 轉成字典
        n = len(s)  # 長度
        pre = -1  # 目前找到的 ( 索引值
        res = []  # 答案

        # 依序讀取 s 的字元
        for i in range(n):
            c = s[i]
            if c == '(':  # 找到 (,記錄索引值
                pre = i
            elif c == ')':  # 找到 )
                sub = s[pre + 1 : i]  # 切下 () 之間的子字串
                if sub not in words:  # sub 不在 words 之中,加上 ?
                    res.append("?")
                else:  # sub 在 words 之中,加上對應的值
                    res.append(words[sub])
                pre = -1  # 重設為 -1
            elif pre == -1:  # 找到字母而且目前沒有 (,直接將字母加到 res
                res.append(c)
        
        return "".join(res)  # 接成字串再回傳


2026年9月25日 星期五

LeetCode 解題筆記:764. Largest Plus Sign

作者:王一哲
日期:2026年9月25日


LeetCode 題目連結:764. Largest Plus Sign

解題想法


中等難度題,題目給一個正整數 $n$,代表一個 $n \times n$ 的二維陣列,陣列之中除了某些位置為 $0$,其它位置都是 $1$。再給一個二維陣列 $mines$,其中每一個元素為長度 $2$ 的陣列,代表數值為 $0$ 的位置。題目定義從 $n \times n$ 的二維陣列中找出 + 號大小的計算方式,從 + 中央開始為長度 1,向上、下、左、右延伸,如果 4 個方向都是 1 則長度加 1,如果任何一個方向是 0 就不能再延伸。題目要回傳最大的 + 大小。

首先為了便於查詢指定坐標是否在 mines 之中,如果用 Python 解題,可以先將 $mines$ 轉成 set 會比較快;如果用 C++ 解題,再開另一個二維陣列標記 0 的位置會比較快。接下來定義一個 $n \times n$ 的二維陣列 $dp$,用來記錄以每一格為中心的 + 最大長度,預設值皆設為 $n$。用 for 迴圈掃過 $i = 0$ 到 $i = n-1$;裡面再用一層 for 迴圈掃瞄水平方向,分別更新由左向右、由右向左掃的十字大小,再更新對應位置的 $dp$ 值;再用另用一個 for 迴圈掃瞄鉛直方向,分別更新由上向下、由下向上掃的十字大小,再更新對應位置的 $dp$ 值。全部更新完畢之後,答案為 $dp$ 之中的最大值。

Python 程式碼


Runtime: 1205 ms, beats 21.40%. Memory: 22.84 MB, beats 61.87%.
class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: list[list[int]]) -> int:
        # 轉成 set,查詢指定坐標是否在 mines 之中會比較快
        mineset = {tuple(mine) for mine in mines}
        dp = [[n]*n for _ in range(n)]  # 每一格最大的十字大小,預設為最大值 n
        
        for i in range(n):
            # 掃瞄水平方向
            lcnt, rcnt = 0, 0  # 左向右、右向左掃的十字大小
            for j in range(n):  # 改變欄坐標
                # 由左到右,如果 (i, j) 有地雷歸零,反之加 1
                lcnt = 0 if (i, j) in mineset else lcnt + 1
                dp[i][j] = min(dp[i][j], lcnt)

                # 由右到左,如果 (i, n-j-1) 有地雷歸零,反之加 1
                k = n-j-1
                rcnt = 0 if (i, k) in mineset else rcnt + 1
                dp[i][k] = min(dp[i][k], rcnt)
            
            # 掃瞄鉛直方向
            ucnt, dcnt = 0, 0  # 上向下、下向上掃的十字大小
            for j in range(n):  # 改變列坐標
                # 由上到下,如果 (j, i) 有地雷歸零,反之加 1
                ucnt = 0 if (j, i) in mineset else ucnt + 1
                dp[j][i] = min(dp[j][i], ucnt)

                # 由下到上,如果 (n-j-1) 有地雷歸零,反之加 1
                k = n-j-1
                dcnt = 0 if (k, i) in mineset else dcnt + 1
                dp[k][i] = min(dp[k][i], dcnt)
        
        # 掃過所有的格子找最大值
        ans = 0
        for i in range(n):
            for j in range(n):
                ans = max(ans, dp[i][j])
        return ans


2026年9月24日 星期四

LeetCode 解題筆記:3550. Smallest Index With Digit Sum Equal to Index

作者:王一哲
日期:2026年9月24日


LeetCode 題目連結:3550. Smallest Index With Digit Sum Equal to Index

解題想法


簡單題,題目一個整數陣列 $nums$,且 $0 \leq nums[i] \leq 1000$,長度小於等於 $100$,要找出 $nums$ 之中各個位數加總等於索引值的元素,如果有好幾個元素符合條件,回傳最小的索引值,如果沒有任何一個元素符合條件則回傳 $-1$。用一個 for 迴圈依序讀取每個元素,再用一個 while 迴圈或是轉成字串計算位數加總,如果位數加總等於索引值 $i$ 就回傳 $i$,不需要再跑之後的元素。如果 for 迴圈跑完還沒有找到符合條件的元素,回傳 $-1$。

Python 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 19.33 MB, beats 29.46%.
class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            num = nums[i]
            dsum = 0
            while num:
                dsum += num % 10
                num //= 10
            if dsum == i: return i
        return -1


用 enumerate 比較慢。Runtime: 2 ms, beats 65.51%. Memory: 19.36 MB, beats 29.46%.
class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            dsum = 0
            while num:
                dsum += num % 10
                num //= 10
            if dsum == i: return i
        return -1


轉成字串更慢。Runtime: 7 ms, beats 16.46%. Memory: 19.29 MB, beats 67.07%.
class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            dsum = sum(int(c) for c in str(num))
            if dsum == i: return i
        return -1


2026年9月23日 星期三

LeetCode 解題筆記:1658. Minimum Operations to Reduce X to Zero

作者:王一哲
日期:2026年9月23日


LeetCode 題目連結:1658. Minimum Operations to Reduce X to Zero

解題想法


中等難度題,題目一個正整數陣列 $nums$ 及一個正整數 $x$,每次操作時可以選擇 $nums$ 最前面或最後面一個數字,將 $x$ 減去這個數字並從 $nums$ 之中移除此項,如果要使 $x$ 歸零,最少的操作次數是幾次?如果無法歸零,回傳 $-1$。這題底下的提示很重要,如果真的按照題目的要求寫程式,要先計算 $nums$ 的前綴和 $psum$ 及後綴和 $ssum$,再從 $psum$ 及 $ssum$ 之中分別檢查使 $x$ 歸零需要取的數量,這樣寫很麻煩。提示中有說,改成計算連續子陣列的和,假設 $nums$ 加總為 $total$,則我們要找的連續子陣列和為 $target = total - x$,如果 $target = 0$ 回傳 $nums$ 的長度 $n$;如果 $target$ 是其它的值,則用滑動視窗找區間和等於 $target$ 的最長子陣列長度 $length$,答案為 $n - length$。

Python 程式碼


Runtime: 71 ms, beats 76.89%. Memory: 30.84 MB, beats 71.36%.
class Solution:
    def minOperations(self, nums: list[int], x: int) -> int:
        n = len(nums)  # 數量
        target = sum(nums) - x  # 最長子陣列和目標值,等於全部的元素加總 - x
        # 特例,如果目標值為 0,全部都要刪掉,回傳 n
        if target == 0: return n  
        
        # 一般狀況,用滑動視窗找加總等於目標值的最長子陣列
        ans = n + 1  # 答案設定成不可能的值 n + 1
        left = 0  # 左端點
        isum = 0  # 區間和
        for right in range(n):  # 掃過右端點 0 ~ n-1
            isum += nums[right]  # 更新區間和
            # 如果左、右端點未重合,區間和大於目標值,移除左端點
            while left < right and isum > target:
                isum -= nums[left]
                left += 1
            # 如果區間和等於目標值,更新答案
            if isum == target:
                length = right - left + 1
                ans = min(ans, n - length)
        # 如果答案不是預設值回傳答案,反之回傳 -1
        return ans if ans < n + 1 else -1


2026年9月22日 星期二

LeetCode 解題筆記:739. Daily Temperatures

作者:王一哲
日期:2026年9月22日


LeetCode 題目連結:739. Daily Temperatures

解題想法


中等難度題,題目一個表示每日氣溫的整數陣列 $temperatures$,要找出每一天要在幾天之後才會遇到更高的氣溫,如果之後沒有任何一天的氣溫更高,則當天的答案為 0。這題很適合用堆疊處理,開一個堆疊 $st$,用來記錄目前已經讀到、而且還沒有找到答案的氣溫及索引值。用一個 for 迴圈讀取每天的氣溫 $t$ 及索引值 $i$;再用一個 while 迴圈,如果 $st$ 之中有資料而且 $t$ 大於 $st$ 最後一項的氣溫,移除 $st$ 的最後一項,如果這項的索引值為 $pre$,則這項對應的答案為 $pre - i$;跑完 while 迴圈之後再加入 $(t, i)$。

Python 程式碼


Runtime: 97 ms, beats 50.76%. Memory: 34.32 MB, beats 21.54%.
class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        ans = [0] * len(temperatures)  # 答案
        st = []  # 堆疊,放入 (t, idx)
        
        for i, t in enumerate(temperatures):
            # 如果 st 有資料,t 大於 st 最後一項的溫度
            while st and t > st[-1][0]:
                pre = st.pop()[1]  # 移除 st 最後一項
                ans[pre] = i - pre  # 這項的索引值答案為 i - pre
            # (t, i) 加入 st
            st.append((t, i))
        return ans


2026年9月21日 星期一

LeetCode 解題筆記:3524. Find X Value of Array I

作者:王一哲
日期:2026年9月21日


LeetCode 題目連結:3524. Find X Value of Array I

解題想法


中等難度題,題目正整數陣列 $nums$、一個正整數 $k$,可以移 $nums$ 之中移除不重疊的前綴子陣列及後綴子陣列,使 $nums$ 乘下的元素積乘對 $k$ 取餘數,計算得到各種餘數有幾種方法數。題目下方有提示:
  1. 用動態規畫解題。
  2. 定義 $dp[i][r]$ 為以索引值 $i$ 為結尾的元素乘積,對 $k$ 取餘數為 $r$ 的方法數。
  3. 將每一個索引值的 $dp[i][r]$ 加起來,計算答案 $ans[r]$。
基本上按照提示寫程式碼,應該就可以得到答案。在更新 $dp$ 陣列的過程中,每次相乘後都要對 $k$ 取餘數,可以避免數字過大。而且更新 $dp$ 時只需要用到前一個數字的狀態,可以用滾動陣列節省記憶體。

Python 程式碼


Runtime: 435 ms, beats 26.32%. Memory: 46.36 MB, beats 19.74%.
class Solution:
    def resultArray(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        # dp[i][j] 代表以索引值 i-1 結尾,其元素乘積除以 k 餘數為 j 的子陣列數量
        dp = [[0]*k for _ in range(n+1)]
        ans = [0]*k  # 答案
        for i in range(1, n+1):
            # nums[i-1] 為長度 1 的子陣列
            rem = nums[i-1] % k
            dp[i][rem] = 1
            # 內層迴圈,跑 j = 0 ~ k-1,將目前的數字接在前一個結尾的子陣列之後
            for j in range(k):
                if dp[i-1][j] > 0:  # 如果有前一個結尾對應的子陣列數量
                    new_rem = (j * rem) % k
                    dp[i][new_rem] += dp[i-1][j]
            # 將這一回産生的答案都加到 ans
            for j in range(k):
                ans[j] += dp[i][j]
        # 回傳答案
        return ans


2026年9月20日 星期日

LeetCode 解題筆記:3498. Reverse Degree of a String

作者:王一哲
日期:2026年9月20日


LeetCode 題目連結:3498. Reverse Degree of a String

解題想法


簡單題,題目給一個字串 $s$,將 $s[i]$ 換算成 $26 - (s[i] - 'a')$,再乘以 $i+1$,將全部的值加起來並回傳,用一個 for 迴圈就解決了。

Python 程式碼


Runtime: 3 ms, beats 97.65%. Memory: 19.30 MB, beats 55.57%.
class Solution:
    def reverseDegree(self, s: str) -> int:
        ans = 0
        for i, c in enumerate(s, start=1):
            ans += (26 - ord(c) + ord('a')) * i
        return ans


Runtime: 3 ms, beats 97.65%. Memory: 19.32 MB, beats 19.13%.
class Solution:
    def reverseDegree(self, s: str) -> int:
        return sum((26 - ord(c) + ord('a')) * i for i, c in enumerate(s, start=1))