41. First Missing Positive （Hard）

Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses constant extra space.

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        
        # full [1,2,3...len]
        # missing due to -1 , gap ..
        # e.g [3,4,-1,1]
        #     [-3,4,-5,-1]
        #      
        
        length = len(nums)
        
        for i,n in enumerate(nums):
            if n<=0:
                nums[i]=length+1
                #length+1  means mums[i] invalid
                
        for i,n in enumerate(nums):
            real_n = abs(n)
            pos_n = real_n-1
            if pos_n<=length-1:
                nums[pos_n] = -abs(nums[pos_n])
        
        for i,n in enumerate(nums):
            if n>0:
                return i+1
        
        return length+1

用 -abs（val）符号来判断是否已经扫过，注意0和负数的处理。

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 can trap after raining.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

class Solution:
    def trap(self, height: List[int]) -> int:
        
        # 当入栈时候左边界确定
        # 当入的元素比栈顶大出栈，出栈右边界确定，计算，入栈当前值
        # 边界情况， 第一个元素入栈左边界为空
        # 
        stack = []
        res = 0
        for i,h in enumerate(height):
            while stack and h>height[stack[-1]]:
                #calculate
                cur = stack.pop()
                if stack:
                    left= stack[-1]  
                    right = i
                  
                    width = right-left-1  
                     
                    height_ = min(height[left],height[right])-height[cur]  
                    val = width*height_
                    res+=val
            
            stack.append(i)
        
        return res
        

虽然做出来了， 但花了很长时间。。。。。

43. Multiply Strings (Medium)

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

        # 1 2 3 j
        # 4 5 6 i
        #-------
        # 7 3 8
     #  6 1 5
    # 4 9 2
    #  5 6 0 8 8
   
## answer
class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        res = [0]*(len(num1)+len(num2))
        for i in range(len(num1)-1,-1,-1):
            carry = 0
            for j in range(len(num2)-1,-1,-1):
                temp = int(num1[i])*int(num2[j]) + carry
                carry = (res[i+j+1] + temp) //10
                res[i+j+1] = (res[i+j+1] + temp) % 10
            res[i] += carry
        return ''.join(list(map(str,res))).lstrip('0') if ''.join(list(map(str,res))).lstrip('0') else "0"

成功做出来，但是得很细心。
答案写的很精简，思路一样
第二次做不会的。。。。醉了

44. Wildcard Matching （Hard）

# 遇到 time limit exceeded 问题
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        
        # ? any single
        # * any sequence
        
        if not p:
            return not s
        if not s:
            if len(set(p))==1 and p[0]=='*':
                return True
            return False
#       first block  way of writing           
        if p[0] in {s[0],'?'}:
            #match single
            return self.isMatch(s[1:],p[1:])
        elif p[0]=='*':
            #match sequence     match 0 s,      match 1 s,p not change
            return self.isMatch(s,p[1:]) or self.isMatch(s[1:],p)
        elif p[0]!=s[0]:
            return False
        
#         second block way of writting   using var firstmatch     
#         firstmatch=  p[0] in {'?',s[0]}              
#         if p[0]=='*':
#             if len(p)==1:
#                 return True
#             else:
#                 #                 0 s                     1 s
#                 return self.isMatch(s,p[1:]) or  self.isMatch(s[1:],p)
#         else:
#             return firstmatch and self.isMatch(s[1:],p[1:])
    
            
''' time limit exceeded   1) remove dup*  2) using memorization of (s,p) results   '''  
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        def removedup(p):
            res=[]
            pre=None
            for e in p:
                if pre=='*' and e=='*':
                    continue
                res.append(e)
                pre=e
            return "".join(res)
                
        dic=dict()
        
        def M(s,p):
            if (s,p) in dic: return dic[(s,p)]
            if not p: return not s
            if not s: 
                if p=='*':
                    dic[(s,p)]=True
                    return True
                else:
                    dic[(s,p)]=False
                    return False
            firstmatch= p[0] in {s[0],'?'}
            
            if p[0]=='*':
                res=M(s,p[1:]) or M(s[1:],p)
                dic[(s,p)]=res
                return res
            else:
                res=firstmatch and M(s[1:],p[1:])
                dic[(s,p)]=res
                return res
        
        return M(s,removedup(p))

还有dynamic programming 解法， 比较不熟悉， 暂时放弃。

45. Jump Game II （Medium）

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
You can assume that you can always reach the last index.

class Solution:
    def jump(self, nums: List[int]) -> int:
        # i,
        # i+nums[i] is max can just at this step
        # search prev to i+nums[i], which can just further
        if len(nums)==1: return 0
        
        pos = 0 
        step = 0
        while pos<len(nums)-1:
            step+=1
            move_to = None
            max_can_reach = -float('inf')
            for i in range(pos,pos+nums[pos]+1):
                if i>=len(nums)-1: return step
                reach = i+nums[i]
                if reach> max_can_reach:
                    max_can_reach = reach
                    move_to = i
            pos = move_to
               
        return step

#anser way of writing
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n < 2:
            return 0 
        
        # max position one could reach 
        # starting from index <= i 
        right = nums[0]
        # max number of steps one could do
        # inside this jump
        cur = nums[0]
        
        jumps = 1
        for i in range(1, n):
            # if to reach this point 
            # one needs one more jump
            if cur < i:
                jumps += 1
                cur = right
            right = max(right, nums[i] + i)
                
        return jumps


class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums)==1: return 0

        cur = 0
        maxright = nums[0]
        jump = 0
        for i in range(1,len(nums)):
            if cur<i:
                jump+=1
                cur=maxright
            maxright = max(maxright, nums[i]+i)
            
        
        return jump

费了点力气写出来了，思路， 如果pos不到最后一位，需要移动，step+=1， 确定移动到哪里，移动到可以使下次移动更远的index位置。 从【pos，pos+nums【pos】】中选出能达到最远的index，那个index就当前步会移动的地方。 注意再扫能移动到最远的地方时候， 如果【pos，pos+nums【pos】】已经大于等于了最后的位置，再当前步就可提前结束了，return step就行。
答案直接扫从1到LEN（nums）的位置，right能到位置为 right = max(right, nums[i] + i)， 如果在right更新前， cur小于i， 则需要jump，jump后 cur=right。

46. Permutations （Medium）

Blue because can not write the switch postion solution.
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res =[]
        def bt(tmp):
            if len(tmp)==len(nums):
                res.append(tmp[:])
            for n in nums:
                if n not in tmp:   
                    tmp.append(n)
                    bt(tmp)
                    tmp.pop()
        
        bt([])
        return res

# aswer way of writing 用了swap 比较省检查是否在tmp那步。
class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(first = 0):
            # if all integers are used up
            if first == n:  
                output.append(nums[:])
            for i in range(first, n):
                # place i-th integer first 
                # in the current permutation
                nums[first], nums[i] = nums[i], nums[first]
                # use next integers to complete the permutations
                backtrack(first + 1)
                # backtrack
                nums[first], nums[i] = nums[i], nums[first]
        
        n = len(nums)
        output = []
        backtrack()
        return output

backtracking 应用, swap方法很巧妙。

47. Permutations II （Medium)

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        visited = [False]*len(nums)
        
        res = []
        def bt(temp,visited):
            if len(temp)==len(nums):
                res.append(temp[:])
            
            else:
                for i in range(len(nums)):
                    
                    if visited[i] or (i>0 and nums[i]==nums[i-1] and not visited[i-1]) : continue 
         
                    visited[i]=True
                    temp.append(nums[i])
                    bt(temp,visited[:])
                    temp.pop()
                    visited[i]=False
                     
        
        nums.sort()
        bt([],visited)
        return res

试着用 Permutations swap方法+if条件去重，失败， 没想到得开一个visited来记录是否访问过。 如果访问过或者提前访问（i-1 没访问但开始访问i）则continue。

#无奈做法用set去重
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        nums.sort()
        n=len(nums)
        res = []
        def bt(tmp,first):
            if first==n:
                res.append(tmp[:])
                return
            
            for j in range(first,n):
                if j-1>=first and nums[j] == nums[j-1]: 
                    continue
                tmp[j],tmp[first] = tmp[first],tmp[j]
                bt(tmp,first+1)
                tmp[j],tmp[first] = tmp[first],tmp[j]
        
        bt(nums,0)
        return list(set( [tuple(e) for e in res]))

48. Rotate Image （Medium）

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        
        n = len(matrix)
        
        for level in range(n//2):
            len_level = n-level*2
            
            for i in range(len_level-1):
                lefttop = matrix[level][level+i]
                righttop =matrix[level+i][level+len_level-1]
                rightbot = matrix[n-level-1][level+len_level-i-1]
                leftbot = matrix[level+len_level-i-1][level]
                
                print(lefttop,righttop,rightbot,leftbot)
                
                matrix[level+i][level+len_level-1] = lefttop
                matrix[n-level-1][level+len_level-i-1] = righttop
                matrix[level+len_level-i-1][level] = rightbot
                matrix[level][level+i] = leftbot

49. Group Anagrams (Medium)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        if len(strs)==1: return [strs]
        res = []
        dic = dict()
        for str in strs:
            key = ''.join(sorted([e for e in str]))
            if key not in dic:
                          dic[key] = []
            dic[key].append(str)
        for k,v in dic.items():
                          res.append(v)
        return res

50. Pow(x, n) Medium

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n==0: return 1.0
        if n<0:
            x=1.0/x
            n=-n
        
        if n%2==1:
            return x*self.myPow(x,n//2)**2
        else:
            return self.myPow(x,n//2)**2