python3
初學(xué)python 小白 有些地方不是很熟練 所以寫的地方有些啰嗦?? 請大家輕點噴 有錯誤的地方請大家?guī)臀抑刚?/p>
刪除排序數(shù)組中的重復(fù)項
給定一個排序數(shù)組，你需要在 原地 刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。
給定數(shù)組 nums = [1,1,2],
函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個元素被修改為 1, 2。
你不需要考慮數(shù)組中超出新長度后面的元素。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
max = -999999999999
index = 0
for x in nums:
if max < x:
max = x
nums[index] = x
index += 1
return index
買賣股票的最佳時機(jī) II
給定一個數(shù)組，它的第 i 個元素是一支給定股票第 i 天的價格。
設(shè)計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3
class Solution:
def maxProfit(self, prices: List[int]) -> int:
sum = 0
index = 0
length = len(prices)
while index < len(prices):
newIndex = index
flag = 0
while newIndex < len(prices):
x = prices[newIndex]
length = len(prices)
count = length - 1 if newIndex + 1 >= length - 1 else newIndex + 1
behind = prices[count]
if x < behind:
flag += 1
else:
break
newIndex += 1
x = prices[index]
if flag > 0:
count = index + flag
sum += prices[count] - x
index = count
index += 1
else:
count = length - 1 if index + 1 >= length - 1 else index + 1
if x - prices[count] < 0:
sum += prices[count] - x
index += 2 #跳過賣出股票那天
else:
index += 1
return sum
旋轉(zhuǎn)數(shù)組
給定一個數(shù)組，將數(shù)組中的元素向右移動 k 個位置，其中 k 是非負(fù)數(shù)。
輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
length = len(nums)-1
while k > 0:
nums.insert(0, nums[length])
del nums[length+1]
k -= 1
存在重復(fù)元素
給定一個整數(shù)數(shù)組，判斷是否存在重復(fù)元素。
如果任意一值在數(shù)組中出現(xiàn)至少兩次，函數(shù)返回 true 。如果數(shù)組中每個元素都不相同，則返回 false 。
輸入: [1,2,3,1]
輸出: true
利用map特性來判斷是否有重復(fù)的數(shù)字
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
dict = {}
for x in nums:
str1 = str(x)
dict[str1] = x
if len(dict) == len(nums):
return False
else:
return True
只出現(xiàn)一次的數(shù)字
給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。
說明：
你的算法應(yīng)該具有線性時間復(fù)雜度。 你可以不使用額外空間來實現(xiàn)嗎？
輸入: [2,2,1]
輸出: 1
class Solution:
def singleNumber(self, nums: List[int]) -> int:
length = len(nums)
index = 0
only = 0
if length == 1:
return nums[0]
nums.sort()
while index < length:
x = nums[index]
count = length - 1 if index + 1 >= length - 1 else index + 1
x2 = nums[count]
if x != x2:
if count == length - 1:
only = x2
else:
only = x
index += 1
else:
index += 2
if length - index == 1:
index -= 1
return only
兩個數(shù)組的交集 II
給定兩個數(shù)組，編寫一個函數(shù)來計算它們的交集。
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
newNumsDict = {}
littleNewNumsDict = {}
newNums = []
lengthOne = len(nums1)
lengthTwo = len(nums2)
flag = 0 #標(biāo)記從那個數(shù)組里獲取數(shù)組（這里感覺沒有必要有點啰嗦??）
if lengthOne < lengthTwo:
length = lengthOne
flag = 1
else:
length = lengthTwo
flag = 2
index = 0
while index < length:
x = 0
littleLength = 0
littleIndex = 0
if flag == 1:
x = nums1[index]
littleLength = lengthTwo
else:
x = nums2[index]
littleLength = lengthOne
while littleIndex < littleLength:
littleNumber = 0
if flag == 1:
littleNumber = nums2[littleIndex]
else:
littleNumber = nums1[littleIndex]
if x == littleNumber:
# 這里是這個算法主要比較的地方根據(jù)map key 來判斷這個數(shù)字是否已經(jīng)存在
big = newNumsDict.get(str(index))
little = littleNewNumsDict.get(str(littleIndex))
if little is None and big is None:
newNumsDict[str(index)] = x
littleNewNumsDict[str(littleIndex)] = x
newNums.append(x)
littleIndex += 1
index += 1
return newNums
加一
給定一個由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。
最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個元素只存儲單個數(shù)字。
你可以假設(shè)除了整數(shù) 0 之外，這個整數(shù)不會以零開頭。
這個題一開始沒有看懂什么意思?? 其實是叫數(shù)組轉(zhuǎn)換成整型 進(jìn)行加一計算 這樣一想還是蠻簡單的
輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數(shù)組表示數(shù)字 123。
def plusOne(digits: List[int]) -> List[int]:
# 進(jìn)行轉(zhuǎn)換
number = "".join(map(str, digits))
# 進(jìn)行 加1
number = int(number) + 1
# 在轉(zhuǎn)換回去??
return list(map(int, list(str(number))))
移動零
給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序。
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
index = 0
length = len(nums)
while index < length:
x = nums[index]
if x == 0:
#我用數(shù)組方式把數(shù)據(jù)加到后面在進(jìn)行刪除對應(yīng)位置下標(biāo)0（我覺得效率要比進(jìn)行交換要高 但給的時間相比較慢。 添加 和刪除 對于數(shù)組就是O(1)復(fù)雜度）
nums.append(x)
del nums[index]
index = 0
# 這個長度也需要進(jìn)行相應(yīng)的調(diào)正
length -= 1
else:
index += 1
兩數(shù)之和
給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個 整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素不能使用兩遍。
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
這個也是利用map key 進(jìn)行判斷
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
index = 0
length = len(nums)
map = {}
while index < length:
x = nums[index]
if map.get(target - x) is not None:
return [map.get(target - x),index ]
map[x] = index
index += 1
# 這個和上面差不多 主要思想利用差值進(jìn)行對比 到達(dá)遍歷一次（不過這個我把數(shù)組進(jìn)行了排序 下標(biāo)位置進(jìn)行改變了 這個提交不成功 但我覺得也是一種方法 故而記錄保存一下吧）
class Solution:
def twoSum(nums: List[int], target: int) -> List[int]:
index = 0
length = len(nums)
newNums = []
oneNumber = nums[0]
poorNumber = abs(target - oneNumber)
newNums.append(0)
while index < length:
x = nums[index]
if x == poorNumber:
newNums.append(index)
index += 1
return newNums
