algorithms

75. Sort Colors Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library’s sort function. 規則 in-place algorithm (不可用其他資料結構，對原有數據做改變) 不可用原生 sort 函式 測試案例 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] 思路 用雙指針 遍歷 實作 class Solution: def sortColors(self, nums: List[int]) -> None: zero_index = 0 # 左指針 two_index = len(nums) - 1 # 右指針 index = 0 # 遍歷指針 # [2,0,2,1,1,0] # 0 <= 5 # [0, 0, 2, 1, 1, 2], two_index = 4, index = 0 # 1 <= 4 # [0, 0, 2, 1, 1, 2], zero_index = 1, index = 1 # [0, 0, 2, 1, 1, 2], zero_index = 1, index = 2 # [0, 0, 1, 1, 2, 2], two_index = 3, index = 2 # 2 <= 3 # [0, 0, 1, 1, 2, 2], zero_index = 2, index = 3 # 4 <= 3 # skip # return while index <= two_index: if nums[index] == 0: nums[index], nums[zero_index] = nums[zero_index], nums[index] # 交換 zero_index += 1 index += 1 elif nums[index] == 2: nums[index], nums[two_index] = nums[two_index], nums[index] # 交換 two_index -= 1 else: index += 1 return nums

思路 找出最小值並放入新陣列依序排列 n*n = O(n^2) 實作 def selectionSort(nums): result = [] # 結果陣列 while nums: smallest = self.helper(nums) result.append(nums.pop(smallest)) # 取出最小值並放入新陣列 return result def helper(self, nums): smallest_i = 0 smallest = nums[smallest_i] for i in range(1, len(nums)): if nums[i] < smallest: # 找出最小值 smallest = nums[i] # 更新最小值 smallest_i = i # 更新最小值索引 return smallest_i 也可以透過內建函式達到一樣效果，具體流程如下: min() 取出最小值 remove 在 nums 內的最小值 append 進入新陣列 def selectSort2(self, nums): result = [] while nums: smallest = min(nums) # 取出最小值 nums....

704. Binary Search Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity. 規則 給予一個數字 target 和一個數組 nums，如果 nums 中存在 target，則返回 target 的索引，反之返回 -1。 測試案例 Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4 Example 2: Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1 思路 取出中間值 如果 low > high ,則代表沒找到，回傳 -1 如果中間值等於 target，命中則回傳 如果中間值大於 target，則從中間值開始往左找 如果中間值小於 target，則從中間值開始往右找 實作 def search(self, nums, target) -> int: return self....

46. Permutations Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. 規則 全排列 測試案例 Example 1: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Example 2: Input: nums = [0,1] Output: [[0,1],[1,0]] Example 3: Input: nums = [1] Output: [[1]] 思路 列出所有可能性 觀察底下為 swap 後即可 合併為同一陣列輸出 深度優先 實作 result = [] # 初始化 result # {0, 1, 2} #{1} -> 2 #{2} -> 2 #{3} -> 2 for i in range(start, len(nums)): # swap 值交換，以便生成不同的排列。這是排列算法的關鍵部分，通過不斷交換元素，生成不同的排列。 # 外層開始 nums[0] = 1 # 外層開始 nums[1] = 2 # 外層開始 nums[2] = 3 nums[start], nums[i] = nums[i], nums[start] result += self....

383. Ransom Note Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise. Each letter in magazine can only be used once in ransomNote. 規則 給予 ransomNote(target) 和 magazine(dict) 拼字，如果拼得出來=True，反之為 False。 測試案例 Example 1: Input: ransomNote = "a", magazine = "b" Output: false Example 2: Input: ransomNote = "aa", magazine = "ab" Output: false Example 3: Input: ransomNote = "aa", magazine = "aab" Output: true 思路 根據規則每個字只能用一次，如果重複使用則返回 False 創建 hashmap 儲存 magazine values loop 依序遞減 解法 def canConstruct(self, ransomNote: str, magazine: str): values = {} for c in magazine: if c not in values: # 不存在 hashmap 內 values[c] = 1 # 建立 else: values[c] += 1 # 有則+1 for c in ransomNote: if c not in values or values[c] == 0: # 不存在或已經用完 return False else: values[c] -= 1 # 有則-1 return True 使用內建 defaultdict 來處理 hashmap，解法大同小異，但速度較快且代碼更簡潔。...

1. Two Sum Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. 規則 給一組陣列以及 target，回傳某兩數 index 相加等於 target 數。 測試案例 Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]....