📝 LeetCode 簡單題目學習筆記

💪 魚～加油呀！呀呀呀、一起來刷題吧！

1️⃣ Two Sum

簡單 Array Hash Table

題目：給定一個整數陣列 nums 和一個目標值 target，找出兩個數使它們相加等於 target，返回這兩個數的索引。

思路：

暴力解：兩層迴圈 O(n²)
優化：使用 Hash Table 記錄已遍歷的值，一層迴圈 O(n)
關鍵：target - nums[i] 是否在表中

程式碼：

class Solution:
    def twoSum(self, nums, target):
        seen = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i
        return []

延伸：

Three Sum（LeetCode 15）
Four Sum（LeetCode 18）

2️⃣ Valid Parentheses

簡單 Stack String

題目：判斷一個只包含 ()[]{} 的字串是否為有效的括號組合。

思路：

使用 Stack（堆疊）處理
左括號 push 進堆疊
右括號時檢查堆疊頂端是否匹配
最後堆疊必須為空

程式碼：

class Solution:
    def isValid(self, s):
        stack = []
        mapping = {')': '(', '}': '{', ']': '['}
        for char in s:
            if char in mapping:
                if stack and stack[-1] == mapping[char]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(char)
        return not stack

延伸：

Longest Valid Parentheses（LeetCode 32）
Generate Parentheses（LeetCode 22）

3️⃣ Merge Two Sorted Lists

簡單 Linked List Recursion

題目：合併兩個已排序的鏈結串列，回傳合併後的結果。

思路：

使用虛擬頭節點（dummy node）簡化操作
比較兩列表頭，取較小的接上去
遞迴或迭代完成合併

程式碼：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode()
        current = dummy
        while l1 and l2:
            if l1.val < l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
        current.next = l1 if l1 else l2
        return dummy.next

延伸：

Merge k Sorted Lists（LeetCode 23）
Sort List（LeetCode 148）

4️⃣ Best Time to Buy and Sell Stock

簡單 Array Dynamic Programming

題目：給定股價陣列，找出只買一次賣一次的最大利潤。

思路：

只遍歷一次，記錄目前的最低價和最大利潤
利潤 = 當前價格 - 最低價
時間 O(n)，空間 O(1)

程式碼：

class Solution:
    def maxProfit(self, prices):
        min_price = float('inf')
        max_profit = 0
        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)
        return max_profit

延伸：

Best Time to Buy and Sell Stock II（LeetCode 122）
Best Time to Buy and Sell Stock III（LeetCode 123）

5️⃣ Palindrome Number

簡單 Math

題目：判斷一個整數是否是回文數（正著讀和反著讀一樣）。

思路：

負數不可能是回文
反轉後半數字與前半比較
不用字串，直接數學運算

程式碼：

class Solution:
    def isPalindrome(self, x):
        if x < 0:
            return False
        original = x
        reversed_num = 0
        while x:
            reversed_num = reversed_num * 10 + x % 10
            x //= 10
        return original == reversed_num

延伸：

Palindromic Substrings（LeetCode 647）
Longest Palindromic Substring（LeetCode 5）

6️⃣ Longest Common Prefix

簡單 String

題目：找出一組字串中最長的共同前綴。

思路：

縱向掃描：比較每個字元的第 i 個字母
或縱向掃描：先找最短的字串作為基準

程式碼：

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        shortest = min(strs, key=len)
        for i, char in enumerate(shortest):
            for s in strs:
                if s[i] != char:
                    return shortest[:i]
        return shortest

延伸：

Longest Common Subsequence（LeetCode 1143）

7️⃣ Valid Anagram

簡單 String Hash Table Sorting

題目：判斷兩個字串是否為字謎（字母排列相同）。

思路：

方法一：排序後比較 O(n log n)
方法二：26 個字母計數 O(n)

程式碼：

class Solution:
    def isAnagram(self, s, t):
        if len(s) != len(t):
            return False
        count = [0] * 26
        for char in s:
            count[ord(char) - ord('a')] += 1
        for char in t:
            count[ord(char) - ord('a')] -= 1
            if count[ord(char) - ord('a')] < 0:
                return False
        return True

延伸：

Group Anagrams（LeetCode 49）

8️⃣ Search Insert Position

簡單 Array Binary Search

題目：在排序陣列中找到 target 的位置，或返回應該插入的位置。

思路：

二分搜尋 O(log n)
左閉右開區間 [left, right)

程式碼：

class Solution:
    def searchInsert(self, nums, target):
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

延伸：

Search in Rotated Sorted Array（LeetCode 33）
First Bad Version（LeetCode 278）

9️⃣ Maximum Subarray

簡單 Array Dynamic Programming Kadane's Algorithm

題目：找出陣列中連續子陣列的最大和。

思路：

Kadane's Algorithm（卡登演算法）
動態規劃：dp[i] = max(nums[i], dp[i-1] + nums[i])

程式碼：

class Solution:
    def maxSubArray(self, nums):
        max_sum = current = nums[0]
        for i in range(1, len(nums)):
            current = max(nums[i], current + nums[i])
            max_sum = max(max_sum, current)
        return max_sum

延伸：

Maximum Product Subarray（LeetCode 152）
Best Time to Buy and Sell Stock

🔟 Contains Duplicate

簡單 Array Hash Table

題目：判斷陣列中是否有重複的元素。

思路：

方法一：Set 檢查 O(n) 時間 O(n) 空間
方法二：排序後檢查相鄰 O(n log n)

程式碼：

class Solution:
    def containsDuplicate(self, nums):
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

延伸：

Contains Duplicate II（LeetCode 219）
Contains Duplicate III（LeetCode 220）

1️⃣1️⃣ Plus One

簡單 Array Math

題目：給定一個由數字組成的非空陣列，代表一個非負整數。將這個數字加一。最高位數字存在於陣列的頭部。

思路：

從陣列末尾開始遍歷
處理進位 carry
如果最後有進位，需要在陣列前面插入 1

程式碼：

class Solution:
    def plusOne(self, digits):
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits
            digits[i] = 0
        return [1] + digits

延伸：

Add Two Numbers（LeetCode 2）
Plus One Linked List（LeetCode 369）

1️⃣2️⃣ Move Zeroes

簡單 Array Two Pointers

題目：將陣列中的所有 0 移到最后，同時保持非零元素的相對順序。

思路：

使用雙指針，一個指針指向下一個非零元素應該放置的位置
另一個指針遍歷陣列
只需 O(n) 時間和 O(1) 空間

程式碼：

class Solution:
    def moveZeroes(self, nums):
        insert_pos = 0
        for num in nums:
            if num != 0:
                nums[insert_pos] = num
                insert_pos += 1
        while insert_pos < len(nums):
            nums[insert_pos] = 0
            insert_pos += 1

延伸：

Remove Element（LeetCode 27）
Partition Array（LeetCode 面试题 21）

📊 題目分類整理

類型	題目
Array	Two Sum, Best Time, Max Subarray, Contains Duplicate
String	Valid Parentheses, Longest Common Prefix, Valid Anagram
Linked List	Merge Two Sorted Lists
Hash Table	Two Sum, Valid Anagram, Contains Duplicate
Two Pointers	Merge Two Sorted Lists
Binary Search	Search Insert Position
Dynamic Programming	Best Time, Max Subarray

✅ 解題技巧總結

Hash Table - 快速查找 O(1)
Two Pointers - 陣列/串列操作
Sliding Window - 連續子陣列問題
Binary Search - 排序陣列
Stack - 括號、嵌套結構
DP - 最優化問題

💪 魚～慢慢來呀！一題一題刷，不急的呀！呀呀呀、你可以的！

✅ 完成學習

完成本教材後，點擊下方按鈕記錄你的學習進度！