1. Arrays & Hashing (9) - Python

# 1. Arrays & Hashing (9) - Python > 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主 > > 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)  * Hash * 廣義概念，將任意長度的輸入值轉換為固定長度的輸出值，此過程稱為 hashing * 輸出後的數值又稱為 hash value(雜湊值) * Hash function * 進行 hashing 時，將輸入映射到固定長度輸出的函數。 * 通常在加密領域會用到 * 在 hash table 或 hash set 等資料結構中，用來計算元素儲存的位置 * Hash table * 一種資料結構，以鍵值對(key-value pair)的形式儲存資料 * hash table 中的每個 key 都是唯一的 * 通過 hash function 將 key 映射到表格中的某個對應位置 * Python 中的 dictionary 就是 hash table 實作 * 用來實現高效率的查找與插入 * Hash set * 一種根據 hash table 所建立的資料結構，用來儲存不重複的元素集合 * 不在意元素的順序與鍵值對的關係 * Python 中的 set 就是 hash set 的實作 ## 1. Contains Duplicate **Easy** > Given an integer array `nums`, return `True` if any value appears **more than once** in the array, otherwise return `False` ### Example 1: ```java Input: nums = [1, 2, 3, 3] Output: True ``` ### Example 2: ```java Input: nums = [1, 2, 3, 4] Output: False ``` ### Recommended complexity * Time complexity: $O(n)$ * where n is the size of the input array * Space complexity: $O(n)$ ### Solution **(1) Brute force** #### 1. Brute force ```python= class Solution: def hasDuplicate(self, nums: List[int]) -> bool: for i in range(len(nums)-1): for j in range(i+1, len(nums)): if nums[i] == nums[j]: return True return False ``` #### 2. Sort ```python= class Solution: def hasDuplicate(self, nums: List[int]) -> bool: nums.sort() for i in range(len(nums)-1): if nums[i] == nums[i+1]: return True return False ``` #### 3. Hash set ```python= class Solution: def hasDuplicate(self, nums: List[int]) -> bool: hash_set = set() for i in nums: if i in hash_set: return True else: hash_set.add(i) return False ``` ## 2. Is Anagram **Easy** > Given two strings `s` and `t`, return `True` if the two strings are anagrams of each other, otherwise return `False` > > An **anagram** is a string that contains the exact same characters as another string, but the order of the characters can be different. ### Example 1: ```java Input: s = "racecar", t = "carrace" Output: Ture ``` ### Example 2: ```java Input: s = "jar", t = "jam" Output: False ``` ### Constraints * `s` and `t` consist of lowercase English letters. ### ### Solution #### 1. Sorting ```python= class Solution: def isAnagram(self, s: str, t: str) -> bool: s = sorted(s) t = sorted(t) if len(s) != len (t): return False for i in range(len(s)): if s[i] == t[i]: continue else: return False return True ``` #### 2. Hash table ```python= class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False dict_s = dict() dict_t = dict() for i in range(len(s)): if s[i] in dict_s: dict_s[s[i]] += 1 else: dict_s[s[i]] = 0 if t[i] in dict_t: dict_t[t[i]] += 1 else: dict_t[t[i]] = 0 if dict_s == dict_t: return True else: return False ``` ## 3. Two Integer Sum **Easy** > Given an array of integers `nums` and an integer `target`, return the indices `i` and `j` such that `nums[i] + nums[j] == target` and `i != j`. > > You may assume that every input has exactly one pair of indices `i` and `j` that satisfy the condition. > > Return the answer with the smaller index first. ### Example 1: ```java Input: nums = [3, 4, 5, 6], target = 7 Output: [0,1] ``` ### Example 2: ```java Input: nums = [5, 5], taeget = 10 Output: [0, 2] ``` ### Example 3: ```java Input: nums = [5, 5], target = 10 Output: [0, 1] ``` ### Constraints * `2 <= nums.length <= 1000` * `-10,000,000 <= nums[i] <= 10,000,000` * `-10,000,000 <= target <= 10,000,000` ### Solution #### 1. Brute force ```python= class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: return [i, j] ``` ## 4. Encode and Decode Strings **Medium** > Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings. > > Please implement `encode` and `decode` ### Example 1: ```java Input: ["neet","code","love","you"] Output:["neet","code","love","you"] ``` ### Example 2: ```java Input: ["we","say",":","yes"] Output: ["we","say",":","yes"] ``` ### Constraints * `0 <= strs.length < 100` * `0 <= strs[i].length < 200` * `strs[i]` contains only UTF-8 characters. 以下程式碼**測資成功但提交失敗**。因為 while 迴圈中儲存每個字串的長度時，只儲存第一個數字(`num = int(s[i])`)，如果某個字串有 9 個字元以上就會出錯，例如: ### Solution #### 1. My (False) * `["neet","code","love","you"]` 編碼後為 `"4#neet4#code4#love4#you"`，可以正確解碼 * `["ThisIsProblem", "ha"]` 編碼後為 `13#ThisIsProblem2#ha` 無法正確解碼，因為第一個字串的長度只會讀取到 `1` 而不是 `13` ```python= class Solution: def encode(self, strs: List[str]) -> str: encode = "" for s in strs: encode += f"{len(s)}#{s}" return encode def decode(self, s: str) -> List[str]: decode = [] i = 0 while (i < len(s)): num = int(s[i]) # problem is here !! decode.append(s[i+2:i+2+num]) i += (2+num) return decode ``` ### 2. Correct version ```python= class Solution: def encode(self, strs: List[str]) -> str: encode = "" for s in strs: encode += f"{len(s)}#{s}" return encode def decode(self, s: str) -> List[str]: decode = [] i = 0 while (i < len(s)): j = i while (s[j] != "#"): j += 1 length = int(s[i:j]) i = j + 1 decode.append(s[i:i+length]) i = i + length return decode ``` ## 5. Product of Array Except Self **Medium** > Given an integer array `nums`m return an array `output` where `output[i]` is the product of all the elements of `nums` except `nums[i]`. > > Each product is **guaranteed** to fit in a **32-bit** integer. > > Follow-up: Could you solve it in $O(n)$ time without using the division operation ? ### Example 1: ```java Input: nums = [1, 2, 4, 6] Output: [48, 24, 12, 8] ``` ### Example 2: ```java Input: nums = [-1, 0, 1, 2, 3] Output: [0, -6, 0, 0, 0] ``` ### Constraints * `2 <= nums.length <= 1000` * `20 <= nums[i] <= 20` ### Solution #### 1. My (Division ver.) * 有使用除法進行運算 * 時間複雜度為: $O(n^2)$ ```python= class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: product = 1 for item in nums: product *= item output = [] for i in range(len(nums)): if nums[i] != 0: res = product // nums[i] output.append(res) else: res = 1 for j in range(len(nums)): if j == i: pass else: res *= nums[j] output.append(res) return output ``` #### 2. Correct (Non-division ver.) * 注意迴圈不能針對串列的元素迭代，應該要迭代 `range()`，否則如果串列有相同元素就會出錯 * 時間複雜度為: $O(n^2)$ ```python= class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: res = [] for i in range(len(nums)): product = 1 for j in range(len(nums)): if j == i: pass else: product *= nums[j] res.append(product) return res ``` #### 3. Correct (Prefix & postfix) * 時間複雜度 $O(n)$ * 空間複雜度 $O(n)$，因為使用兩個 array 來儲存 prefix 與 postfix ```python= class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: pre = [1] * len(nums) post = [1] * len(nums) for i in range(len(nums)): if i == 0: pre[i] = nums[i] post[-1-i] = nums[-1-i] else: pre[i] = pre[i-1] * nums[i] post[-1-i] = post[-i] * nums[-1-i] res = [] for i in range(len(nums)): if i == 0: res.append(post[i+1]) elif i == (len(nums)-1): res.append(pre[i-1]) else: res.append(pre[i-1] * post[i+1]) return res ``` * 時間複雜度 $O(n)$ * 空間複雜度 $O(n)$ ```pytohn= class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: left_default = right_default = 1 n = len(nums) res = [1] * n # prefix produt for i in range(1, n): res[i] = res[i] * nums[i-1] * left_default left_default *= nums[i-1] # postfix product for i in range(1, n): res[-1-i] = res[-1-i] * nums[-i] * right_default right_default *= nums[-i] return res ``` ## 6. Valid Sudoku **Medium** > You are given a `9 x 9` Sudoku board `board`. A Sudoku board is valid of the following rules are followed: > 1. Each row must contain the digits `1-9` without duplicates. > 2. Each column must contain the digits `1-9` without duplicates. > 3. Each of the nine `3x3` sub-boxes of the grid must contain the digits `1-9` without duplicates. > > Return `True` if the Sudoku board is valid, otherwise return `False` > Note: A board does not need to be full or be solvable to be valid. ### Example 1: ![image](https://hackmd.io/_uploads/H15JvMMWke.png) ```java Input: board = [["1","2",".",".","3",".",".",".","."], ["4",".",".","5",".",".",".",".","."], [".","9","8",".",".",".",".",".","3"], ["5",".",".",".","6",".",".",".","4"], [".",".",".","8",".","3",".",".","5"], ["7",".",".",".","2",".",".",".","6"], [".",".",".",".",".",".","2",".","."], [".",".",".","4","1","9",".",".","8"], [".",".",".",".","8",".",".","7","9"]] Output: true ``` ### Example 2: ```java Input: board = [["1","2",".",".","3",".",".",".","."], ["4",".",".","5",".",".",".",".","."], [".","9","1",".",".",".",".",".","3"], ["5",".",".",".","6",".",".",".","4"], [".",".",".","8",".","3",".",".","5"], ["7",".",".",".","2",".",".",".","6"], [".",".",".",".",".",".","2",".","."], [".",".",".","4","1","9",".",".","8"], [".",".",".",".","8",".",".","7","9"]] Output: false ``` ### Constraints * `board.length == 9` * `board[i].length == 9` * `board[i][j]` is a digit `1-9` or `"."`. ### Solution #### 1. Brute force ```python= class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: # Brute force solution # search row for row in range(9): numbers = set() for idx in range(9): if board[row][idx] == ".": continue if board[row][idx] in numbers: return False else: numbers.add(board[row][idx]) # search column for col in range(9): numbers = set() for idx in range(9): if board[idx][col] == ".": continue if board[idx][col] in numbers: return False else: numbers.add(board[idx][col]) # search sub-boxes for box in range(9): numbers = set() for i in range(3): for j in range(3): row = (box // 3) * 3 + i col = (box % 3) * 3 + j if board[row][col] == ".": continue if board[row][col] in numbers: return False else: numbers.add(board[row][col]) return True ``` #### 2. Hash set ```python= class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: # Hash set rows = defaultdict(set) cols = defaultdict(set) squares = defaultdict(set) for r in range(9): for c in range(9): if board[r][c] == ".": continue if ((board[r][c] in rows[r]) or \ (board[r][c] in cols[c]) or \ (board[r][c] in squares[(r//3, c//3)])): return False else: rows[r].add(board[r][c]) cols[c].add(board[r][c]) squares[(r//3, c//3)].add(board[r][c]) return True ``` ## . Longest Conseccutive Sequence **Medium** > Given an array of integers `nums`, return the length of the longest consecutive seauence of elements. > > A consecutive sequence is a sequence of elements in which each element is exactly `1` greater than the previous element. > > You must write an algorithm that runs in $O(n)$ time. ### Example 1: ```java Input: nums = [2, 20, 4, 10, 3, 4, 5] Output: 4 ``` The longest consecutive sequence is `[2, 3, 4, 5]` ### Example 2: ```java Input: nums = [0, 3, 2, 5, 4, 6, 1, 1] Output: 7 ``` ### Constraints * `0 <= nums.length <= 1000` * `-10^9 <= nums[i] <= 10^9` ### Solution #### 1. My version 結合了 sorted 與 hash set 的概念 ```python= # My version class Solution: def longestConsecutive(self, nums: List[int]) -> int: if not nums: return 0 HashSet = set(nums) HashSet_sort = sorted(HashSet) length = [] count = 1 for i in range(len(HashSet_sort)-1): if list(HashSet_sort)[i+1] - list(HashSet_sort)[i] == 1: count += 1 else: length.append(count) count = 1 length.append(count) return max(length) ``` ##### 2.