leetcode刷题记录（十八）

res = up = down = 0
        for i in range(1,len(A)):
            if down and A[i-1] < A[i] or A[i-1] == A[i]:
                up = down = 0
            up += A[i-1] < A[i]
            down += A[i-1] > A[i]
            if up and down: res = max(res,up+down+1)
        return res

B = set()
        for string in A:
            C = list(string)
            a,b = C[::2],C[1::2]
            B.add((''.join(sorted(a)),''.join(sorted(b))))
        return len(B)

s,e = 0,len(A) - 1
        while s < e:
            while A[s]%2 == 0 and s < e:
                s += 1
            while A[e]%2 == 1 and s < e:
                e -= 1
            A[s], A[e] = A[e],A[s]
        return A

n = len(s)
        cnt0 = s.count('0')
        cnt1 = 0
        res = n - cnt0
        for i in range(n):
            if s[i] == '0':
                cnt0 -= 1
            elif s[i] == '1':
                res = min(res,cnt1+cnt0)
                cnt1 += 1
        return res

n = len(T)
res = [0]*n

for i in range(n-2,-1,-1):
    k = i+1
    
    while T[i] >= T[k] and res[k]>0:
        k += res[k]
    if T[k] > T[i]:
        res[i] = k-i
return res

left = right = water = 0
        i,j = 0,len(height)-1
        while i<=j :
            left,right = max(left,height[i]),max(right,height[j])
            while i<=j and height[i] <=left <= right:
                water += left - height[i]
                i += 1
            while i<=j and height[j] <=right <= left:
                water += right - height[j]
                j -= 1
        return water

if not root:
            return 
        right = root.right
        if root.left:
            self.flatten(root.left)
            tail = root.left
            while tail.right:
                tail = tail.right
            root.left,root.right,tail.right = None, root.left,right
        
        self.flatten(right)

n = len(A)
        
        if n < 2: return True
        
        a = b = False
        for i in range(1,n):
            if A[i] > A[i-1]:
                a = True
            if A[i] < A[i-1]:
                b = True
            
            if a and b:
                return False
        return True

length = len(digits) - 1
        res = list(digits)
        while res[length] == 9:
            res[length] = 0
            length -= 1
        if (length < 0):
            res = [1] + res
        else:
            res[length] += 1
        return res

res = []
        sd = ''.join(str(i) for i in digits)
        ids = int(sd) + 1
        sd = str(ids)
        for i in sd:
            res.append(int(i))
        return res

big = set()
        for i in xrange(0,9):
            for j in xrange(0,9):
                if board[i][j] != '.':
                    cur = board[i][j]
                    if (i,cur) in big or (cur,j) in big or (i/3,j/3,cur) in big:
                        return False
                    big.add((i,cur))
                    big.add((cur,j))
                    big.add((i/3,j/3,cur))
        return True

visited = [0] * len(rooms)
        self.dfs(rooms, 0, visited)
        return sum(visited) == len(rooms)
        
    def dfs(self, rooms, index, visited):
        visited[index] = 1
        for key in rooms[index]:
            if not visited[key]:
                self.dfs(rooms, key, visited)

stack, n = [], len(pushed)
        p = 0
        for i in range(n):
            if stack and popped[i] == stack[-1]:
                stack.pop()
            else:
                while p<n and pushed[p] != popped[i]:
                    stack.append(pushed[p])
                    p += 1
                p += 1
        return not stack

if not root: return [""]
        def getDepth(root):
            if not root:
                return 0
            return 1 + max(getDepth(root.left), getDepth(root.right))
        d = getDepth(root)
        cols = 2**d -1
        self.res = [["" for i in range(cols)] for j in range(d)]
        def helper(root, d, pos):
            self.res[-d - 1][pos] = str(root.val)
            if root.left: helper(root.left, d - 1, pos - 2 ** (d - 1))
            if root.right: helper(root.right, d - 1, pos + 2 ** (d - 1))
        helper(root, d-1, 2**(d-1) -1)
        return self.res

def expressiveWords(self, S, words):
        return sum(self.check(S,W) for W in words)
    
    def check(self, S, W):
        i,j,i2,j2,n,m = 0,0,0,0,len(S),len(W)
        while i<n and j<m:
            if S[i] != W[j]: return False
            while i2<n and S[i2] == S[i]: i2+=1
            while j2<m and W[j2] == W[j]: j2+=1
            if i2-i != j2-j and i2 - i < max(3,j2-j): return False
            i,j = i2,j2
        return i==n and j==m

def helper(s):
            res = []
            for c in s:
                if c != '#':
                    res.append(c)
                else:
                    res = res[:-1]
            return res
        return helper(S) == helper(T)