最後更新日期: 15/12/2024

🤔

　　相似的事物放一起，是讓環境井然有序的關鍵，這也是電腦世界中陣列（Array）此資料結構的設計理念。因為事物都在同處，我們可藉索引在常數時間（O(1)）內找到對應元素（隨機存取）。

　　如果不是相似的事物，如果不放在一起，我們還有方法能好好整理它們嗎？可以，用鍵（Key）值（Value）架構即可。我們先定好一個雜湊（Hashing）函數，讓要管理的事物都依循此函數的判斷放到對應區塊中。這樣就能在常數時間（O(1)）內找到鍵所對應的值。

　　以下為LeetCode中，與陣列（Array）和雜湊（Hashing）有關的題目與解答摘要。題目只會更多，但解題核心往往不變，祝大家都只練少量題目就在競試中有良好表現😊。

💡

有時反向遍歷陣列，做法會簡單很多
程式碼要一開始就簡潔很難，寫完再整理比較容易
善用陣列索引的有序性，有時會比雜湊表還好用

😎1. Two Sum

Description

　　給予一個長度為n的整數陣列nums和一個整數target，陣列中必然僅存一對數字，相加為target。請回傳以此兩數索引值（indices）為值的陣列。

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

Solutions

❌Approach #1 暴力法（Brute Force）

　　若毫無頭緒，那就先用暴力解試試。在嵌狀迴圈（Nested Loop）的運作下，時間複雜度會是O(n²)，明顯會有更好解法。

Approach #2 Two-pass 雜湊表

　　我們可以：

先遍歷一次陣列，用雜湊表hashmap記錄每個元素（值當key，索引值當value）
第二次遍歷時，若target-nums[i]已在hashmap內，且其值（陣列索引值）與當前元素不同，代表即為所求。

　　這樣的時間與空間複雜度皆為O(n)。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            hashmap[nums[i]] = i
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap and hashmap[complement] != i:
                return [i, hashmap[complement]]

⭐Approach #3 One-pass 雜湊表

　　上述為Two-Pass Algorithm，即便時間複雜度已經夠好，但能否遍歷一遍（One-Pass）就完成呢？題目告知僅會有一對數字會是答案，那反過來想，若用雜湊表紀錄的值是所求配對的另個數字（target-v），我們就能在首次遍歷中直接找到答案。這樣的時間與空間複雜度皆為O(n)。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}  # val -> index

        for i, v in enumerate(nums):
            diff = target - v
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[v] = i

😎27. Remove Element

Description

　　給予一個整數陣列nums和一個整數val，請原地移除nums中的val。陣列中的元素順序可以變動，請回傳陣列中與val相異的元素數量。

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Solutions

⭐Approach 1: Two Pointers

　　我們使用雙指標來處理問題：

用右指標j持續遍歷nums：
- 沒遇val時，i和j同步前進，並讓nums[i] = nums[j]
- 遇val時，i會停在原處，等待下次nums[j] != val時，讓val被後面非val值替換掉
陣列遍歷完時，左指標i的位置即為所求

　　這樣的時間複雜度為O(n)，空間複雜度為O(1)。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0 
        for j in range(len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
        return i

😎28. Find the Index of the First Occurrence in a String

Description

　　給予兩字串needle和haystack，請回傳前者在後者中出現的首個位置索引，若非為後者一部分則回傳-1。

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

Solutions

　　此題有其他解法能達到更好的時間複雜度，但因難度為Easy而先不進階討論。

Approach #1: Sliding Window

　　我們可以直觀地比較字串，遇到符合狀況時回傳索引。

　　這樣的時間複雜度為O(N*M)，空間複雜度為O(1)。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(needle)
        # 以needle長度為單位，從haystack的首字元開始比較
        for start in range(len(haystack) - n + 1):
            for i in range(n):
                if needle[i] != haystack[start + i]:
                    break
                # 符合長度達needle長度，已找到
                if i == n - 1:
                    return start

        return -1

😐36. Valid Sudoku

Description

　　判斷一個9x9的方陣是否能成為數獨板（Sudoku）。數獨板的每條列（row）和每條行（column ）都不能包含重複數字（1–9），每個3x3的子區塊也不能包含。

Solutions

⭐Approach #1 使用雜湊表

　　一個板子能否成為數獨板，其每行、列、小區塊不得有重複數字。因此我們：

用兩層迴圈去檢查所有元素
用三個雜湊表cols、rows，和squares來幫助判斷當前遍歷到的元素是否合法

　　這樣的時間和空間複雜度皆為O(81)（也就是O(n²)）。

from collections import defaultdict


class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = defaultdict(set)
        rows = defaultdict(set)
        squares = defaultdict(set)  # key = (r /3, c /3)

        for i in range(len(board)):
            for j in range(len(board[i])):
                char = board[i][j]
                if char == ".":
                    continue
                else:
                    if char in cols[j] or \
                            char in rows[i] or \
                            char in squares[(i // 3, j // 3)]:
                        return False
                    else:
                        rows[i].add(char)
                        cols[j].add(char)
                        squares[(i // 3, j // 3)].add(char)
        return True

😐49. Group Anagrams

Description

　　給予一個字串陣列strs，將其中互為anagram的分組，順序不限。

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Input: strs = [""]
Output: [[""]]

Solutions

Approach #1 Categorize by Sorted String

　　我們可以：

準備好回傳雜湊表ans
排序每個字串，以排序完樣貌作為ans的鍵（分類依據）
鍵同者歸到同一群

　　這樣的時間複雜度為O(N*KlogK)，空間複雜度為O(NK)，N為字串數量，K為字串們中最長字串長。也許會有更好的解法。

class Solution(object):
    def groupAnagrams(self, strs):
        ans = collections.defaultdict(list)
        for s in strs:
            ans[tuple(sorted(s))].append(s)
        return ans.values()

⭐Approach #2 Categorize by Count

　　題目告知字串內容皆為小寫英文字母，所以我們可用一個大小為26的陣列，以英文字母在ASCII編碼的相對位置決定其在陣列的位置（像是ord(c) - ord("a")）來記錄次數。

建立一個雜湊表ans
遍歷字串們
- 各給予一個陣列count記錄串內出現的字元次數
- 將count轉為獨特物件（tuple()），作為分類依據
回傳各鍵值（ans.values()）

　　這樣的總時間與空間複雜度皆為O(NK)，N為字串數量，K為最長字串長。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord("a")] += 1
            ans[tuple(count)].append(s)
        return ans.values()

😎58. Length of Last Word

Description

　　給予一個字串s，其內容由字母和空白字元組成，請回傳字串中末個字詞長。

Example 1:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Example 2:

Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.

Example 3:

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

Solutions

⭐Approach #1: One-loop Iteration

　　我們可以反向遍歷字串，並在碰到字母時時開始判斷此字詞長。

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        res = 0
        touched = False
        for i in range(len(s) - 1, -1, -1):
            if s[i] == " ":
                if touched:
                    return res
            else:
                touched = True
                res += 1
        return res

😐75. Sort Colors

Description

　　給予一個陣列nums，其中元素可能有0、1、2，代表紅白藍。請將它們依一組組排序後回傳。

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Solutions

⭐Approach #1: One Pass

　　排序陣列的有效做法需要O(NlogN)，而當陣列元素組成有重複且種類少（像是此題的三種），我們就可應用荷蘭國旗問題（Dutch National Flag problem），讓時間複雜度降為O(N)：

使用三個指標low、mid和high，在遍歷陣列時調整元素位置
在mid尚未越過high時，若nums[mid]：
- 為最小元素：與nums[low]互換，並讓low往前，完成low位置的排序
- 為最大元素：與nums[high]互換，並讓high往內，完成high位置的排序
- 為中間元素：單純讓mid往前
迴圈結束時，元素位置即為所求

　　這樣的時間複雜度為O(n)，空間複雜度為O(1)。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        # mid is an index of element under consideration
        low = mid = 0
        high = len(nums) - 1

        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 2:
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1
            else:
                mid += 1

😎118. Pascal’s Triangle

Description

　　給予一整數numRows，請回傳帕斯卡三角形（Pascal’s triangle）前numRows列的數值。

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Solutions

⭐Approach #1: Dynamic Programming

　　我們可以直觀地用過往結果，算出每列數值。

　　這樣的時間複雜度為O(numRows²)，空間複雜度為O(1)。

from typing import List


class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = [[1]]
        if numRows == 1:
            return res
        res.append([1, 1])
        if numRows == 2:
            return res
        for i in range(2, numRows):
            tmp = [1]
            j = 0
            k = 1
            prev = res[-1]
            while k < i:
                tmp.append(prev[j] + prev[k])
                j += 1
                k += 1
            tmp.append(1)
            res.append(tmp)
        return res

😐122. Best Time to Buy and Sell Stock II

Description

　　給予一個整數陣列prices，記錄一支股票在第i天的價格。每天我們都能決定要買或賣股票，即便當天同時買進與賣出也可以。請回傳你能得到的最大利潤。

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Solutions

⭐Approach #1: Simple One Pass

　　因為沒有買賣成本，我們可以採用貪婪演算法的精神：只要一有獲利就賣出。

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        l = 0
        for r in range(1, len(prices)):
            profit = prices[r] - prices[l]
            if profit > 0:
                res += profit
            l += 1
        return res

😐128. Longest Consecutive Sequence

Description

　　給予一個未排序的整數陣列nums，找出元素們可構成的最長連續序列之長。我們得在時間複雜度O(n)內完成。

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Solutions

❌Approach #1 暴力解

　　我們先從暴力解開始：

嘗試把每個元素當成開頭，設為current_num
持續把current_num + 1，看nums中是否有對應值

　　這樣的時間複雜度為O(n³)（持續current_num + 1後就再檢查一次）。

class Solution:
    def longestConsecutive(self, nums):
        longest_streak = 0
        for num in nums:
            current_num = num
            current_streak = 1
            while current_num + 1 in nums:
                current_num += 1
                current_streak += 1

            longest_streak = max(longest_streak, current_streak)

        return longest_streak

❌Approach #2 先排序

　　我們也可以：

排序陣列
遍歷陣列，確認鄰近元素是否連續

　　這樣的時間複雜度是O(nlogn)，仍不符題目限制的O(n)。

class Solution:
    def longestConsecutive(self, nums):
        if not nums:
            return 0

        nums.sort()

        longest_streak = 1
        current_streak = 1

        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                if nums[i] == nums[i - 1] + 1:
                    current_streak += 1
                else:
                    longest_streak = max(longest_streak, current_streak)
                    current_streak = 1

        return max(longest_streak, current_streak)

⭐Approach #3 用個雜湊表再加點巧思

　　前面的暴力法有兩處能優化：

用一個雜湊集合numSet紀錄出現過的元素，讓查詢耗時降至O(1)
選n做開頭前，先確認n-1是否存在（有就代表有更好的當頭），進而省下後續嘗試

　　這樣的時間與空間複雜度皆為O(n)。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)
        longest = 0

        for n in nums:
            # check if its the start of a sequence
            if (n - 1) not in numSet:
                length = 1
                while (n + length) in numSet:
                    length += 1
                longest = max(length, longest)
        return longest

😎169. Majority Element

Description

　　給予一個大小為n的整數陣列nums，請回傳主要元素（majority element）。所謂的主要元素，是其數量超過整體的1/2，我們可以假設其必然存在。

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Solutions

⭐Approach #1: HashMap

　　我們可用雜湊表紀錄出現過的數字，當某數出現次數超過總數一半時，即為所求。

　　這樣的時間與空間複雜度皆為O(N)。

from collections import defaultdict
from typing import List


class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        mp = defaultdict(int)

        for n in nums:
            mp[n] += 1
            if mp[n] > len(nums) // 2:
                return n

⭐Approach #2: Boyer-Moore Voting Algorithm

　　我們可以不用額外空間就來處理。因多數元素量該超過整體一半，我們可將非它元素當作同個陣營，一起比較數量：

用count記錄出現次數，candidate記錄當前統計元素
遍歷陣列：
- 若count為0，將當前元素設為candidate
- 若遍歷到的元素為candidate，將count+1
- 否則，count-1
遍歷完後，candidate即為所求

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

from typing import List


class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None
        for num in nums:
            if count == 0:
                candidate = num
            if num == candidate:
                count += 1
            else:
                count -= 1

        return candidate

😐179. Largest Number

Description

　　給予一個非負整數陣列nums，請用元素組合成一個最大數字並以字串形式回傳。

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]
Output: "9534330"

Solutions

　　要將數字湊成最大整數，必然得將數字越大者放越高位。考慮到每個數的位數不同，我們得比大小，因而選用python的字串比較來滿足所求。

　　這樣的時間複雜度為O(NlogN)，空間複雜度為O(N)。

from functools import cmp_to_key
from typing import List


class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # 使用字串比大小的特性來滿足條件所需
        # 例如: 89 > 9, 989 > 98
        for i, n in enumerate(nums):
            nums[i] = str(n)

        def compare(n1, n2):
            # -1 代表 n1 < n2，應放在 n2 前面
            if n1 + n2 > n2 + n1:
                return -1
            else:
                return 1

        nums = sorted(nums, key=cmp_to_key(compare))

        return str(int("".join(nums)))

😎205. Isomorphic Strings

Description

　　給予兩個字串s和t，判斷它們是否同構（Isomorphic）。也就是各位置字母可以不同，但順序和映射關係得相同。

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Solutions

⭐Approach #1: Character Mapping with Dictionary

　　我們可用雜湊表記錄映射關係，因題目的要求為一對一映射，故我們用兩個雜湊表互相對照。

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        mp1 = {}
        mp2 = {}
        for i in range(len(s)):
            if s[i] not in mp1 and t[i] not in mp2:
                mp1[s[i]] = t[i]
                mp2[t[i]] = s[i]

            # 用get連帶判斷映射關係是否存在
            elif mp1.get(s[i]) != t[i] or mp2.get(t[i]) != s[i]:
                return False

        return True

😎217. Contains Duplicate

Description

　　給予一個長度為n的整數陣列。若其中有重複元素則回傳True，否則回傳False。

Input: nums = [1,2,3,1]
Output: true

Input: nums = [1,2,3,4]
Output: false

Solutions

❌Approach #1 線性搜尋（Linear Search）

　　一開始若毫無頭緒，我們可先用一個嵌狀迴圈（Nested Loop），兩兩比對元素來處理。若發現有元素相同則回傳True，跑完迴圈後都沒發現則回傳False。但這樣的時間複雜度過高（O(n²)），也許會有更好的解法。

def containsDuplicate(nums):
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] == nums[i]:
                return True
        return False

Approach #2 先排序（Sort）

　　因為題目沒有禁止去改原有陣列，所以我們可以：

排序
檢查相鄰元素是否相同
- 有的話就回傳True
- 遍歷完則回傳False

　　這樣的時間複雜度是O(nlogn)（O(nlogn) + O(n)），也許還有更好的解法。

def containsDuplicate(nums):
    nums.sort()
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1]:
            return True
    return False

⭐Approach #3 雜湊表（Hash Table）

　　要檢查陣列中有沒有重複元素，最糟情況下我們仍得遍歷整個陣列，所以目標的時間複雜度會是O(n)。我們可以：

用一個雜湊表hashset記錄出現過的元素
在遍歷過程中檢查此元素是否存在hashset內
- 存在的話回傳True
- 遍歷完後回傳False

　　這樣的時間複雜度為O(n)（在雜湊表新增和查詢元素皆僅需O(1)），空間複雜度則因使用雜湊表而為O(n)。

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hashset = set()

        for n in nums:
            if n in hashset:
                return True
            hashset.add(n)
        return False

😐238. Product of Array Except Self

Description

　　給予一個整數陣列nums，請回傳一個陣列answer，其中各值皆為原陣列nums中同索引值以外的眾值乘積（product）。乘積結果不用擔心會超過32-bit整數的限制，我們不能在過程使用除法，並且得在O(n)內完成。

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Solutions

❌Approach #0 Brute Force

　　因為時間複雜度被要求在O(n)內，故暴力解O(n²)（一一乘積）不適合。

Approach #1 使用前綴與後綴表（Left and Right product lists）

　　用幾個例子來幫助理解後，我們發現每個位置的乘積結果，可拆成左與右乘積，且可用前次的結果來避免重複運算。因此我們：

由左至右遍歷陣列，用一個陣列L儲存左乘積（prefix as left product）
由右至左遍歷陣列，用另個陣列R儲存右乘積（postfix as right product）
藉由索引合併兩個乘積，結果即為所求
附註：首元素的左乘積和末元素的右乘積都設為1

　　這樣的時間複雜度為O(n)（O(3n)），空間複雜度也為O(n)，有機會降低空間複雜度嗎？

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)

        L, R, answer = [0] * length, [0] * length, [0] * length

        L[0] = 1
        for i in range(1, length):
            L[i] = nums[i - 1] * L[i - 1]

        R[length - 1] = 1
        for i in reversed(range(length - 1)):
            R[i] = nums[i + 1] * R[i + 1]

        for i in range(length):
            answer[i] = L[i] * R[i]

        return answer

⭐Approach #2 優化空間複雜度

　　回顧前面的解法，我們發現可以：

先把左乘積結果放到回傳陣列res中
由右往左遍歷陣列時：
- 用變數postfix儲存累計的右乘積
- 將結果依序乘回res中

　　這樣的時間複雜度為O(n)，空間複雜度則降為O(1)。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * (len(nums))

        prefix = 1
        for i in range(len(nums)):
            res[i] = prefix
            prefix *= nums[i]
        postfix = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] *= postfix
            postfix *= nums[i]
        return res

😎242. Valid Anagram

Description

　　給予兩字串（t, s，長度為n），判斷t是否為s的一種anagram。所謂的anagram，是指兩個字串所用的元素種類和數量皆為一致，只是順序不同。

Input: s = "anagram", t = "nagaram"
Output: true

Input: s = "rat", t = "car"
Output: false

Solutions

Approach #1 先排序（Sort）

　　因為題目沒有禁止我們更改原有字串，所以我們：

先排序（sort）兩字串
比較它們是否相同

　　這樣的時間複雜度為O(nlogn)，也許還有更好的解法。

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    str1 = sorted(s)
    str2 = sorted(t)
    return str1 == str2

⭐Approach #2 用雜湊表統計出現頻率（Frequency Counter）

　　判斷anagram時必然得遍歷整個字串，所以時間複雜度不會小於O(n)。我們可以：

用兩個雜湊表countS和countT記錄這兩字串字詞的出現次數
若兩表皆同，代表t為s的anagram

　　這樣的時間複雜度為O(n)，空間複雜度為O(1)（因字詞種類有限）。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        countS, countT = {}, {}

        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)
        return countS == countT

😐271. Encode and Decode Strings

Description

　　設計一個演算法，能將一組字串陣列編碼（Encode ）成一個字串，得以經由網路傳送至其他環境，並在解碼（Decode ）後得到原本的字串陣列。

// Machine 1 (sender) has the function:
string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

// Machine 2 (receiver) has the function:
vector<string> decode(string s) {
  //... your code
  return strs;
}

// Machine 1 does
string encoded_string = encode(strs);

// Machine 2 does
vector<string> strs2 = decode(encoded_string);

===============================================
Input: dummy_input = ["Hello","World"]
Output: ["Hello","World"]
Explanation:
Machine 1:
Codec encoder = new Codec();
String msg = encoder.encode(strs);
Machine 1 ---msg---> Machine 2

Machine 2:
Codec decoder = new Codec();
String[] strs = decoder.decode(msg);

Solutions

⭐Approach #1 使用特殊符號來分隔

　　要編碼一組字串完後，從A送到B再解碼來讀取，我們可以用特殊符號來分隔。

　　官方是用非美標準資訊交換碼（Non-ASCII）來分隔，但面試時不一定能正確回想。

class Codec:
    def encode(self, strs):
        if len(strs) == 0:
            return chr(258)

        return chr(257).join(x for x in strs)

    def decode(self, s):
        if s == chr(258):
            return []
        return s.split(chr(257))

　　我們可以改成：

用一個符號（此處用#）當作間隔記號
附上字串長度處理原字串包含#的情況
即便原字串包含了數字+#，也不會影響編碼再解碼的結果

　　這樣總時間複雜度為O(n)，空間複雜度為O(1)。

class Solution:
    def encode(self, strs):
        res = ""
        for s in strs:
            res += str(len(s)) + "#" + s
        return res

    def decode(self, s):
        res, i = [], 0

        while i < len(s):
            j = i
            while s[j] != "#":
                j += 1
            length = int(s[i:j])
            res.append(s[j + 1: j + 1 + length])
            i = j + 1 + length
        return res

😐280. Wiggle Sort

Description

　　給予一個整數陣列nums，請排序後回傳它。順序規則像是nums[0] <= nums[1] >= nums[2] <= nums[3]，讓基數位置的元素大於或等於兩旁的偶數元素。

Solutions

Approach #1: Sorting

　　我們可以先排序，再交換當中元素順序為題目所求。

　　這樣的時間複雜度為O(NlogN)，空間複雜度為O(1)。

class Solution:
    def swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]

    def wiggleSort(self, nums):
        nums.sort()
        for i in range(1, len(nums) - 1, 2):
            nums[i], nums[i + 1] = nums[i + 1], nums[i]

⭐Approach #2: Greedy

　　題目的有序，是要每個基數位置的元素≥下個元素；偶數位置的元素≤下個元素。我們舉幾個例子後發現這其實可以應用貪婪精神，每次比較當前元素與下個元素，並且不用擔心互換位置後影響前個條件的成。

　　這樣的時間複雜度為O(N)，空間複雜度為O(1)。

class Solution:
    def wiggleSort(self, nums):
        for i in range(len(nums) - 1):
            if (
                    (i % 2 == 0 and nums[i] > nums[i + 1]) or
                    (i % 2 == 1 and nums[i] < nums[i + 1])
            ):
                nums[i], nums[i + 1] = nums[i + 1], nums[i]

😎290. Word Pattern

Description

　　給予字串pattern和s，請判斷s是否依循pattern關係呈現。

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

Solutions

⭐Approach #1: Two Hash Maps

　　我們先將s轉為陣列words，並用兩個雜湊表紀錄一對一的映射關係。

　　這樣的時間複雜度為O(N+M)，空間複雜度為O(1)。

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split(" ")
        if len(pattern) != len(words):
            return False
        cToW = {}
        wToC = {}

        for c, w in zip(pattern, words):
            if c in cToW and cToW[c] != w:
                return False
            if w in wToC and wToC[w] != c:
                return False
            cToW[c] = w
            wToC[w] = c
        return True

🧰: LeetCode: Array & Hashing (1/3)

🤔

💡

😎1. Two Sum

Description

Solutions

❌Approach #1 暴力法（Brute Force）

Approach #2 Two-pass 雜湊表

⭐Approach #3 One-pass 雜湊表

😎27. Remove Element

Description

Example 1:

Example 2:

Solutions

⭐Approach 1: Two Pointers

😎28. Find the Index of the First Occurrence in a String

Description

Example 1:

Example 2:

Solutions

Approach #1: Sliding Window

😐36. Valid Sudoku

Description

Solutions

⭐Approach #1 使用雜湊表

😐49. Group Anagrams

Description

Solutions

Approach #1 Categorize by Sorted String

⭐Approach #2 Categorize by Count

😎58. Length of Last Word

Description

Example 1:

Example 2:

Example 3:

Solutions

⭐Approach #1: One-loop Iteration

😐75. Sort Colors

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: One Pass

😎118. Pascal’s Triangle

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: Dynamic Programming

😐122. Best Time to Buy and Sell Stock II

Description

Example 1:

Example 2:

Example 3:

Solutions

⭐Approach #1: Simple One Pass

😐128. Longest Consecutive Sequence

Description

Solutions

❌Approach #1 暴力解

❌Approach #2 先排序

⭐Approach #3 用個雜湊表再加點巧思

😎169. Majority Element

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: HashMap

⭐Approach #2: Boyer-Moore Voting Algorithm

😐179. Largest Number

Description

Example 1:

Example 2:

Solutions

😎205. Isomorphic Strings

Description

Example 1:

Example 2:

Example 3:

Solutions

　　官方是用非美標準資訊交換碼（Non-ASCII）來分隔，但面試時不一定能正確回想。