Table of Contents:

🤔

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

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

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

💡

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

😎605. Can Place Flowers

Description

　　有塊可種花的土地，其中花不能鄰近彼此。現在用僅含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

Description

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

Description

　　請自行設計一個雜湊集合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

Description

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

Description

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

Description

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

Description

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

Description

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

Description

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

😎1380. Lucky Numbers in a Matrix

Description

　　給予一個m x n，值相異的陣列matrix，請回傳當中的幸運數字（順序不限）。它們在陣列中的當列（row）為最小值，當行（column）為最大值。

Example 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.

Example 2:

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.

Example 3:

Input: matrix = [[7,8],[1,2]]
Output: [7]
Explanation: 7 is the only lucky number since it is the minimum in its row and the maximum in its column.

Solutions

Approach #1: Simulation

　　我們可以按照題目要求，直觀地寫下判斷過程。

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

class Solution:
    def luckyNumbers(self, matrix):
        N = len(matrix)
        M = len(matrix[0])

        rowMin = []
        for i in range(N):
            rMin = float('inf')
            for j in range(M):
                rMin = min(rMin, matrix[i][j])
            rowMin.append(rMin)

        colMax = []
        for i in range(M):
            cMax = float('-inf')
            for j in range(N):
                cMax = max(cMax, matrix[j][i])
            colMax.append(cMax)

        result = []
        for i in range(N):
            for j in range(M):
                if matrix[i][j] == rowMin[i] and matrix[i][j] == colMax[j]:
                    result.append(matrix[i][j])

        return result

⭐Approach #2: Greedy

　　經思考後，我們引入一個觀念來簡化找尋過程：幸運數字不會超過一個。我們先假設有兩個幸運數字X和Y處於相異行列，但實際列舉其大小時，會發現得同時滿足Y<X與Y>X，故假設錯誤。

　　所以，要找出那可能的唯一幸運數字，我們先找出每列最小元素，並記住當中最大值；再找出每行最大元素，記住當中最小值。若兩極值相同，即為所求，否則代表無幸運數字。

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

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        N, M = len(matrix), len(matrix[0])

        r_min_max = float('-inf')
        for i in range(N):
            r_min = min(matrix[i])
            r_min_max = max(r_min_max, r_min)

        c_max_min = float('inf')
        for i in range(M):
            c_max = max(matrix[j][i] for j in range(N))
            c_max_min = min(c_max_min, c_max)

        if r_min_max == c_max_min:
            return [r_min_max]
        else:
            return []

😐1930. Unique Length-3 Palindromic Subsequences

Description

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

Description

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

Description

　　給予一個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)]

😎605. Can Place Flowers

Description

　　有塊可種花的土地，其中花不能鄰近彼此。現在用僅含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

Description

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

Description

　　請自行設計一個雜湊集合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

😎724. Find Pivot Index

Description

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

Description

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

⭐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

Description

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

Description

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

Description

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

Description

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

😎1380. Lucky Numbers in a Matrix

Description

　　給予一個m x n，值相異的陣列matrix，請回傳當中的幸運數字（順序不限）。它們在陣列中的當列（row）為最小值，當行（column）為最大值。

Example 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.

Example 2:

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.

Example 3:

Input: matrix = [[7,8],[1,2]]
Output: [7]
Explanation: 7 is the only lucky number since it is the minimum in its row and the maximum in its column.

Solutions

Approach #1: Simulation

　　我們可以按照題目要求，直觀地寫下判斷過程。

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

class Solution:
    def luckyNumbers(self, matrix):
        N = len(matrix)
        M = len(matrix[0])

        rowMin = []
        for i in range(N):
            rMin = float('inf')
            for j in range(M):
                rMin = min(rMin, matrix[i][j])
            rowMin.append(rMin)

        colMax = []
        for i in range(M):
            cMax = float('-inf')
            for j in range(N):
                cMax = max(cMax, matrix[j][i])
            colMax.append(cMax)

        result = []
        for i in range(N):
            for j in range(M):
                if matrix[i][j] == rowMin[i] and matrix[i][j] == colMax[j]:
                    result.append(matrix[i][j])

        return result

⭐Approach #2: Greedy

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

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        N, M = len(matrix), len(matrix[0])

        r_min_max = float('-inf')
        for i in range(N):
            r_min = min(matrix[i])
            r_min_max = max(r_min_max, r_min)

        c_max_min = float('inf')
        for i in range(M):
            c_max = max(matrix[j][i] for j in range(N))
            c_max_min = min(c_max_min, c_max)

        if r_min_max == c_max_min:
            return [r_min_max]
        else:
            return []

😐1930. Unique Length-3 Palindromic Subsequences

Description

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

Description

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

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

Description

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

Description

　　給予一個字串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 (3/3)

🤔

💡

😎605. Can Place Flowers

Description

Example 1:

Example 2:

Solutions

⭐Approach #1 Single Scan

😐665. Non-decreasing Array

Description

Example 1:

Example 2:

Solutions

Approach #1: Greedy

😎705. Design HashSet

Description

Solutions

⭐Approach #1: LinkedList

⭐Approach #2: Binary Search Tree (BST)

Notes

😎724. Find Pivot Index

Description

Example 1:

Example 2:

Example 3:

Solutions

⭐Approach #1: Prefix Sum

😐912. Sort an Array

Description

Example 1:

Example 2:

Constraints:

Solutions

⭐Approach #1: Merge Sort

⭐Approach #2: Counting Sort

😎929. Unique Email Addresses

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: Linear Iteration

😐1004. Max Consecutive Ones III

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: Sliding Window

😎1189. Maximum Number of Balloons

Description

Example 1:

Example 2:

Example 3:

Solutions

⭐Approach #1: Counting Characters

😎1299. Replace Elements with Greatest Element on Right Side

Description

Example 1:

Example 2:

Solutions

⭐Approach #1: One-pass Iteration

😎1380. Lucky Numbers in a Matrix

Description

Example 1:

Example 2:

Example 3:

Solutions

Approach #1: Simulation

⭐Approach #2: Greedy

😐1930. Unique Length-3 Palindromic Subsequences

Description

Example 1:

Example 2:

Example 3:

Solutions

😐2017. Grid Game

Description

Example 1:

Example 2:

Example 3: