31. Next Permutation （Medium）

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).
The replacement must be in place and use only constant extra memory.

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        #   A B
        # 2 4 5 3 1
        # 2 5 4 3 1
        # 2 5 1 3 4

        # 5 4 3 2 1

        def rev(i,j):
            while i<j:
                nums[i],nums[j] = nums[j],nums[i]
                i+=1
                j-=1
        A = None
        for i in reversed(range(len(nums))):
            if i-1>=0 and nums[i-1] <nums[i]:
                A = i-1
                break
        if A is None: 
            rev(0,len(nums)-1)
            return
        B = None
        for j in range(A,len(nums)):
            if nums[A]<nums[j]:
                B = j
        nums[A],nums[B] = nums[B],nums[A]
        rev(A+1,len(nums)-1)


class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        #                     peak  <--      
        # 9  6  8   7  1  |2|  5  4  3 1
        #                     find first greater than 2 swap <-
        #                 |3|  5  4  2 1
        #                     rest just rev
        #                  3   1  4  2 5
        
        def rev(nums):
            l=0
            r=len(nums)-1
            while l<r:
                nums[l],nums[r]=nums[r],nums[l]
                l+=1
                r-=1
        
        l = len(nums)
        pos_a = None
        pos_b = None
        for i in range(l-1,-1,-1):
            if i-1>=0 and nums[i-1] < nums[i]:
                a = nums[i-1]
                pos_a = i-1
                break
         
        if  pos_a is None: 
            rev(nums)  
        else:
            for i in range(l-1,pos_a,-1):
                if nums[i]>nums[pos_a]:
                    pos_b = i
                    break
            print(pos_a,pos_b)
            nums[pos_a],nums[pos_b] = nums[pos_b],nums[pos_a]
            nums[pos_a+1:] =  nums[pos_a+1:][::-1 ]

思路， 从最后一位开始，找到第一次drop位置标记为pos_a, 再从后向前找到第一个比num【pos_a】大的位置计为pos_b, swap value of pos_a, pos_b, 对于pos_a之后的，rev。
what if 是 下一个更小的位置？？ drop=>increase, 大=>小

32. Longest Valid Parentheses （Hard）

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        
        #"))))())()()(()"
        stack=[-1]
        res=0
        for i,n in enumerate(s):
            if n=='(':
                stack.append(i)
            else:
                #n==')'
                if stack:
                    stack.pop()
                
                if stack:
                    res=max(res,i-stack[-1])
                else:
                    stack.append(i)
        
        return res

题目有坑，如果直接用判断是否是valid parentheses方法计算长度，就掉坑里了。。。
方法依旧是用stack， 但stack里面存的是（括号的位置，如果是（入栈， 否则出栈，出栈时候因为是），所以开始计算长度，“当前位置-stack【-1】” stack【-1】是已经pop后的位置了，所以是起始点，如果栈pop后为空，继续入栈，此为新起始点。（其实为起始点的前一位，算长度避免 j-i+1，直接j-i）

33. Search in Rotated Sorted Array (Medium)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)-1

        while l<=r:
            m = (l+r)//2
            if target ==nums[m]: return m

            if nums[l] <=nums[m]:
                #left increase
                if nums[l] <=target and target <=nums[m]:
                    r=m-1
                else:
                    l=m+1
            else:
                #right increase
                if nums[m]<=target and target<=nums[r]:
                    l=m+1
                else:
                    r=m-1

        return -1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)-1
        
        while l<=r:
            m = (l+r)//2
            if nums[m] == target: return m
            
            #@stuck here
            if nums[l] > nums[m]:
                #increasing at right
                if nums[m] <= target and target<=nums[r]:
                    l = m+1
                else:
                    r = m-1
            
            else:
                #increasing at left
                if nums[l] <= target and target<=nums[m]:
                    r = m-1
                else:
                    l = m+1
        return -1

这个必须会的题目，binary search 判断单增区间用mid 和 left 比 （mid he right比是错误的）。根据单调区间缩小搜索范围。 若先判断左丹增后判断右丹增，则需要nums[left]<=nums[mid]

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

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        
        def bsl(nums,target):
            l=0
            r=len(nums)-1
            while l<=r:
                m = (l+r)//2
                
                if nums[m] >= target:
                    r = m-1
                else:
                    l = m+1
            return l
        
        def bsr(nums,target):
            l=0
            r=len(nums)-1
            while l<=r:
                m = (l+r)//2
                
                if nums[m] <= target:
                    l = m+1
                else:
                    r = m-1
            return r
        
        return [bsl(nums,target),bsr(nums,target)] if bsl(nums,target) <= bsr(nums,target) else [-1,-1]

35. Search Insert Position (Easy)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        
        l=0
        r=len(nums)-1
        
        while l<=r:
            m=(l+r)//2
            if nums[m]==target:
                return m
            elif nums[m]<target:
                l=m+1
            else:
                r=m-1
        return l

target 大于 mid值 说明是插入位置，l位置刚好更新为插入位置， 返回left。

36. Valid Sudoku （Medium）

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for row in board:
            row = [e for e in row if e!='.']
            if len(set(row))!=len(row):
                return False
        
        for col in zip(*board):
            print(col)
            col = [e for e in col if e!='.']
            if len(set(col))!=len(col):
                return False
        dic={k:[] for k in range(9)}    
        for i in range(9):
            for j in range(9):
                ind = (i//3)*3 + j//3
                dic[ind].append(board[i][j])
        
        for k,v in dic.items():
            row = [e for e in v if e!='.']
            if len(set(row))!=len(row):
                return False        
        return True

box index boxid = (i//3)*3+j//3 or key=(i//3,j//3)

37. Sudoku Solver (hard)

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        row  = {i:set() for i in range(9)}
        col = {j:set() for j in range(9)}
        box = {boxid:set() for boxid in range(9)}
        
        def canplace(num,i,j):
            boxid = (i//3)*3+j//3
            if (num in row[i]) or (num in col[j]) or (num in box[boxid]):
                return False
            return True
        
        def place(num,i,j):
            boxid = (i//3)*3+j//3
            board[i][j] = num
            row[i].add(num)
            col[j].add(num)
            box[boxid].add(num)
        
        def remove(num,i,j):
            board[i][j] = '.'
            boxid = (i//3)*3+j//3
            row[i].remove(num)
            col[j].remove(num)
            box[boxid].remove(num)
        
        solved = False
        def placenext(i,j):
            if i==8 and j==8:
                nonlocal solved
                solved=True
            
            elif j==8:
                bt(i+1,0)
            else:
                bt(i,j+1)
        
        #@stuck place step ignored
        for i in range(9):
            for j in range(9):
                if board[i][j]!='.':
                    place(board[i][j],i,j)
                    
        
        def bt(i,j):
            
            if board[i][j]=='.':
                for d in range(1,10):
                    d = str(d)
                    if canplace(d,i,j):
                        place(d,i,j)
                        placenext(i,j)

                        if not solved:
                            remove(d,i,j)
            else:
                placenext(i,j)
                            
        
        bt(0,0)

主要function， canplace、 remove、 placenext。 backtracking逻辑，如果要填， scan1到9，如果能填入，填入，填入下一个， 如果没有solve，去除填入值。 如果当前空不填，填入下一个。
思路简单，但构建出思路难。

38. Count and Say （Medium）

class Solution:
    def countAndSay(self, n: int) -> str:
        
        if n==1: return '1'
        prev = '1'
        
        for i in range(n-1):
            cur = ''    
            pre_char = None
            c=0
            #print('in',prev)
            while prev:
                cur_char = prev[0]
                if pre_char and cur_char!=pre_char:
                    #output
                    cur+= str(c)+pre_char
                    c=1
                else:
                    c+=1
                
                pre_char = cur_char
                prev=prev[1:]
            if c:
                cur+= str(c)+pre_char
            #print('out',cur)
            prev=cur
        
        return prev
                

not hard,but need to pay attention to details.

39. Combination Sum (Medium)

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        res = []
        def bt(tmp,val,start):
            if val<0: return
            if val==0:
                res.append(tmp[:])
                
            for i in range(start,len(candidates)):
                tmp.append(candidates[i])
                bt(tmp,val-candidates[i],i)
                tmp.pop()
                
        bt([],target,0)
        return res

典型的backtracking，可以重复利用元素，所以内循环中 start=i

40. Combination Sum II （Medium）

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        def bt(tmp,val,start):
            if val<0:
                return
            if val==0:
                res.append(tmp[:])
            
            for i in range(start,len(candidates)):
                if i>start and candidates[i]==candidates[i-1]:continue
                tmp.append(candidates[i])
                bt(tmp,val-candidates[i],i+1)
                tmp.pop()
        bt([],target,0)
        return res

注意去重复，也许得写个backtracking模板总结。