leetcode刷题记录（十二）

def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        low, high = 0, len(nums)-1
        
        while low <= high:
            mid = (low+high)>>1
            if target== nums[mid]:
                return mid
            if nums[low] <= nums[mid]:
                if nums[low] <= target <= nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            else:
                if nums[mid] <= target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1
        
        return -1

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        low = 0
        high = len(nums) - 1
        while low<=high:
            mid = (low+high)//2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                high = mid - 1
            if nums[mid] < target:
                low = mid + 1
        return ((high+low)//2 + 1)

nums.append(target)
nums.sort()
return nums.index(target)

res = []
        def dfs(target, index, path):
            if target < 0:
                return
            if target == 0:
                res.append(path)
                return
            for i in range(index,len(candidates)):
                dfs(target-candidates[i],i,path+[candidates[i]])
                
        dfs(target,0,[])
        return res

cur = maxs =  -float('inf')
        for i in xrange(len(nums)):
            cur +=nums[i]
            cur = max(cur,nums[i])
            maxs = max(maxs,cur)
        return maxs

a = 0
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        self.convertBST(root.right)
        self.a += root.val
        root.val = self.a
        self.convertBST(root.left)
        return root

five, ten = 0, 0
        for i in bills:
            if i == 5:
                five+=1
            elif i == 10:
                five -=1
                ten +=1
            else:
                if ten > 0:
                    five -=1
                    ten -=1
                else:
                    five -=3
            if five < 0:
                return False
        return True

if p == None and q == None:
            return True
        if p and q:
            return (p.val==q.val) and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        else:
            return False

def findLHS(self, nums):
     """
     :type nums: List[int]
     :rtype: int
     """
     m = {}
     for i in nums:
         if i not in m:
             m[i] = 1
         else:
             m[i] += 1
     l = 0
     for i in m:
         if m.get(i+1):
             l = max(l,m[i]+m[i+1])
     return l

def findSecondMinimumValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.ans = float('inf')
        minx = root.val
        
        def dfs(node):
            if node:
                if minx<node.val<self.ans:
                    self.ans = node.val
                elif node.val == minx:
                    dfs(node.left)
                    dfs(node.right)
        dfs(root)
        return self.ans if self.ans < float('inf') else -1

max1 = big = small = nums[0]
        for i in nums[1:]:
            temp = big
            big = max(i,i*big,i*small)
            small = min(i,i*temp,i*small)
            max1 = max(max1,big)
        return max1

def maxProduct(self, A):
       B = A[::-1]
       for i in range(1, len(A)):
           A[i] *= A[i - 1] or 1
           B[i] *= B[i - 1] or 1
       return max(A + B)

def diStringMatch(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        i = 0
        j = len(S)
        res = []
        
        for x in S:
            if x=='I':
                res.append(i)
                i+=1
            else:
                res.append(j)
                j-=1
        res.append(j if S[-1]=='D' else i)
        return res