最後更新日期: 02/06/2024

Table of Contents:

🤔Why It Matters

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

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

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

💡Learned

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

😎1. Two Sum

Illustration

　　給予一個長度為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

Illustration

　　給予一個整數陣列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

Illustration

　　給予兩字串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

Illustration

　　判斷一個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

Illustration

　　給予一個字串陣列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

Illustration

　　給予一個字串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

Illustration

　　給予一個陣列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

Illustration

　　給予一整數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

Illustration

　　給予一個整數陣列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

Illustration

　　給予一個未排序的整數陣列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

Illustration

　　給予一個大小為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

Illustration

　　給予一個非負整數陣列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

Illustration

　　給予兩個字串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

Illustration

　　給予一個長度為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

Illustration

　　給予一個整數陣列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

Illustration

　　給予兩字串（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

Illustration

　　設計一個演算法，能將一組字串陣列編碼（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

Illustration

　　給予一個整數陣列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

Illustration

　　給予字串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

😎303. Range Sum Query – Immutable

Illustration

　　給予一個整數陣列nums，請將其化為一種資料結構，能夠應對sumRange(left, right)的要求（對於left ≤ right，回傳此區間內的元素和）。

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]
Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Solutions

Approach #1: Brute Force

　　我們可以直接遍歷區段內的元素並加總。

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

class NumArray:

    def __init__(self, nums: List[int]):
        self.arr = nums

    def sumRange(self, left: int, right: int) -> int:
        res = 0
        for i in range(left, right + 1):
            res += self.arr[i]

        return res

⭐Approach #2: Caching

　　若過程運算多次，紀錄先前算過的成果就能加快效能。但若儲存每個可能區間，空間複雜度會高達O(N²)。我們可藉sumRange[i, j] = sumRange[0, j] - sumRange[0, i]這概念，降低空間複雜度至O(N)，

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

class NumArray:
    def __init__(self, nums):
        self.sum = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.sum[i + 1] = self.sum[i] + nums[i]

    def sumRange(self, i, j):
        return self.sum[j + 1] - self.sum[i]

😐304. Range Sum Query 2D -Immutable

Illustration

　　給予一個二維陣列matrix，請建構一個資料結構NumMatrix，它的方法sumRegion能求出範圍內的數總和。

Example 1:

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]
Explanation
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

Solutions

❌Approach #1: Brute Force

　　我們可以直接計算，但在一些測試案例中會運算超時。

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

class NumMatrix:
    def __init__(self, matrix):
        self.data = matrix

    def sumRegion(self, row1, col1, row2, col2):
        total = 0
        for r in range(row1, row2 + 1):
            for c in range(col1, col2 + 1):
                total += self.data[r][c]
        return total

⭐Approach #2: Caching Smarter

　　如同前題（No. 303），我們可在初始化時先儲存計算成果，減少日後運算。如何有效地儲存成果，我們以下圖的原點O（[0, 0]）、A（[row1, col1]）、B（[row1, col2]）、C（[row2, col1]）、D（[row2, col2]）點來說明：

算出整體面積Sum(OD)
將整體面積減去Sum(OB)、Sum(OC)，再加上Sum(OA)，即為所求Sum(AD)
注意，記憶陣列dp的長寬各為原本大小再+1，代表的是端點座標

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

class NumMatrix:
    def __init__(self, matrix):
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return
        self.dp = [[0] * (len(matrix[0]) + 1) for _ in range(len(matrix) + 1)]
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                self.dp[r + 1][c + 1] = (self.dp[r + 1][c]
                                         + self.dp[r][c + 1]
                                         + matrix[r][c]
                                         - self.dp[r][c]
                                         )

    def sumRegion(self, row1, col1, row2, col2):
        return (
                self.dp[row2 + 1][col2 + 1]
                - self.dp[row1][col2 + 1]
                - self.dp[row2 + 1][col1]
                + self.dp[row1][col1]
        )

😐307. Range Sum Query – Mutable

Illustration

　　給予一個整數陣列nums，請建構一個資料結構NumArray，其方法：

update(index, val)：將索引index處的值更新為val
sumRange(left, right)：回傳包含左右兩點的數和

Example 1:

Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]
Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

Solutions

❌Approach #1: Naive

　　我們可以先直觀地處理，但這樣的解法在一些測試案例中會超時。

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

class NumArray:
    def __init__(self, nums):
        self.nums = nums

    def sumRange(self, i, j):
        total = 0
        for l in range(i, j + 1):
            total += self.nums[l]
        return total

    def update(self, i, val):
        self.nums[i] = val

⭐Approach #2: Segment Tree

　　此題適合使用線段樹（Segment Tree），它會把每個數做為一棵二元樹的葉子節點，依循其架構就能在O(logN)內找到元素和或是修改資料。

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

class NumArray:
    # space: O(n)
    def __init__(self, nums: List[int]):
        if len(nums) > 0:
            self.n = len(nums)
            self.tree = [0] * (self.n * 2)
            self.buildTree(nums)

    # time: O(n)
    def buildTree(self, nums):
        for i in range(self.n, self.n * 2):
            self.tree[i] = nums[i - self.n]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]

    def update(self, pos: int, val: int) -> None:
        pos += self.n
        self.tree[pos] = val
        while pos > 0:
            left = pos
            right = pos
            if pos % 2 == 0:
                right = pos + 1
            else:
                left = pos - 1
            # parent is updated after child is updated
            self.tree[pos // 2] = self.tree[left] + self.tree[right]
            pos //= 2

    def sumRange(self, l: int, r: int) -> int:
        # get leaf with index 'l' and 'r'
        l += self.n
        r += self.n
        sum = 0
        while l <= r:
            # if l is right child of its parent
            if l % 2 == 1:
                sum += self.tree[l]
                l += 1
            # if r is left child of its parent
            if r % 2 == 0:
                sum += self.tree[r]
                r -= 1
            l //= 2
            r //= 2
        return sum

😐347. Top K Frequent Elements

Illustration

　　給予一個整數陣列nums和一個整數k，請回傳陣列中出現頻率≥k的元素。

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

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

Solutions

Approach #1 使用堆積（Heap）

　　要求前K項元素，我們通常會想到優先佇列（Prioirty Queue），也就是堆積（Heap）。我們：

將元素與出現次數建為一個雜湊表（count）
用內建函式heapq.nlargest()，建立一個前K大的陣列
回傳它即

　　這樣的時間複雜度為O(NlogK)（僅排序前K個），空間複雜度則為O(N+K)（雜湊表O(N)，堆積O(K)）。

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # O(1) time 
        if k == len(nums):
            return nums

        # 1. build hash map : character and how often it appears
        # O(N) time
        count = Counter(nums)
        # 2-3. build heap of top k frequent elements and
        # convert it into an output array
        # O(N log k) time
        return heapq.nlargest(k, count.keys(), key=count.get)

⭐Approach #2 用陣列索引值分類出現次數不同的元素

　　我們可將陣列索引值當成歸類的鍵。我們：

用一個雜湊表count統計元素與其出現次數
創造一個列數n+1的二維陣列，將count值依鍵放入索引值相同的陣列中
從尾端遍歷此陣列，將索引值≥k者納入res

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

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        freq = [[] for i in range(len(nums) + 1)]

        for n in nums:
            count[n] = 1 + count.get(n, 0)
        for n, c in count.items():
            freq[c].append(n)

        res = []
        for i in range(len(freq) - 1, 0, -1):
            for n in freq[i]:
                res.append(n)
                if len(res) == k:
                    return res

😎392. Is Subsequence

Illustration

　　給予兩個字串s和t，如果s是t的子序列（subsequence ）則回傳True，否則回傳False。

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

Solutions

⭐Approach #1: Two-Pointers

　　我們可以用Two-Pointers來解題：

用l和r兩指標遍歷字串s和t
- 若s[l] == t[r]，代表t當下字元已符合，可讓r往前，
- 持續讓r往前，用下個字元判斷是否符合
遍歷完s或t時，判斷l==len(s)是否為真，看s是否已比對完成

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

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        l = 0
        r = 0
        while l < len(s) and r < len(t):
            if s[l] == t[r]:
                l += 1
            r += 1

        return l == len(s)

😐438. Find All Anagrams in a String

Illustration

　　給予兩字串s和p，請回傳在s中所有能成為p的異位構詞（anagram）之字串起始點索引為一陣列。

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Solutions

⭐Approach #1: Sliding Window

　　我們可先統計p內的字元出現頻率，再用移動視窗判斷所夾擊的s子字串，其字元出現頻率也相同。

　　這樣的時間複雜度為O(N_S)，空間複雜度為O(K)。N_S為s的長度，K為出現過的元素數量。

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        l = 0
        counterP = Counter(p)
        counterS = Counter(s[0:len(p) - 1])
        res = []

        for r in range(len(p) - 1, len(s)):
            counterS[s[r]] = counterS.get(s[r], 0) + 1
            if counterP == counterS:
                res.append(l)
            l += 1
        return res

😎485. Max Consecutive Ones

Illustration

　　給予一個二元陣列nums，請回傳其中元素1最大連續長。

Example 1:

Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

Example 2:

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

Solutions

⭐Approach #1: One pass

　　我們可以遍歷一次陣列，統計連續出現的最大長度。

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

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        count = max_count = 0
        for num in nums:
            if num == 1:
                count += 1
            else:
                max_count = max(max_count, count)
                count = 0
        return max(max_count, count)

😎448. Find All Numbers Disappeared in an Array

Illustration

　　給予一個具備n個整數的陣列nums，其數值界在[1, n]內，請以一個陣列形式，回傳沒出現在此範圍內的數字。

Example 1:

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

Example 2:

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

Solutions

Approach #1: Using Hash Map

　　如果使用雜湊表，此題可以輕易地處理。

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

class Solution(object):
    def findDisappearedNumbers(self, nums):
        hash_table = {}
        for num in nums:
            hash_table[num] = 1

        result = []

        for num in range(1, len(nums) + 1):
            if num not in hash_table:
                result.append(num)

        return result

⭐Approach #2: O(1) Space InPlace Modification Solution

　　若要讓空間複雜度降為O(1)，我們得善用所給陣列，方法為：

以索引值作為數值範圍，但得注意索引值從0開始
遍歷陣列，將索引值對應數值變為負
再次遍歷陣列，若值>0代表沒出現過，加到陣列res中
回傳res

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

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            new_index = abs(nums[i]) - 1
            if nums[new_index] > 0:
                # 代表出現過一次
                nums[new_index] *= -1

        result = []

        for i in range(1, len(nums) + 1):
            # 代表沒出現過
            if nums[i - 1] > 0:
                result.append(i)

        return result

😐487. Max Consecutive Ones II

Illustration

　　給予一個二元陣列nums，若能反轉一次0為1，請回傳1所能連續的最大長度。

Example 1:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

Example 2:

Input: nums = [1,0,1,1,0,1]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones.
The max number of consecutive ones is 4.

Solutions

⭐Approach #1: Sliding Window

　　我們可以用移動視窗來解題：

用指標l和r當作窗口邊界，zeroCount記錄窗口內的0數量，res記錄最大長度
用r遍歷陣列：
- 若遇到0，將zeroCount+1
- 若zeroCount>1，就持續移動l，直到zeroCount<2
- 更新res
遍歷完後，res即為所求

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

from typing import List


class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        res = 0
        l, r = 0, 0
        zeroCount = 0

        while r < len(nums):
            if nums[r] == 0:
                zeroCount += 1

            while zeroCount > 1:
                if nums[l] == 0:
                    zeroCount -= 1
                l += 1

            res = max(res, r - l + 1)
            r += 1

        return res

😎496. Next Greater Element I

Illustration

　　陣列某元素x的下個更大元素（next greater element），是指其右邊比它更大的首個元素。現在給予兩個0-indexed的整數陣列nums1和nums2，前者為後者的子集合（subset）。

　　現在遍歷nums1，找出兩陣列同值時（兩陣列內的值皆相異）的nums2索引和其下個更大元素，沒有則回傳-1。請回傳等同nums1長度的答案陣列。

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

Solutions

　　以下所用符號，m為nums1的元素量，n為nums2的元素量，n > m。

Approach #1: Brute Force

　　我們可以先直觀地處理。

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

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = []
        for n in nums1:
            j = 0
            while nums2[j] != n:
                j += 1
            while j < len(nums2) and nums2[j] <= n:
                j += 1
            if j == len(nums2):
                res.append(-1)
            else:
                res.append(nums2[j])
        return res

⭐Approach #2: Using Stack

　　若先算出nums2各元素的下個更大元素，我們就能將時間複雜度降至O(n)：

用堆疊stack輔助找出nums2各元素的下個更大元素，雜湊表mp儲存
遍歷nums2
- 將元素存入stack
- 若當前元素>先前元素，則為先前元素的下個更大元素，將關係記錄到mp中
遍歷nums1，用陣列res儲存各元素的下個更大元素
回傳res，即為所求

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

from typing import List


class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 輔助找出nums2中各元素的下個更大元素
        stack = []
        # 儲存每個元素的下個更大元素
        mp = {}

        for num in nums2:
            # 找到之前所存元素的下個更大元素
            while stack and num > stack[-1]:
                # 記錄元素的下個更大元素，並將其從堆疊中移除
                mp[stack.pop()] = num
            stack.append(num)

        # 此時堆疊內的元素皆沒有下個更大元素
        while stack:
            mp[stack.pop()] = -1

        # 使用nums1的元素順序，放入對應答案
        res = []
        for num in nums1:
            res.append(mp[num])

        return res

😐523. Continuous Subarray Sum

Illustration

　　給予一整數陣列nums和整數k，請判斷nums是否有好（good）的子陣列。好的特徵是：

長度≥2
子陣列的元素和是k的倍數（0也算）

Example 1:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

Input: nums = [23,2,6,4,7], k = 13
Output: false

Solutions

⭐Approach #1: HashMap

　　此題需要的主要觀念是對餘數的了解：

使用雜湊表mp，記錄在索引元素當下總和（total）的餘數
遍歷陣列nums，若餘數值再次出現，代表這中間有子陣列的元素和可被k整除

　　這樣的時間複雜度為O(N)，空間複雜度為O(min(N, k))，N為元素數量。

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # 如果0再次出現，那可確保即便是前兩個元素也滿足後面的判斷式
        mp = {0: -1}
        total = 0
        for i, j in enumerate(nums):
            total += j
            remainder = total % k
            # 若再度出現相同餘數，代表中間有個子陣列的和為k的倍數
            if remainder in mp:
                # 確認此子陣列相隔超過2
                if i - mp[remainder] >= 2:
                    return True
                else:
                    continue
            mp[remainder] = i
        return False

😐535. Encode and Decode TinyURL

Illustration

　　短網址服務（TinyURL）能將一個長網址（e.g. https://leetcode.com/problems/design-tinyurl）轉換成短網址（e.g.　http://tinyurl.com/4e9iAk），請設計一個類別來完成此功能。

Example 1:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

Solutions

⭐Approach #1 Using Simple Counter

　　轉換長網址為短網址的關鍵在於一對一映射，我們使用遞增數字來完成。

class Codec:
    def __init__(self):
        self.encodeMap = {}
        self.decodeMap = {}
        self.base = "http://tinyurl.com/"

    def encode(self, longUrl: str) -> str:
        if longUrl not in self.encodeMap:
            # 用遞增數字為編號
            shortUrl = self.base + str(len(self.encodeMap) + 1)
            self.encodeMap[longUrl] = shortUrl
            self.decodeMap[shortUrl] = longUrl
        return self.encodeMap[longUrl]

    def decode(self, shortUrl: str) -> str:
        return self.decodeMap[shortUrl]

😐554. Brick Wall

Illustration

　　在你面前有面n列矩形牆，我們以二維陣列wall表達裡面磚頭的寬度（高度皆相同），每列總寬度皆同。

　　請從頂到尾劃一條垂直線，請回傳可以劃過最少塊的磚頭數量（擦邊狀態不需計算）。

Example 1:

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2

Example 2:

Input: wall = [[1],[1],[1]]
Output: 3

Solutions

Approach #1 HashMap

　　我們可用個雜湊表，記錄每個x座標所沒切到的磚頭數。遍歷完後就能知道哪個座標所切到的磚頭數最少。

　　這樣的時間複雜度為O(n)，空間複雜度為O(m)，n為牆內磚頭總數，m為牆寬。

from collections import defaultdict


class Solution:
    def leastBricks(self, wall):
        map = defaultdict(int)

        for bricks in wall:
            # 磚頭間隙的座標
            xCord = 0
            for i in range(len(bricks) - 1):
                xCord += bricks[i]
                map[xCord] += 1

        # 以每層都會切到來更新
        res = len(wall)
        for key in map:
            res = min(res, len(wall) - map[key])

        return res

😐560. Subarray Sum Equals K

Illustration

　　給予一個整數陣列nums和一個整數k，請回傳和為k的子陣列數量。

Example 1:

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

Example 2:

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

Solutions

❌Approach #1: Brute Force

　　我們可以直觀找出所有子陣列後，判斷和是否為k。

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

class Solution:
    def subarraySum(self, nums, k):
        count = 0
        for start in range(len(nums)):
            for end in range(start + 1, len(nums) + 1):
                total = sum(nums[start:end])
                if total == k:
                    count += 1
        return count

❌Approach #2: Without Space

　　我們也可以遍歷並讓每個元素作為子陣列起點來判斷。

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

class Solution:
    def subarraySum(self, nums, k):
        count = 0
        for start in range(len(nums)):
            total = 0
            for end in range(start, len(nums)):
                total += nums[end]
                if total == k:
                    count += 1
        return count

⭐Approach #3: Using Hashmap

　　子陣列是一段位置連續的元素，若記錄每段和，就能在遍歷一趟後完成所求：

用count紀錄所求子陣列數量，total紀錄元素和，hashmap紀錄和值與出現次數
遍歷陣列nums：
- 更新total
- 若total - k已出現過（首次對到的為0，即total = k，後續對到的則會是k的倍數），則將出現次數加到count中
遍歷完時，count即為所求

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

class Solution:
    def subarraySum(self, nums, k):
        count = 0
        total = 0
        hashmap = {0: 1}
        for i in range(len(nums)):
            total += nums[i]
            if total - k in hashmap:
                count += hashmap[total - k]
            hashmap[total] = hashmap.get(total, 0) + 1
        return count

😎605. Can Place Flowers

Illustration

　　有塊可種花的土地，其中花不能鄰近彼此。現在用僅含0和1的陣列flowerbed表示種花狀態，並給予一整數n，請判斷此地能否再種至少n朵花。

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: false

Solutions

⭐Approach #1 Single Scan

　　我們可以直觀地遍歷陣列：

判斷左邊是否為空，右邊是否為空
若遍歷到的元素為空且左右邊也為空，種花
順勢判斷種花數是否已比n大，提早結束遍歷
遍歷完後，判斷所種花數是否比n大

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

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count = 0
        for i in range(len(flowerbed)):
            if flowerbed[i] == 0:
                isLeftEmpty = i == 0 or flowerbed[i - 1] == 0
                isRightEmpty = i == len(flowerbed) - 1 or flowerbed[i + 1] == 0

                if isLeftEmpty and isRightEmpty:
                    flowerbed[i] = 1
                    count += 1
                    if count >= n:
                        return True

        return count >= n

😐665. Non-decreasing Array

Illustration

　　給予一個大小為n的整數陣列nums，請判斷能否在最多調整一個元素時，使陣列成為非遞減狀態。

Example 1:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: nums = [4,2,1]
Output: false
Explanation: You cannot get a non-decreasing array by modifying at most one element.

Solutions

Approach #1: Greedy

　　如同題目敘述，我們有一次機會來調整元素，以下為解題特徵：

若調整完又出現要調整的情況，回傳False
調整方向得考量再前個元素值，目標是維持數值為非遞增狀態

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

from typing import List


class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        isViolated = False
        for i in range(1, len(nums)):
            # 數值下降
            if nums[i - 1] > nums[i]:
                if isViolated:
                    return False
                isViolated = True

                # 再前個數值較小，故將前個數值與當前數值對齊，使整體維持非遞減
                if i < 2 or nums[i - 2] <= nums[i]:
                    nums[i - 1] = nums[i]
                # 再前個數值較大，故將當前數值與前個數值對齊，使整體維持非遞減
                else:
                    nums[i] = nums[i - 1]

        return True

😎705. Design HashSet

Illustration

　　請自行設計一個雜湊集合MyHashSet，其應包含：

void add(key)：插入key
bool contains(key)：判斷key是否在其中
void remove(key)：如果key在其中就移除它

Example 1:

Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]

Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // return False, (already removed)

Solutions

　　以下所用符號，K為預定義的籃子數，M為插入雜湊集合中的相異數數量。

⭐Approach #1: LinkedList

　　這樣的時間複雜度為O(logN/K)，空間複雜度為O(K+M)。

⭐Approach #2: Binary Search Tree (BST)

　　這樣的時間複雜度為O(logN/K)，空間複雜度為O(K+M)。

Notes

　　上述做法中所用的記憶體範圍為固定。若要動態擴增空間，可用一個閥值（load factor）判斷是否要擴增記憶體空間。擴增空間能減少碰撞的發生，進而提升整體效能。但也得考慮重新雜湊（rehashing）和重新分配已存值的成本。

😎724. Find Pivot Index

Illustration

　　給予一個整數陣列nums，請算出當中的樞紐（pivot）索引。其特徵是左邊的元素和等於右邊的元素和，若沒有此索引則回傳-1。

Example 1:

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2:

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Example 3:

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Solutions

⭐Approach #1: Prefix Sum

　　使用前綴和的概念，即可得到所求。

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

class Solution(object):
    def pivotIndex(self, nums):
        S = sum(nums)
        leftsum = 0
        for i, x in enumerate(nums):
            if leftsum == (S - leftsum - x):
                return i
            leftsum += x
        return -1

😐912. Sort an Array

Illustration

　　給予一個陣列nums，請排為升序方向後回傳。避免使用內建函式，時間複雜度得在O(nlog(n))內，空間複雜度越小越好。

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.

Constraints:

1 <= nums.length <= 5 * 10⁴
-5 * 10⁴ <= nums[i] <= 5 * 10⁴

Solutions

　　用效能來分類排序法大概為二：一種僅與元素個數N有關，一種則與N和元素值域K有關。前類有Merge Sort和Quick Sort（O(NlogN)），後者則有Counting Sort（O(N+K)）。此題的元素個數和值域相當，相較下來Counting Sort更適合在此情境。

⭐Approach #1: Merge Sort

　　此題若用Quick Sort，會有測試案例因超時而失敗（其最糟情況的時間複雜度為O(N²)），故我們使用Merge Sort。它的的處理方法是分治（Divide & Conquer）：

將現有陣列分為左右子陣列
藉由遞迴持續平分，在元素量為1時開始合併
合併時排序，所有元素皆合併後即全體有序

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

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def mergeSort(arr):
            if len(arr) > 1:
                mid = len(arr) // 2
                L = arr[:mid]
                R = arr[mid:]

                mergeSort(L)
                mergeSort(R)

                l, r, merged_index = 0, 0, 0
                while l < len(L) and r < len(R):
                    if L[l] <= R[r]:
                        arr[merged_index] = L[l]
                        l += 1
                    else:
                        arr[merged_index] = R[r]
                        r += 1
                    merged_index += 1
                # copy remaining elements of L[] if any
                while l < len(L):
                    arr[merged_index] = L[l]
                    l += 1
                    merged_index += 1
                # copy remaining elements of R[] if any
                while r < len(R):
                    arr[merged_index] = R[r]
                    r += 1
                    merged_index += 1
            return arr
        return mergeSort(nums)

⭐Approach #2: Counting Sort

　　計數排序算是桶排序（Bucket Sort）的特殊情況：

使用一個記數陣列，大小取決於資料數值範圍
遍歷資料，將各元素對應的記數陣列值+1
按照陣列的順序和對應值，生成有序資料

　　這樣的時間複雜度為O(N+K)，空間複雜度為O(N)，K為元素的值範圍。

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def counting_sort(nums):
            # Create the counting hash map.
            counts = defaultdict(int)
            # Update element's count in the hash map.
            for num in nums:
                counts[num] += 1

            rearrangedIndex = 0
            # Place each element in its correct position in the array.
            for num in range(min(nums), max(nums) + 1):
                while counts[num] > 0:
                    nums[rearrangedIndex] = num
                    rearrangedIndex += 1
                    counts[num] -= 1

            return nums
        return counting_sort(nums)

😎929. Unique Email Addresses

Illustration

　　給予一個字串陣列emails，儲存不同email。各Email可藉@分成兩部分（local name和domain name），而對於local name則又會有兩項規則：

遇到"."：忽略
遇到"+"：忽略它和其後面字元

　　請回傳相異Email數量。

Example 1:

Input: emails = ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
Output: 2
Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails.

Example 2:

Input: emails = ["a@leetcode.com","b@leetcode.com","c@leetcode.com"]
Output: 3

Solutions

⭐Approach #1: Linear Iteration

　　我們可以線性掃描一遍：

按規則擬出對應Email，將其加入雜湊表中
回傳雜湊表內元素數量，即為所求

　　這樣的時間複雜度為O(N*M)，空間複雜度為O(N*M)，N為Email數量，M為Email的平均長度。

from typing import List


class Solution:
    def numUniqueEmails(self, emails: List[str]) -> int:
        record = set()
        for e in emails:
            tmp = ""
            l = 0
            metPlus = False
            while e[l] != "@":
                if e[l] != ".":
                    if e[l] == "+":
                        metPlus = True
                    if not metPlus:
                        tmp += e[l]
                l += 1
            tmp += "@"
            while l < len(e):
                tmp += e[l]
                l += 1
            record.add(tmp)
        return len(record)

😐1004. Max Consecutive Ones III

Illustration

　　給予一個二維陣列nums和整數k，若你能反轉0為1最多k次，請回傳連續1的最大長度。

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Solutions

⭐Approach #1: Sliding Window

　　如同#487，我們同樣可用滑動視窗來處理。

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

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        count = 0
        l, r = 0, 0
        res = 0
        while r < len(nums):
            if nums[r] == 0:
                count += 1
            while count > k:
                if nums[l] == 0:
                    count -= 1
                l += 1
            res = max(res, r - l + 1)
            r += 1
        return res

😎1189. Maximum Number of Balloons

Illustration

　　給予一個字串text，請判斷其中字元能不計順序地組成幾個"balloon"。

Example 1:

Input: text = "nlaebolko"
Output: 1

Example 2:

Input: text = "loonbalxballpoon"
Output: 2

Example 3:

Input: text = "leetcode"
Output: 0

Solutions

⭐Approach #1: Counting Characters

　　我們可以直觀地用雜湊表統計。

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

from collections import Counter


class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        countText = Counter(text)
        balloon = Counter("balloon")

        res = float("inf")
        for c in balloon:
            res = min(res, countText[c] // balloon[c])
        return res

😎1299. Replace Elements with Greatest Element on Right Side

Illustration

　　給予一個陣列arr，將元素替換成其右最大者，並將末元素設為-1後回傳。

Example 1:

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Explanation: 
- index 0 --> the greatest element to the right of index 0 is index 1 (18).
- index 1 --> the greatest element to the right of index 1 is index 4 (6).
- index 2 --> the greatest element to the right of index 2 is index 4 (6).
- index 3 --> the greatest element to the right of index 3 is index 4 (6).
- index 4 --> the greatest element to the right of index 4 is index 5 (1).
- index 5 --> there are no elements to the right of index 5, so we put -1.

Example 2:

Input: arr = [400]
Output: [-1]
Explanation: There are no elements to the right of index 0.

Solutions

⭐Approach #1: One-pass Iteration

　　這題如果倒過來處理，會簡單很多。

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

from typing import List


class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        if len(arr) == 1:
            arr[0] = -1
            return arr

        maxN = arr[-1]
        for i in range(len(arr) - 2, -1, -1):
            prev = arr[i]
            arr[i] = maxN
            maxN = max(maxN, prev)
        arr[-1] = -1
        return arr

😐1930. Unique Length-3 Palindromic Subsequences

Illustration

　　給予一個字串s，請回傳長為3的迴文相異子序列數量。

Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")

Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")

Solutions

⭐Approach #1: lfind&rfind and HashSet

　　我們可以用程式語言內建的找尋字元函式，搭配雜湊表來處理：

用count統計長為3的迴文數量，chars統計s中有幾種相異字元
遍歷chars：
- 找出當前字元的首個位置和末個位置
- 計算它們之間有幾種不同字元，就能算出能組成幾種長為3的迴文序列
遍歷完後，count即為所求

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

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        count = 0
        # 統計s中幾種字元
        chars = set(s)
        # 遍歷每個字元
        for char in chars:
            # 找出此字元的首個和末個位置
            first, last = s.find(char), s.rfind(char)
            # 若位置相同，自然沒有迴文可言
            # 要成為有效迴文(長度為3)，首末位置中間至少得有一個字元，故取first+1至last-1之間
            # 這中間有幾個不同字元，就有幾個長度為3的有效迴文
            count += len(set(s[first + 1:last]))
        return count

😐2017. Grid Game

Illustration

　　給予一個大小為2 * n的二維陣列grid，值代表分數，兩機器人在其中取分競賽。它們皆從(0, 0)出發，終點為(1, n-1)，每次移動僅能往右或往下。第一台機器人會先行移動，方格被經過後的分數值將歸為0。

　　第一台機器人想最小化第二台機器人所得分數，第二台則想最大化。在理想操作下，請回傳第二台機器人所能得到的最大分數值。

Example 1:

Input: grid = [[2,5,4],[1,5,1]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 0 + 4 + 0 = 4 points.

Example 2:

Input: grid = [[3,3,1],[8,5,2]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 3 + 1 + 0 = 4 points.

Example 3:

Input: grid = [[1,3,1,15],[1,3,3,1]]
Output: 7
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 1 + 3 + 3 + 0 = 7 points.

Solutions

Notes

在這路徑中，兩台機器人皆僅能往下走一次：
- 路徑形狀如同閃電，將剩下有分數的區間分成左下和右上
- 第二台機器人想得到的，就是這兩塊在不同寬度時的兩者之最大值
- 第一台機器人所追求的，則是求出每次最大值中的最小值，走其對應路線來限制它
追求首台機器人所得分數最大化，無法確保第二台機器人所得分數最小化

⭐Approach #1: Iteration

　　如同上面所述，我們記錄左下和右上這兩塊的最大值，並從這n種情況中找出最小值，即為首台機器人的目標。

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

class Solution(object):
    def gridGame(self, grid):
        result = float("inf")
        # 第一排的總和，會隨著從左至右遍歷陣列而減少
        right = sum(grid[0])
        # 第二排的總和，會隨著從左至右遍歷陣列而增加
        left = 0

        for a, b in zip(grid[0], grid[1]):
            # 將第一台機器人這次占用的向下路徑扣除
            right -= a
            result = min(result, max(left, right))
            # 將第二台機器人上次占用的向下路徑加回來
            left += b
        return result

😎2215. Find the Difference of Two Arrays

Illustration

　　給予一個0-indexed的整數陣列nums1和nums2，請回傳一個大小為2的二維陣列answer，其子陣列不需在意順序，內容為原陣列不包含另個陣列的相異元素。

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].

Example 2:

Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].

Solutions

⭐Approach #1: HashSet

　　我們可以使用雜湊表來處理。

　　這樣的時間複雜度為O(M+N)，空間複雜度為O(max(M, N))，M與N為兩陣列大小。

from typing import List


class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        res1 = set()
        res2 = set()
        for n in nums1:
            if n not in nums2:
                res1.add(n)

        for n in nums2:
            if n not in nums1:
                res2.add(n)

        return [list(res1), list(res2)]

😐2405. Optimal Partition of String

Illustration

　　給予一個字串s，請切分它們使各子字串字元在其中僅出現一次。請回傳所需的子字串最少數量。

Example 1:

Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.

Example 2:

Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").

Solutions

Approach #1: Greedy

　　我們可用個雜湊表mp記錄當前字母是否出現過，若發現再次出現，則將前面字元的記錄刪除（切分成一個子字串），重新開始計算。

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

from collections import defaultdict


class Solution:
    def partitionString(self, s: str) -> int:
        count = 1
        mp = defaultdict(bool)
        l = 0
        for r in range(len(s)):
            if mp[s[r]]:
                count += 1
                while l != r:
                    mp[s[l]] = False
                    l += 1
            mp[s[r]] = True

        return count

🧱: LeetCode – Array & Hashing

🤔Why It Matters

💡Learned

😎1. Two Sum

Illustration

Solutions

❌Approach #1 暴力法（Brute Force）

Approach #2 Two-pass 雜湊表

⭐Approach #3 One-pass 雜湊表

😎27. Remove Element

Illustration

Example 1:

Example 2:

Solutions

⭐Approach 1: Two Pointers

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

Illustration

Example 1:

Example 2:

Solutions

Approach #1: Sliding Window

😐36. Valid Sudoku

Illustration

Solutions

⭐Approach #1 使用雜湊表

😐49. Group Anagrams

Illustration

Solutions

Approach #1 Categorize by Sorted String

⭐Approach #2 Categorize by Count

😎58. Length of Last Word

Illustration

Example 1:

Example 2:

Example 3:

Solutions

⭐Approach #1: One-loop Iteration

😐75. Sort Colors

Illustration

Example 1:

Example 2:

Solutions

⭐Approach #1: One Pass

😎118. Pascal’s Triangle

Illustration

Example 1:

Example 2:

Solutions

⭐Approach #1: Dynamic Programming

😐122. Best Time to Buy and Sell Stock II

Illustration

Example 1:

Example 2:

Example 3:

Solutions

⭐Approach #1: Simple One Pass

😐128. Longest Consecutive Sequence

Illustration

Solutions

❌Approach #1 暴力解

❌Approach #2 先排序

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

😎169. Majority Element

Illustration

Example 1:

Example 2:

Solutions

⭐Approach #1: HashMap

⭐Approach #2: Boyer-Moore Voting Algorithm

😐179. Largest Number

Illustration

Example 1:

Example 2:

Solutions

😎205. Isomorphic Strings

Illustration

Example 1:

Example 2:

Example 3:

Solutions

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