leetcode刷题记录（十六）

cur, res = float('-inf'), 0
        for p in sorted(pairs, key = lambda x:x[1]) : 
            if cur < p[0] :
                cur, res = p[1], res+1
        return res

d = {}
        for h,k in people:
            if h not in d:
                d[h] = [[h,k]]
            else:
                d[h].append([h,k])
        
        res =[]
        for h in sorted(d.keys(), reverse = True):
            group = sorted(d[h])
            if not res:
                res += group
            else:
                for h,k in group:
                    res.insert(k,[h,k])
        return res

if not root: return True
        stack = [(root.left,root.right)]
        while stack:
            cur = stack.pop()
            l,r = cur[0],cur[1]
            if not l and not r:
                continue
            if not l and r or not r and l or l.val != r.val:
                return False
            stack.append((l.left,r.right))
            stack.append((l.right,r.left))
        return True

def robs(nums):
            a,b = 0,0
            for i in nums:
                a,b = b, max(a+i,b)
            return b
        
        return max(robs(nums[len(nums)!=1:]),robs(nums[:-1]))

def rob(self, root):
        return self.robs(root)[1]
    
    def robs(self, node):
        if node is None:
            return (0,0)
        l = self.robs(node.left)
        r = self.robs(node.right)
        return (l[1]+r[1], max(l[1]+r[1],l[0]+r[0]+node.val))

ans,level = [],[root]
        while root and level:
            ans.append([node.val for node in level])
            level = [kid for n in level for kid in (n.left, n.right) if kid]
        return ans

if not root:
            return False
        bfs,s=[root],set()
        for i in bfs:
            if k-i.val in s: return True
            s.add(i.val)
            if i.left: bfs.append(i.left)
            if i.right: bfs.append(i.right)
        return False

if not nums: return 0
        dic = {nums[0]:1,-nums[0]:1} if nums[0] != 0 else {0:2}
        for i in range(1,len(nums)):
            tdic = {}
            for d in dic:
                tdic[d+nums[i]] = tdic.get(d+nums[i],0) + dic.get(d,0)
                tdic[d - nums[i]] = tdic.get(d - nums[i], 0) + dic.get(d, 0)
            dic = tdic
        return dic.get(S,0)

if len(prices)<2:
            return 0
        sell,buy,prev_sell,prev_buy=0,-prices[0],0,0
        for price in prices:
            prev_buy=buy
            buy=max(prev_sell-price,prev_buy)
            prev_sell=sell
            sell=max(prev_buy+price,prev_sell)
        return sell

i,j = 0, len(height)-1
        water = 0
        while i<j:
            water = max(water,(j-i)*min(height[i],height[j]))
            if height[i] < height[j]:
                i+=1
            else:
                j-=1
        return water

p1,p2=0,len(nums)-1
       p=0
       while p<=p2:
           if nums[p]<1:
               nums[p],nums[p1]=nums[p1],nums[p]
               p1+=1
               p+=1
           elif nums[p]>1:
               nums[p],nums[p2]=nums[p2],nums[p]
               p2-=1
           else:
               p+=1

if not matrix: return 0
        m,n = len(matrix), len(matrix[0])
        dp = [[0 if matrix[i][j] == '0' else 1 for j in range(0,n)] for i in range(0,m)]
        for i in range(1,m):
            for j in range(1,n):
                if matrix[i][j]=='1':
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
                else:
                    dp[i][j] = 0
        res = max(max(row) for row in dp)
        return res**2

dic = {0:1}
        res = presum = 0
        for num in nums:
            presum += num
            res += dic.get(presum - k,0)
            dic[presum] = dic.get(presum,0) + 1
        return res

res = [[]]
for num in sorted(nums):
    res+=[item+[num] for item in res]
return res

def isValidBST(self, root,floor=float('-inf'), ceiling=float('inf')):
        if not root:
            return True
        if root.val <= floor or root.val >= ceiling:
            return False
        return self.isValidBST(root.left, floor, root.val) and self.isValidBST(root.right, root.val, ceiling)