Skip to content

README.md

Latest commit

 

History

History
361 lines (296 loc) · 10.2 KB

README.md

File metadata and controls

361 lines (296 loc) · 10.2 KB
Raw

演算法 (Algorithms)

目錄 (Table of Contents)

    1. 陣列 (Array) / 字串 (String)
    • 字串操作 (String Operation)
        1. Merge Strings Alternately (Easy)
        1. Greatest Common Divisor of Strings (Easy)
        1. Reverse Vowels of a String (Easy)
        1. Reverse Words in a String (Medium)
        1. String Compression (Medium)
    • 陣列操作 (Array Operation)
        1. Kids With the Greatest Number of Candies (Easy)
        1. Can Place Flowers (Easy)
        1. Increasing Triplet Subsequence (Medium)
    1. 雙指針 (Two Pointers)
    • 同向雙指針 (Same Direction)
        1. Move Zeroes (Easy)
        1. Is Subsequence (Easy)
    • 相向雙指針 (Opposite Direction)
        1. Container With Most Water (Medium)
        1. Max Number of K-Sum Pairs (Medium)
    1. 滑動視窗 (Sliding Window)
    • 固定視窗 (Fixed Window)
        1. Maximum Average Subarray I (Easy)
        1. Maximum Number of Vowels in a Substring of Given Length (Medium)
    • 可變視窗 (Variable Window)
        1. Max Consecutive Ones III (Medium)
        1. Longest Subarray of 1's After Deleting One Element (Medium)
    1. 前綴和 (Prefix Sum)
    • 前綴和應用 (Prefix Sum Application)
        1. Find the Highest Altitude (Easy)
        1. Find Pivot Index (Easy)
        1. Product of Array Except Self (Medium)
    1. 雜湊表 (Hash Map / Set)
    • 集合運算 (Set Operations)
        1. Find the Difference of Two Arrays (Easy)
        1. Determine if Two Strings Are Close (Medium)
    • 計數統計 (Frequency Count)
        1. Unique Number of Occurrences (Easy)
        1. Equal Row and Column Pairs (Medium)
    1. 堆疊 (Stack)
    • 字串操作 (String Operation)
        1. Removing Stars From a String (Medium)
        1. Decode String (Medium)
    • 模擬 (Simulation)
        1. Asteroid Collision (Medium)
    • 6.1. 單調堆疊 (Monotonic Stack)
      • 序列問題 (Sequence Problem)
          1. Daily Temperatures (Medium)
          1. Online Stock Span (Medium)
    1. 佇列 (Queue)
    • 佇列應用 (Queue Application)
        1. Number of Recent Calls (Easy)
        1. Dota2 Senate (Medium)
    1. 鏈結串列 (Linked List)
    • 節點操作 (Node Operation)
        1. Reverse Linked List (Easy)
        1. Delete the Middle Node of a Linked List (Medium)
        1. Odd Even Linked List (Medium)
    • 雙指針應用 (Two Pointers Application)
        1. Maximum Twin Sum of a Linked List (Medium)
    1. 二元樹 (Binary Tree)
    • 9.1. 深度優先搜尋 (DFS)
      • 樹的屬性 (Tree Properties)
          1. Maximum Depth of Binary Tree (Easy)
          1. Leaf-Similar Trees (Easy)
          1. Count Good Nodes in Binary Tree (Medium)
          1. Longest ZigZag Path in a Binary Tree (Medium)
      • 路徑問題 (Path Problem)
          1. Path Sum III (Medium)
          1. Lowest Common Ancestor of a Binary Tree (Medium)
    • 9.2. 廣度優先搜尋 (BFS)
      • 層序遍歷 (Level Order Traversal)
          1. Binary Tree Right Side View (Medium)
          1. Maximum Level Sum of a Binary Tree (Medium)
    1. 二元搜尋樹 (Binary Search Tree)
    • 搜尋與修改 (Search and Modify)
        1. Search in a Binary Search Tree (Easy)
        1. Delete Node in a BST (Medium)
    1. 堆積 (Heap / Priority Queue)
    • 第 K 大/小元素 (Kth Largest/Smallest)
        1. Kth Largest Element in an Array (Medium)
        1. Smallest Number in Infinite Set (Medium)
    • 最優化選擇 (Optimization)
        1. Maximum Subsequence Score (Medium)
        1. Total Cost to Hire K Workers (Medium)
    1. 字典樹 (Trie)
    • 設計實作 (Design & Implementation)
        1. Implement Trie (Prefix Tree) (Medium)
    • 搜尋應用 (Search Application)
        1. Search Suggestions System (Medium)
    1. 圖 (Graph)
    • 13.1. 深度優先搜尋 (DFS)
      • 連通性問題 (Connectivity)
          1. Keys and Rooms (Medium)
          1. Number of Provinces (Medium)
      • 路徑問題 (Path Problem)
          1. Reorder Routes to Make All Paths Lead to the City Zero (Medium)
          1. Evaluate Division (Medium)
    • 13.2. 廣度優先搜尋 (BFS)
      • 最短路徑 (Shortest Path)
          1. Nearest Exit from Entrance in Maze (Medium)
          1. Rotting Oranges (Medium)
    1. 二元搜尋 (Binary Search)
    • 標準搜尋 (Standard Search)
        1. Guess Number Higher or Lower (Easy)
    • 搜尋答案範圍 (Search on Answer)
        1. Successful Pairs of Spells and Potions (Medium)
        1. Find Peak Element (Medium)
        1. Koko Eating Bananas (Medium)
    1. 回溯 (Backtracking)
    • 組合問題 (Combination)
        1. Letter Combinations of a Phone Number (Medium)
        1. Combination Sum III (Medium)
    1. 動態規劃 (Dynamic Programming)
    • 16.1. 一維 DP (1D DP)
      • 線性遞推 (Linear Recurrence)
          1. N-th Tribonacci Number (Easy)
          1. Min Cost Climbing Stairs (Easy)
          1. House Robber (Medium)
          1. Domino and Tromino Tiling (Medium)
    • 16.2. 多維 DP (Multidimensional DP)
      • 路徑問題 (Path Problem)
          1. Unique Paths (Medium)
      • 字串問題 (String Problem)
          1. Longest Common Subsequence (Medium)
          1. Edit Distance (Medium)
      • 股票問題 (Stock Problem)
          1. Best Time to Buy and Sell Stock with Transaction Fee (Medium)
    1. 位元操作 (Bit Manipulation)
    • 位元運算 (Bitwise Operation)
        1. Counting Bits (Easy)
        1. Single Number (Easy)
        1. Minimum Flips to Make a OR b Equal to c (Medium)
    1. 區間 (Intervals)
    • 貪婪區間 (Greedy Interval)
        1. Non-overlapping Intervals (Medium)
        1. Minimum Number of Arrows to Burst Balloons (Medium)

陣列 (Array) / 字串 (String)

初始化陣列，使用內建的 list 來建立動態陣列：

arr: list[int] = [1, 2, 3, 4, 5]
filled_arr: list[int] = [0] * 5

print(filled_arr)  # [0, 0, 0, 0, 0]


s = "Hello"
lst = list(s)

print(lst)  # ['H', 'e', 'l', 'l', 'o']

訪問元素：

arr: list[int] = [1, 2, 3, 4, 5]

print(arr)  # [1, 2, 3, 4, 5]
print(arr[0])  # 1
print(arr[-1])  # 5
print(arr[1:4])  # [2, 3, 4]  ← 切片 (Slicing)


s = "Hello"

print(s[0])  # H
print(s[-1])  # o
print(s[1:4])  # ell  ← 切片 (Slicing)

插入元素：

arr: list[int] = [1, 2, 3, 4, 5]
arr.append(6)
print(arr)  # [1, 2, 3, 4, 5, 6]

arr: list[int] = [1, 2, 3, 4, 5]
arr.insert(0, 99)
print(arr)  # [99, 1, 2, 3, 4, 5]

arr: list[int] = [1, 2, 3, 4, 5]
arr.extend([6, 7, 8, 9, 10])
print(arr)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

arr: list[int] = [1, 2, 3, 4, 5]
new_arr = arr + [6, 7, 8, 9, 10]
print(new_arr)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

刪除元素：

arr: list[int] = [1, 2, 3, 4, 5]
arr.remove(3)
print(arr)  # [1, 2, 4, 5]

arr: list[int] = [1, 2, 3, 4, 5]
val = arr.pop()  # 移除最後一個
print(f"val = {val}, arr = {arr}")  # val = 5, arr = [1, 2, 3, 4]

arr: list[int] = [1, 2, 3, 4, 5]
val = arr.pop(1)  # 移除 index 1
print(f"val = {val}, arr = {arr}")  # val = 2, arr = [1, 3, 4, 5]

arr: list[int] = [1, 2, 3, 4, 5]
del arr[0]  # 刪除 index 0
print(arr)  # [2, 3, 4, 5]

arr: list[int] = [1, 2, 3, 4, 5]
del arr[1:3]  # 刪除 index 1~2
print(arr)  # [1, 4, 5]

arr: list[int] = [1, 2, 3, 4, 5]
arr.clear()
print(arr)  # []

走訪陣列：

arr: list[int] = [10, 20, 30, 40, 50]

for idx, val in enumerate(arr):
    print(f"index = {idx}, value = {val}")

# index = 0, value = 10
# index = 1, value = 20
# index = 2, value = 30
# index = 3, value = 40
# index = 4, value = 50

雙指標 (Two Pointers) 走訪：

arr = [1, 2, 3, 4, 5]
left, right = 0, len(arr) - 1

while left <= right:
    print(f"left={arr[left]}, right={arr[right]}")
    left += 1
    right -= 1

# left = 1, right = 5
# left = 2, right = 4
# left = 3, right = 3

多陣列同步走訪：

names = ["Alice", "Bob", "Carol"]
scores = [60, 70, 90]

for name, score in zip(names, scores):
    print(f"{name}：{score} 分")

# Alice：60 分
# Bob：70 分
# Carol：90 分

題型

交替合併字串 (1768. Merge Strings Alternately)

給你兩個字串 word1 和 word2。請你從 word1 開始，透過交替加上字母來合併字串。如果一個字串比另一個字串長，就將多出來的字母追加到合併後字串的結尾。

回傳合併後的字串。

範例 1：

輸入: word1 = "abc", word2 = "pqr"
輸出: "apbqcr"
說明: 字串合併情況如下所示:
word1: a   b   c
word2:   p   q   r
合併後: a p b q c r

範例 2：

輸入: word1 = "ab", word2 = "pqrs"
輸出: "apbqrs"
說明: 注意，word2 比 word1 長，"rs" 需要追加到合併後字串的結尾。
word1: a   b
word2:   p   q   r   s
合併後: a p b q   r   s

範例 3：

輸入: word1 = "abcd", word2 = "pq"
輸出: "apbqcd"
說明: 注意，word1 比 word2 長，"cd" 需要追加到合併後字串的結尾。
word1: a   b   c   d
word2:   p   q
合併後: a p b q c   d
解題
from itertools import zip_longest


class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        return "".join(a + b for a, b in zip_longest(word1, word2, fillvalue=""))


# ========== 測試 ==========
sol = Solution()
print(sol.mergeAlternately("abc", "pqr"))  # "apbqcr"
print(sol.mergeAlternately("ab", "pqrs"))  # "apbqrs"
print(sol.mergeAlternately("abcd", "pq"))  # "apbqcd"

使用雙指標 (Two Pointers)：

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        i, j = 0, 0
        result: list[str] = []

        # 雙指標：兩字串都未耗盡時，交替取字元
        while i < len(word1) and j < len(word2):
            result.append(word1[i])  # 先取 word1 的字元
            result.append(word2[j])  # 再取 word2 的字元
            i += 1
            j += 1

        # 附加剩餘部分（最多只有一個字串有剩餘）
        result.append(word1[i:])  # 若 word1 較長，附加其餘部分
        result.append(word2[j:])  # 若 word2 較長，附加其餘部分

        return "".join(result)


# ========== 測試 ==========
sol = Solution()
print(sol.mergeAlternately("abc", "pqr"))  # "apbqcr"
print(sol.mergeAlternately("ab", "pqrs"))  # "apbqrs"
print(sol.mergeAlternately("abcd", "pq"))  # "apbqcd"

鏈結串列 (Linked List)