目录

【1】

20. Valid Parentheses（Easy）

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
1)Open brackets must be closed by the same type of brackets.
2)Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example:
Input: "([)]" Output: false
Input: "{[]}" Output: true

# my solution ,Runtime: 32 ms, faster than 99.51%, T(n)=S(n)=O(n)
class Solution:
    def isValid(self, s: str) -> bool:
        if not s:
            return True
        stack=[]
        mapping = {')' : '(', '}' : '{', ']' : '['}
        for i in s:
            if i in "([{":
                stack.append(i)
            elif stack ==[]:
                return False
            else:
                temp=stack.pop(-1)
                if temp==mapping[i]:
                    continue
                else:
                    stack.append(temp)
                    stack.append(i)
        if stack:
            return False
        return True

21. Merge Two Sorted Lists（Easy）

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# my solution, T(n)=S(n)=O(m+n)
# Runtime: 40 ms, faster than 99.28%
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head=l3=ListNode(0)
        while l1 and l2:
            if l1.val< l2.val:
                l3.next = l1
                l1 = l1.next
            else:
                l3.next = l2
                l2 = l2.next
            l3 = l3.next
        res = l1 or l2
        while res:
            l3.next = res
            l3 = l3.next
            res = res.next
        return head.next

22. Generate Parentheses（Medium）

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

回溯法

# Approach 2: Backtracking
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans=[]
        def backtrack(s='',l=0,r=0):
            if len(s)==2*n:
                ans.append(s)
            if l<n:
                backtrack(s+'(',l+1,r)
            if r<l:
                backtrack(s+')',l,r+1)
        backtrack()
        return ans

23. Merge k Sorted Lists（Hard）

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Approach 1: Brute Force, T(n)=O(NlogN) (sorted time), S(n)=O(N) 
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        nodes=[]
        for l in lists:
            while l:
                nodes.append(l.val)
                l=l.next
        head = p = ListNode(0)
        for node in sorted(nodes):
            p.next = ListNode(node)
            p = p.next
        return head.next

# Approach 2: Compare one by one
# Approach 3: Optimize Approach 2 by Priority Queue, use in python2
# T(n)=O(Nlogk) (sorted time), S(n)=O(N) 
"""
 Problem of python3:
 为了获取到当前node.val最小对应到的那个ListNode对象。
 理论上tuple第二个位置的ListNode对象的大小关系是不被关心的（我们关心的起作用的应该是tuple第一个位置存放的node.val），
 但实际上，当第一个位置的node.val相同的时候，会继续比较tuple的第二个位置的大小关系，
 这时因为python3不支持未定义__lt__方法的ListNode对象之间的大小比较，所以就发生了TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'
（可以看到发生Runtime Error的那组样例存在部分的value相同的node）。
"""
from queue import PriorityQueue
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        head = p = ListNode(0)
        q = PriorityQueue()
        for l in lists:
            if l: 
                q.put((l.val,l))
        while not q.empty():
            p.next = q.get()[1]
            p = p.next
            if p.next:
                q.put((p.next.val,p.next))
        return head.next

31. Next Permutation（Medium）

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Examples:
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

# my solution, T(n)=O(N), S(n)=O(1)
# Runtime: 44 ms, faster than 97.48% of Python3 
class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        def swap(nums,i,j):
            temp=nums[j]
            nums[j]=nums[i]
            nums[i]=temp
        def reverse(nums,start): # python中list的内置rerverse只能反转整体nums
            i,j=start,len(nums)-1
            while(i<j):
                swap(nums,i,j)
                i+=1
                j-=1
        i,j = len(nums)-2,len(nums)-1
        while i>=0 and nums[i+1]<=nums[i]: # O(n)
            i-=1
        if i>-1:
            while i<j and nums[j]<=nums[i]: # O(n)
                j-=1
            swap(nums,i,j)
        reverse(nums,i+1) # O(n)        

32. Longest (Continuous) Valid Parentheses（Hard）

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example :
Input: "(()" , Output: 2
Input: ")()())" , Output: 4

# 感觉这个题目加上“连续”好些吧。。。做半天都理解错了
# 太难了，不会，

# Approach 3: Using Stack , T(n)=S(n)=O(n)
# Runtime: 36 ms, faster than 100.00% of Python3 ...过分了
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack=[-1]
        ans=0
        for i,item in enumerate(s):
            if item =='(':
                stack.append(i)
            else:
                stack.pop()
                if stack==[]:
                    stack.append(i)
                else:
                    ans=max(ans,i-stack[-1])
        return ans

# Approach 4: Without extra space, T(n)=O(n)， S(n)=O(1)
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        l=r=ans=0
        for i,item in enumerate(s):
            if item=='(':
                l+=1
            else:
                r+=1
            if l==r:
                ans=max(ans,2*r)
            elif r>=l:
                l=r=0
        l=r=0
        for i in range(len(s)-1,0,-1):
            if s[i]=='(':
                l+=1
            else:
                r+=1
            if l==r:
                ans=max(ans,2*l)
            elif l>=r:
                l=r=0
        return ans

33. Search in Rotated Sorted Array（Medium）

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
!!!You may assume no duplicate exists in the array.
!!!Your algorithm's runtime complexity must be in the order of O(log n).
Example:
Input: nums = [4,5,6,7,0,1,2], target = 0 , Output: 4
Input: nums = [4,5,6,7,0,1,2], target = 3 , Output: -1

# 暴力遍历，T(n)=O(n),S(n)=O(1)
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n=len(nums)
        if n==0:
            return -1
        if target==nums[0]:
            return 0
        elif n==1:
            return -1
        if target==nums[-1]:
            return n-1
        i,j=1,n-2
        if target>nums[0]:
            while i<n and nums[i-1]<nums[i]:
                if target==nums[i]:
                    return i
                i+=1
        elif target<nums[-1]:
            while j>0 and nums[j]<nums[j+1]:
                if target==nums[j]:
                    return j
                j-=1
        return -1

# 二分查找，T(n)=O(logn),S(n)=O(1)
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo,hi=0,len(nums)-1
        while lo<hi:
            mid=(lo+hi)//2
            if nums[mid]>nums[hi]:
                lo=mid+1
            else:
                hi=mid
        rot=lo # lo==hi is the index of the smallest value
        lo,hi=0,len(nums)-1
        while lo<=hi:
            mid=(lo+hi)//2
            realmid=(mid+rot)%len(nums) # ？
            if nums[realmid]==target:
                return realmid
            if nums[realmid]<target: 
                lo=mid+1
            else:
                hi=mid-1
        return -1     

34. Find First and Last Position of Element in Sorted Array（Medium）

Given an array of integers nums sorted in ascending order, find the starting >and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example:
Input: nums = [5,7,7,8,8,10], target = 8 , Output: [3,4]
Input: nums = [5,7,7,8,8,10], target = 6 , Output: [-1,-1]

# 二分查找，T(n)=O(logn),S(n)=O(1)
# Runtime: 40 ms, faster than 87.82% of Python3 o
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left=right=-1
        # find the lowwer index of target
        low,high=0,len(nums)-1
        while low <= high:
            mid = low + (high - low) // 2;
            if target <= nums[mid]:
                high = mid - 1;
            else:
                low = mid + 1;
        if low < len(nums) and nums[low] == target:
            left=low
        # find the upper index of target
        low,high=0,len(nums)-1
        while low <= high:
            mid = low + (high - low) // 2;
            if target >= nums[mid]:
                low = mid + 1;
            else:
                high = mid - 1;
        if high > -1 and nums[high] == target:
            right=high
        return [left,right]

39. Combination Sum（Medium）

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

# 回溯法啊亲！！！！！！！！总是不会用!!!
# Runtime: 56 ms, faster than 99.41% of Python3 
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(nums, target, temp, ans):
            if target == 0:
                ans += [temp]
            else:
                for num in nums:
                    if num > target: 
                        break
                    if temp!=[] and num < temp[-1]: 
                        continue
                    dfs(nums, target - num, temp + [num], ans)
        ans = []
        dfs(sorted(candidates), target, [], ans)
        return ans

42. Trapping Rain Water（Hard）

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Approach 2: Dynamic Programming

# Approach 1: Brute force , T(n)=O(n^2) , S(n)=O(1) , 超时
class Solution:
    def trap(self, height: List[int]) -> int:
        ans=0
        for i,current in enumerate(height):
            maxleft=maxright=0
            for left in height[:i+1]:
                maxleft=max(maxleft,left)
            for right in height[i:]:
                maxright=max(maxright,right)
            ans+=min(maxleft,maxright)-current
        return ans

# Approach 2: Dynamic Programming ， T(n)=S(n)=O(n)
import copy
class Solution:
    def trap(self, height: List[int]) -> int:
        ans,n=0,len(height)
        if n==0:
            return 0
        leftmax,rightmax=copy.copy(height),copy.copy(height) # 浅复制，不改变源列表
        for i in range(1,n):
            leftmax[i]=max(height[i],leftmax[i-1])
        for i in range(n-2,-1,-1):
            rightmax[i]=max(height[i],rightmax[i+1])
        for i in range(1,n-1):
            ans+=min(leftmax[i],rightmax[i])-height[i]
        return ans

# Approach 4: Using 2 pointers , T(n)=O(n) , S(n)=O(1) 
class Solution:
    def trap(self, height: List[int]) -> int:
        ans=leftmax=rightmax=0
        i,j=0,len(height)-1
        while i<j:
            if height[i]<height[j]:
                if height[i]>=leftmax:
                    leftmax=height[i]
                else:
                    ans+=leftmax-height[i]
                i+=1
            else:
                if height[j]>=rightmax:
                    rightmax=height[j]
                else:
                    ans+=rightmax-height[j]
                j-=1
        return ans