Remove Duplicates from Sorted Array
Example 1:
Input: nums = [1,1,2] Output: 2, nums = [1,2,_] Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
class Solution:2def removeDuplicates(self, nums: List[int]) -> int:3#nums = [1,1,2]4#nums = [0,0,1,1,1,2,2,3,3,4]5head=07for i in range(1, len(nums)):8if nums[head] != nums[i]:9head +=110nums[head]=nums[i]11print(nums)14print(head+1)15return head+1 # return Output16
Best Time to Buy and Sell Stock II
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.
class Solution:2def maxProfit(self, prices: List[int]) -> int:3#Input: prices = [7,1,5,3,6,4]5#[1,2,3,4,5]67ans = 08for i in range(0, len(prices)-1):9if prices[i + 1] > prices[i]:10ans += prices[i + 1] - prices[i]11print(ans)12return ans1415'''17题目大意18可以多次进行买卖操作，但是每天只能要么买要么卖，求最大收益。1920解题方法21这个题不是说可以任意的挑选，而是要按照每天的顺序挑选。这样就很简单了，只要后面的一天比这天的价格高就买入卖出就可。22'''
Rotate Array
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]
class Solution:2def rotate(self, nums: List[int], k: int) -> None:3"""4Do not return anything, modify nums in-place instead.5"""6#nums: [1,2,3,4,5,6,7] 37#[-1,-100,3,99] 28def numReverse(start, end):11while start < end:12nums[start], nums[end] = nums[end], nums[start]13start += 114end -= 115k, n = k % len(nums), len(nums) # 3%7=3 2%1=017if k:19numReverse(0, n - 1) #[7,6,5,4,3,2,1]20numReverse(0, k - 1) #[5,6.7,4,3,2,1]21numReverse(k, n - 1) #[5,6.7,1,2,3,4]2223'''24雙指針（Two Pointer）25分析/解題：27題目給定一個陣列，將其往右輪轉k步，28要求直接將該陣列調整成輪轉後的結果。2930這題一旦沒有Note的要求的話瞬間簡單一百倍。31舉例來說，我們可以直接將後k項和前l-k項合併起來(l為陣列長度)，32就會是答案了；或者，將整個陣列重複銜接一次，取[(l-k):(2 * l - k)]亦可。33(這兩個解法筆者列在Python的註解中供讀者參閱)34但，它們都不是in-place。3536要考慮到in-place的話，我們必須知道，37一定有方法能讓他們跑到該有的地方，且不需用到超過O(1)以外的空間，38一般就意味著會在陣列進行swap的操作(交換兩個元素)。3940先看一下原本的例子：41[1,2,3,4,5,6,7] and k = 3 -> [5,6,7,1,2,3,4]42先不論其他的部分，我們可以發現5~7從最尾端3個變成最前面的3個了；43與此同時，1~4自然從最前面4個變成最尾端4個。44我們先不論大家的順序，先將整個陣列倒過來的話，45可以先達到1~4，5~7分別占據目標的區塊的效果：[7,6,5,4,3,2,1]。46接著再比對一下，發現區塊是對了，但各自剛好被顛倒過一次，47那麼我們再對7~5及4~1分別各進行一次反轉，就會得到我們要的結果。4849所以整個流程就會變成：5051將整個陣列進行反轉52將前k個數進行反轉53將後l-k個數進行反轉54'''
Submission Result: Wrong Answer More Details
[1,2,3,4,5,6]
11
k = k % len(nums) #若沒加上這行 會error
11%6=5
Contains Duplicate
Example 1:
Input: nums = [1,2,3,1] Output: true
class Solution:2def containsDuplicate(self, nums: List[int]) -> bool:3#Input: nums = [1,2,3,1]4#集合（set）是一个无序的不重复元素序列。 裡面的值一定不是重複的6print(nums)8print(set(nums))9print(len(nums))10print(len(set(nums)))11return len(nums) != len(set(nums))13'''17暴力解 會超時19for i in range(0, len(nums)-1):20for j in range(i+1, len(nums)): #改i+121if nums[i]==nums[j]:22return True #也可以return 123'''2425#或者可以用sorted進行排序 就不會超時
Single Number
Example 1:
Input: nums = [2,2,1] Output: 1
在Python中，^ 符號不是指數運算，而是按位異或（XOR）運算符。當你寫 a = 2^2 時，Python 將進行以下步驟：
將
2和2轉換為二進位：2的二進位表示是102的二進位表示也是10
對這兩個二進位進行按位異或運算：
10
當你執行 `print(a)` 時，結果會是 `0`。
這是因為按位異或運算符 `^` 在每一位上，
因為當1碰到1 = 0 ， 0碰到0 = 0。
因為當1碰到1 = 0 ， 0碰到0 = 0。
當改成a=2^2^3
a就會變成 a=3， 因為2^2=0，所以2^2^3=3
# print(bin(2))
# print(bin(3))
# print(bin(1))
# a=2^3^3
# print(a)
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans=0
for i in range(len(nums)):
ans^= nums[i]
return ans
|
class Solution:2def singleNumber(self, nums: List[int]) -> int:3#Input: nums = [2,2,1]4#[4,1,2,1,2]5ans = 07for ele in nums:8ans ^= ele9print(ans)10return ans12'''15這題算是經典題目，因為經典做法太神奇了，16這題考的概念可以用 XOR 漂亮的解出來。1718python 裡面，XOR 的符號表示做 「^」，19我們運用以下特性，同一個東西重複 XOR 兩次則變回原樣，20就可以在最小時間與空間解決此問題。210 ^ a = a22a ^ a = 023b ^ a ^ a = b2425a | b | a ^ b26--|---|------270 | 0 | 0280 | 1 | 1291 | 0 | 1301 | 1 | 03132'''
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# Input: nums = [2,2,1]
# Output: 1
count_dict={}
for num in nums:
if num in count_dict:
count_dict[num]+=1
else:
count_dict[num]=1
# Find the number that appears only once
for key, value in count_dict.items():
if value == 1:
return key |
Intersection of Two Arrays II
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]
class Solution:2def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:3#Input: nums1 = [1,2,2,1], nums2 = [2,2]4n1= sorted(nums1)6n2= sorted(nums2) #已經由小到大 排序完成 nums1 = [1,1,2,2], nums2 = [2,2]7i=010j=011q=[] #設定好串列初始值12while (i < len(n1)) and (j < len(n2)) :14if n1[i]>n2[j]:15j +=116elif n1[i]<n2[j]:18i +=119else: #n1==n221q.append(n1[i])22i +=123j +=124return q
Plus One
Example 1:
Input: digits = [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Incrementing by one gives 123 + 1 = 124. Thus, the result should be [1,2,4].
class Solution:2def plusOne(self, digits: List[int]) -> List[int]:3#Input: digits = [1,2,3]4#Output: [1,2,4]5number_string = ''7number_new = []89# list 用字串串起來10for number in digits:11number_string += str(number) #12312# 字串轉數字，數字 +114number_string = str(int(number_string) + 1) #1241516# 每一個位元拆開成新的 list18for number in number_string:19#120#221#422print(number)23number_new.append(int(number))24#TypeError: ['1', '2', '4'] is not valid value for the expected return type integer[]26#轉成integer 用int()27return number_new2931'''32題目分析33傳入一個純正整數的陣列34該陣列是一個大正整數，依照每個位數拆開35計算出該正整數 +1 的結果36把結果依照輸入的方式也輸出成陣列37解題過程38把輸入的陣列數字一個一個串成字串39字串轉換成數字，然後 +140每個位元拆開做成新的 list 後回傳41'''
Move Zeroes
Example 1:
Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]
class Solution:2 def moveZeroes(self, nums: List[int]) -> None:3 """4 Do not return anything, modify nums in-place instead.5 """6 #Input: nums = [0,1,0,3,12]7 8 head = 09 for i in range(0,len(nums)):10 if nums[i]!=0: #如果非0的話11 nums[head] = nums[i] 12 head += 1 13 14 for j in range(head, len(nums)):15 nums[j] = 016 17 18'''19這邊要順便提到的一個名詞叫in-place algorithm。20所謂的in-place，就是指所有的操作修改，除了一些計數用的變數外，21基本上都在原先的資料結構內解決。2223所以好像不能sorted2425 nums=sorted(nums) #nums = [0,0,1,3,12]26 print(nums)27 for i in range(0,len(nums)-1): 28 if nums[i+1]!=nums[i]:29 count = i+130 break31 32 head=033 while count<len(nums):34 nums[head], nums[count]= nums[count], 035 print(nums)36 count +=137 head +=138 39 return nums40 41''' Two Sum
Example 1:
Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
class Solution:2def twoSum(self, nums: List[int], target: int) -> List[int]:3# Input: nums = [2,7,11,15], target = 94# 雙指針（Two Pointer）5# https://ithelp.ithome.com.tw/articles/102631036# https://ithelp.ithome.com.tw/articles/1026924678'''10這題主要考的是 HashTable，11需要先建立一張表 (此處建立 dict)，12利用 「key -> value」 的特性保存 「剩餘值 對應 index」13因此當後續的計算，發現剩餘值存在 dict 的 key 中，14就能快速反查表得到 index。15'''16#字典做法17mydict = {}18for idx in range(0,len(nums)):20#print(mydict.keys())21if nums[idx] in mydict.keys():22print(mydict)23return [mydict[nums[idx]], idx]24else:25mydict[target - nums[idx]] = idx #保存 「剩餘值」 {'7': 0}26'''29nums_list = list(nums)30nums_list.sort()31print(nums_list)32i = 033j = len(nums) - 1343536if target>=0:37while (i<j):38if (nums_list[i]+nums_list[j]>target):39j -=140elif (nums_list[i]+nums_list[j]<target):41i +=142elif (nums_list[i]+nums_list[j]== target):43return sorted([i,j])44else: #題目會給負值進行測試， 因此要特別改45while (i<j):46if (nums_list[i]+nums_list[j]<target):47j -=148elif (nums_list[i]+nums_list[j]>target):49i +=150elif (nums_list[i]+nums_list[j]== target):51return sorted([i,j])52return sorted([i,j])5456題目會給負值進行測試， 因此要特別改57[-1,-2,-3,-4,-5]58-8596061'''
Valid Sudoku
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
def is_unit_valid(unit):
filtered_unit = []
for i in unit:
if i != '.':
filtered_unit.append(i)
return len(filtered_unit) == len(set(filtered_unit))
def is_subbox_valid(board, row, col):
subbox = []
for i in range(row, row + 3):
for j in range(col, col + 3):
if board[i][j] != '.':
subbox.append(board[i][j])
return len(subbox) == len(set(subbox))
# 檢查每一行
for row in board:
if not is_unit_valid(row):
return False
# 檢查每一列
for col in range(9):
column = []
for row in range(9):
column.append(board[row][col])
if not is_unit_valid(column):
return False
# 檢查每個 3x3 子格
for i in range(0, 9, 3):
for j in range(0, 9, 3):
if not is_subbox_valid(board, i, j):
return False
return True |
これは小さな秘密で、見せたくないです59f93f86-ee81-41b9-bf1d-d0827e0d4af8
Rotate Image
要將 n x n 的 2D 矩陣順時針旋轉 90 度，並且必須在原地進行（不分配另一個 2D 矩陣），我們可以透過兩個步驟來完成這個任務：
- 先將矩陣轉置（交換矩陣的行和列）。
- 然後再反轉矩陣的每一行。
這兩個步驟的具體實現如下：
- 轉置矩陣：將 matrix[i][j] 與 matrix[j][i] 交換。
- 反轉每一行：將每一行的元素順序顛倒。
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
# 轉置矩陣
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# 反轉每一行
for i in range(n):
matrix[i].reverse()
print(matrix) |
matrix[i].reverse() 和 matrix[i] = matrix[i][::-1] 這兩種方法都可以用來反轉列表，但在性能和可讀性上有所不同。在大多數情況下，matrix[i].reverse() 通常比 matrix[i] = matrix[i][::-1] 更快，因為它是原地操作，不需要額外的內存分配和拷貝。
因此，matrix[i].reverse() 更好，尤其是在處理大數據量時，它更高效且更節省內存。
これは小さな秘密で、見せたくないですc918248c-3360-469b-9723-3afce81c8ac2
💫💫💫
qq=[1,2,3]
print(qq.reverse())
Q: 為何print出來是None?
當你使用 qq.reverse() 方法時，這個方法是用來反轉列表 qq 的順序，但它並不返回任何值，也就是說它是在原地修改列表，而不是返回一個新的列表。
因此，當你執行 print(qq.reverse()) 時，它會先執行 qq 的反轉操作，然後 reverse() 方法本身沒有返回值，所以 print() 顯示的是 None。正確的做法是先執行 qq.reverse()，然後直接打印 qq，而不是打印 qq.reverse() 的返回值。
例如：
qq = [1, 2, 3]
qq.reverse() # 在原地反轉 qq
print(qq) # 打印反轉後的 qq
這樣將會輸出：
[3, 2, 1]
你就可以看到 qq 列表已經被反轉過了。
沒有留言:
張貼留言
喜歡我的文章嗎? 喜歡的話可以留言回應我喔! ^^