感恩节假期中断了刷题，沉迷于半小时漫画系列... 补上月25进度。

221. Maximal Square （Medium)

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        rows=len(matrix)
        cols=len(matrix[0])
        maxqlen=0
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j]=='1':
                    sqlen=1
                    flag=True
                    while sqlen+i<rows and sqlen+j< cols and flag:
                        for k in range(j,sqlen+j+1):
                            if matrix[i+sqlen][k]=='0':
                                flag=False
                                break
                        for k in range(i,i+sqlen+1):
                            if matrix[k][j+sqlen]=='0':
                                flag=False
                                break
                        if flag:
                            sqlen+=1
                    
                    if maxqlen<sqlen:
                        maxqlen=sqlen
                        
                        
        return maxqlen**2

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # dp[i][j]  size of box which bottom right in pos[i][j]
        # if matrix[i][j]==1
        #    dp[i][j]=   min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1 
        
        m = len(matrix)
        n = len(matrix[0])
        dp = [[0]*(n+1) for _ in range(m+1)]
        res=0
        for i in range(1,m+1):
            for j in range(1,n+1):
                if matrix[i-1][j-1]=='1':
                    dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1
                    res=max(res,dp[i][j])
        return res**2

试着用cumsum去解但失败了， 方法1，暴力解。 每次发现是“1”就以它作为正方形左上角起始点， 检查 row: i，i+sqlen col: j, j+sqlen 是否有‘0’.
方法2：dp： dp【i】【j】保存右下角位置在i，j的盒子大小。

222. Count Complete Tree Nodes （Medium）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        if not root.right:
            return 1+ self.countNodes(root.left)
        else:
            return  self.countNodes(root.left)+self.countNodes(root.right)+1


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        
        def depth(node):
            d=0
            while node.left:
                node=node.left
                d+=1
            return d
        
        def exists(idx,d,node):
            left=0
            right=2**d-1
            for _ in range(d):
                pivot = (left+right)//2
                if idx<=pivot:
                    node=node.left
                    right=pivot
                else:
                    node=node.right
                    left=pivot +1
            return node is not None
        
        if not root: return 0
        d = depth(root)
        if d==0: return 1
        
        l=1
        r=2**d-1
        while l<=r:
            mid = (l+r)//2
            if exists(mid,d,root):
                l=mid+1
            else:
                r=mid-1
        
        return (2**d-1) +l 
        

给出了个O（n）解法，但题目要求小于O(n)...
思路： 完全二叉树，第0层2^{0个node，第一层，2}1个node，第n层2^n个node，所以假设这个树深度为d=n， 不包含最后一层2⁰⁺²1+..+2^(n-1)=2n - 1 的所有node总和为2^d-1 ,问题转化成求最后一层有多少node。 范围在1~2^n. 因为d=n所以肯定有第一个node。 可以用binary search 求。

223. Rectangle Area （Medium）

class Solution:
    def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
        
        # intersect of 1d line
        
        def intersect(a1,a2,b1,b2):
            if a1>b1:
                a1,a2,b1,b2=b1,b2,a1,a2
            
            #print(a1,a2,b1,b2)
            #case 1  --
            #            --
            if a2<b1:
                return 0
            
            #case 2   a1---a2
            #            b1---b2
            if b1<=a2 and a2<=b2:
                return a2-b1
            # case 3  a1------a2
            #            b1-b2
            if b1<a2 and b2<a2:
                return b2-b1
            
            return 'ERROR'
        
        width = intersect(ax1,ax2,bx1,bx2)
        height = intersect(by1,by2,ay1,ay2)
        print(width,height)
        return (ay2-ay1)*(ax2-ax1)+ (by2-by1)*(bx2-bx1)    -width*height

224. Basic Calculator (Hard)

#通解
class Solution:
    def calculate(self, s: str) -> int:
        
        # 转换为 后缀表达式
        # 运算符优先级
        prec = {}
        prec["*"] = 3
        prec["/"] = 3
        prec["+"] = 2
        prec["-"] = 2
        prec["("] = 1

        res = []
        stack = []
        i = 0
        while i < len(s):
            # 数字 直接 接到后缀表达式上
            if s[i] == " ":
                i += 1
                
            elif s[i].isdigit():
                temp = ""
                while i < len(s) and s[i].isdigit():
                    temp += s[i]
                    i += 1
                res.append(temp)

            # 左括号直接入栈
            elif s[i] == "(":
                stack.append(s[i])
                i += 1

            # 右括号，开始弹栈，直达遇到左括号 左括号出栈 但不输出
            elif s[i] == ")":
                while stack and stack[-1] != "(":
                    res.append(stack.pop())
                stack.pop() # 左括号出战， 但是不输出
                i += 1

            # 遇到运算符
            elif s[i] in ["+", "-", "*", "/"]:
                #  对 "-2 + 2" 或者 "1-(-2)" 进行特殊处理
                if s[i] == "-" and (i == 0 or s[i-1] == "(" ):
                    res.append('0')
                # 只要栈顶符号不低于当前符号，就一直输出。最后把当前符号入栈
                while stack and prec[s[i]]<=prec[stack[-1]]:
                    res.append(stack.pop())
                stack.append(s[i])
                i += 1
        
        # 最后把栈里面的元素均 放到后缀表达式后面
        while stack:
            res.append(stack.pop())


        # 计算后缀表达式
        stack = []
        
        for char in res:
            if char.isdigit():
                stack.append(int(char))
            else:
                x = stack.pop()
                y = stack.pop() 
                if char == "+":
                    stack.append(x + y)
                elif char == "-":
                    stack.append(y-x)
                elif char == "*":
                    stack.append(y*x)
                elif char == "/":
                    stack.append(x/y)

        return stack.pop()

" 2-1 + 2 " 直接用stack解出现-1时候符号和1是合体的，所以换思路把表达式变成前缀/后坠表达。 又遇到后缀表达如何去括号问题。
1 + (( 2 + 3)* 4 ) – 5 方法： 当读到数时，立即输出， 若读到操作符，判断符号与栈顶符号的优先级，若该符号优先级高于栈顶元素，则将该操作符入栈，否则就依次把栈中运算符弹出并加到后缀表达式尾端，但又遇到 "1-(-2)" 无法pass。 同理 "- (3 - (- (4 + 5) ) )" 无法pass。 负号不作为减法，作为符号。 需要特殊处理： 方法：

if e == "-" and (i == 0 or s[i-1] == "(" ):
    s_res.append(0)

答案很简单，问题根源在-号不能互相换 比如(A-B)+C != A-(B+C) , 所以把-看作数字的符号。

class Solution:
    def calculate(self, s: str) -> int:

        stack = []
        operand = 0
        res = 0 # For the on-going result
        sign = 1 # 1 means positive, -1 means negative  

        for ch in s:
            if ch.isdigit():
                # Forming operand, since it could be more than one digit
                operand = (operand * 10) + int(ch)

            elif ch == '+':
                # Evaluate the expression to the left,
                # with result, sign, operand
                res += sign * operand

                # Save the recently encountered '+' sign
                sign = 1
                # Reset operand
                operand = 0

            elif ch == '-':

                res += sign * operand
                sign = -1
                operand = 0

            elif ch == '(':

                # Push the result and sign on to the stack, for later
                # We push the result first, then sign
                stack.append(res)
                stack.append(sign)

                # Reset operand and result, as if new evaluation begins for the new sub-expression
                sign = 1
                res = 0

            elif ch == ')':

                # Evaluate the expression to the left
                # with result, sign and operand
                res += sign * operand

                # ')' marks end of expression within a set of parenthesis
                # Its result is multiplied with sign on top of stack
                # as stack.pop() is the sign before the parenthesis
                res *= stack.pop() # stack pop 1, sign

                # Then add to the next operand on the top.
                # as stack.pop() is the result calculated before this parenthesis
                # (operand on stack) + (sign on stack * (result from parenthesis))
                res += stack.pop() # stack pop 2, operand

                # Reset the operand
                operand = 0

        return res + sign * operand

225. Implement Stack using Queues (Easy)

class MyStack(object):
    def __init__(self):
        self._queue = collections.deque()

    def push(self, x):
        q = self._queue
        q.append(x)
        for _ in range(len(q) - 1):
            q.append(q.popleft())
 
    def pop(self):
        return self._queue.popleft()

    def top(self):
        return self._queue[0]
    
    def empty(self):
        return not len(self._queue)

三种方法

226. Invert Binary Tree （Easy）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root: return root
        root.left,root.right = root.right,root.left
        root.left = self.invertTree(root.left)
        root.right=self.invertTree(root.right)
        return root

227. Basic Calculator II (Medium)

class Solution:
    def calculate(self, s: str) -> int:
        
        #convert to 后缀表达
        priority = {'+':1,'-':1,'*':2,'/':2,'(':0}
        res = [] #保存后缀表达式
        stack=[] #保存符号
        i=0
        while i<len(s):
            ch=s[i]
            if ch.isdigit():
                tmp=ch
                while i+1<len(s) and s[i+1].isdigit():
                    tmp+=s[i+1]
                    i+=1
                res.append(int(tmp))
            
            elif ch=='(':
                stack.append(ch)
            elif ch==')':
                while stack and stack[-1] != "(":
                    res.append(stack.pop())
                stack.pop() 
            elif ch in  ["+", "-", "*", "/"]:
                 if s[i]=='-' and (i==0 or s[i-1]=='('):
                    res.append(0)
                while stack and priority[ch] <= priority[stack[-1]]:
                    res.append(stack.pop())

                stack.append(ch)
            
            i+=1
                
        while stack:
            res.append(stack.pop())
        
        # 计算后缀表达式
        stack = []
        
        for char in res:
            if char not in  ["+", "-", "*", "/"]:
                #char is number
                stack.append(char)
            else:
                x = stack.pop()
                y = stack.pop() 
                if char == "+":
                    stack.append(x + y)
                elif char == "-":
                    stack.append(y-x)
                elif char == "*":
                    stack.append(y*x)
                elif char == "/":
                    stack.append(y//x)

        return stack.pop()


#ANSWER
class Solution:
    def calculate(self, s: str) -> int:
        
        if not s: return 0
        s = s + '+'
        stack = []
        val = 0
        op = '+'
        for n in s:
            if n==' ':  continue
            
            if n.isdigit():
                val=val*10+int(n)
            else:
                if op=='+':
                    stack.append(val)
                elif op=='-':
                    stack.append(-val)
                elif op=='*':
                    stack.append(stack.pop()*val)
                elif op=='/':
                    stack.append(int(stack.pop()/val))

                op = n
                val = 0 
            
        print(stack)
        return sum(stack)

直接上通杀法。转成后缀表达然后求结果。
为了能延时evaluate，所以先给op一个default值+， 然后当遇到下一个符号时候，再去eval之前的op结果，遇到+-要push到stack，遇到*/要从stack取值做计算， 要注意因为是遇到符号才会触发计算，所以s = s+‘+’ 来做最后一位的触发计算。

228. Summary Ranges （Easy）

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        # [0]
        # [0,1]
        # [0,2]
        # [0-2,4]
        # [0-2,4,5]
        
        res = []
        stack=[]
        for n in nums:
            if not stack:
                stack.append(n)
            elif len(stack)==1:
                if n==stack[-1]+1:
                    stack.append(n)
                else:
                    res.append(str(stack[-1]))
                    stack=[n]
            else:
                if n==stack[-1]+1:
                    stack[-1]=n
                else:
                    res.append(str(stack[0])+'->'+str(stack[1]))
                    stack=[n]
 
        if len(stack)==1:
            res.append(str(stack[0]))
        elif len(stack)==2:
            res.append(str(stack[0])+'->'+str(stack[1]))
        
        return res
#answer way of writting
class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        res = []
        i=0
        for j in range(len(nums)):
            if j+1<len(nums) and nums[j+1]==nums[j]+1:
                continue
            if i==j:
                res.append(str(nums[i]))
            else:
                res.append(str(nums[i])+'->'+str(nums[j]))
            i=j+1
        return res

答案更简单

229. Majority Element II (Medium)

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        
        maj1=nums[0]
        maj2=nums[0]
        c1=0
        c2=0

        for n in nums:
            if n==maj1:
                c1+=1
            elif n==maj2:
                c2+=1
            elif c1==0:
                c1=1
                maj1=n
            elif c2==0:
                c2=1
                maj2=n
            else:
                c1-=1
                c2-=1
        #recalce make sure        
        c1=c2=0
        for n in nums:
            if n==maj1:c1+=1
            if n==maj2:c2+=1
        res=[]
        if c1>len(nums)//3:
            res.append(maj1)
        if c2>len(nums)//3 and maj1!=maj2:
            res.append(maj2)
        return res

经典算法，在做majorelement 1时候写过，需要记住。

230. Kth Smallest Element in a BST （Medium）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        ind=0
        stack=[]
        while root or stack:
            while root:
                stack.append(root)
                root=root.left
            
            node=stack.pop()
            ind+=1
            if ind==k:
                return node.val
            
            root=node.right