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