leetcode

題目描述 將一個已經排序好的list中重複的數字刪去，並回傳list長度，必須以in-place的方式處理，不能使用額外的空間 解題思路 使用兩個指針，一個紀錄都沒重複的次數(slow)，一個紀錄當前沒重複的數字(fast)，如果重複，則更新沒重複的數字 Python class Solution: def removeDuplicates(self, nums: List[int]) -> int: n = len(nums) if n < 2: return n slow, fast = 1, 1 for fast in range(1,n): if nums[fast-1] != nums[fast]: nums[slow] = nums[fast] slow += 1 return slow Golang func removeDuplicates(nums []int) int { n := len(nums) if n < 2 { return n } slow, fast := 1, 1 for fast < n { if nums[fast-1] !...

題目描述 給一個長度固定的list，將裡面出現的0做複製，並將剩餘的元素往右移 解題思路 使用單指針做遍歷，條件有兩個，都符合才做處理 假如當前元素為0 考慮最後一個元素也為0要小於list長度 Python class Solution: def duplicateZeros(self, arr: List[int]) -> None: """ Do not return anything, modify arr in-place instead. """ i = 0 while i < len(arr): if arr[i] == 0 and i + 1 < len(arr): arr.insert(i+1, 0) arr.pop() i += 1 i += 1 Golang func duplicateZeros(arr []int) { for i := 0; i < len(arr); i++ { if arr[i] == 0 && i+1 < len(arr) { arr = append(arr[:i+1], arr[i:len(arr)-1]....

題目描述 給一個列表以及一個列表裡兩數相加起來的數，返回此兩數的列表位置 解題思路 可用字典結構當作存取位置用，並用遍歷將相減後還沒有出現的數存進字典裡，之後如果有遍歷到字典裡的數即可立馬返回位置 一樣使用雙指針，將list的index跟element分組做排序，因此新的list為由小到大，接著使用雙指針，一個指向頭一個指向尾，相加如果小於target則代表start太小，相加如果大於target代表end太大 Python 原本想用兩個for去解決 class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): left = nums[i+1:] for j in range(len(left)): if (nums[i] + left[j]) == target: return i, j+i+1 但提交後噴了time limit exceeded class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dict = {} for i in range(len(nums)): if target - nums[i] not in dict: dict[nums[i]] = i else: return [dict[target - nums[i]], i] class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: list_ele_idx = [(ele, idx) for idx, ele in enumerate(nums)] # 主要讓ele在前，使sort生效，因此前面會寫成(ele, idx)，讓ele可以排序 list_ele_idx....

題目描述 給定一個數組nums和一個值val，你需要原地移除所有數值等於val的元素，返回移除後數組的新長度。 時間複雜度為O(1)，不用考慮移除後的數組順序 解題思路 可先定義好一個指針，拿來加上長度，並用for判別是否為val，最後返回指針長度 使用雙指針，快的指針去負責遍歷整個list，慢的指針去紀錄是否有遇到題目給的值，是的話就跳過，最後返回slow Python class Solution: def removeElement(self, nums: List[int], val: int) -> int: ptr = 0 for num in nums: if num != val: nums[ptr] = num ptr += 1 return ptr class Solution: def removeElement(self, nums: List[int], val: int) -> int: fast = slow = 0 while(fast < len(nums)): if(nums[fast] != val): nums[slow] = nums[fast] slow+=1 fast+=1 return slow Golang func removeElement(nums []int, val int) int { fast, slow := 0, 0 for fast < len(nums) { if nums[fast] !...

題目描述：給一個字串，依照題目給的表格，計算出字串對應的值並做加總 思路：依照題目給的表格做一個字典，接著定義一個變數做加總，並依照題目所給的前一位的值小於當前的值時，做相對應的處理 class Solution: def romanToInt(self, s: str) -> int: numeral_map = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000} result = 0 for i in range(len(s)): if i>0 and numeral_map[s[i]] > numeral_map[s[i-1]]: result += numeral_map[s[i]] - 2* numeral_map[s[i-1]] else: result += numeral_map[s[i]] return result