14. Merge Sorted Array
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
最大的数依次插入后面
"""
while n>0:
if m<=0 or nums2[n-1]>=nums1[m-1]:
nums1[m+n-1] = nums2[n-1]
n -= 1
else:
nums1[m+n-1] = nums1[m-1]
m -= 1
15. Merge Two Sorted Lists
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head = cur = ListNode(0)
while l1 and l2:
if l1.val<l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return head.next
16. 118. Pascal's Triangle
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows==0: return list()
res = [[1]]
for i in range(1, numRows,1):
size = i+1
l = [1]
for j in range(1,size-1,1):
l.append(res[i-1][j-1]+res[i-1][j])
l.append(1)
res.append(l)
return res
17.119. Pascal's Triangle II
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
'''
看 discussion 用的一个没想到的技巧
'''
res = [1]
for _ in range(rowIndex):
res = [ x+y for x,y in zip( [0]+res, res+[0])]
return res
18. 121. Best Time to Buy and Sell Stock
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
min_price = float('inf')
for price in prices:
min_price = min(price,min_price)
profit = price - min_price
max_profit = max(max_profit,profit)
return max_profit
19. 122. Best Time to Buy and Sell Stock II
class Solution:
def maxProfit(self, prices: List[int]) -> int:
'''
peak and vally
'''
max_profit=0
for i in range(0,len(prices)-1):
if prices[i]<prices[i+1]:
max_profit += prices[i+1]-prices[i]
return max_profit
20. 169. Majority Element
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
return nums[ len(nums)//2]
21. 229. Majority Element II
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
candiate1,candiate2,count1,count2=0,1,0,0
for n in nums:
if n==candiate1:
count1 +=1
elif n==candiate2:
count2 +=1
elif count1==0:
candiate1=n
count1 =1
elif count2==0:
candiate2=n
count2 =1
else:
count1 -=1
count2 -=1
res = []
for n in [candiate1,candiate2]:
if nums.count(n)>len(nums)//3:
res.append(n)
return res
22.189. Rotate Array
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
1. o(n)空间,O(n)时间
"""
n = len(nums)
k = k%n
res=[0 for i in range(n)]
for i in range(n):
idx = (i+k)%n
res[idx]=nums[i]
for i in range(n):
nums[i]=res[i]
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
1. o(n)空间,O(n)时间
2. o(1),O(n)
"""
def reverse(nums,start,end):
while start<end:
nums[start],nums[end]=nums[end],nums[start]
start += 1
end -= 1
n = len(nums)
k = k%n
reverse(nums,0,n-1)
reverse(nums,0,k-1)
reverse(nums,k,n-1)
23. 217. Contains Duplicate
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return True if len(nums)>len(set(nums)) else False
24.219. Contains Duplicate II
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
dic = {}
for i,n in enumerate(nums):
if n in dic and i-dic[n]<=k:
return True
else:
dic[n] =i
return False
