studyleetcode

#leetcode 345
class Solution345:
    def reverseVowels(self, s: str) -> str:
        length=len(s)
        low,high=0,length-1
        s=list(s)
        res =['a','e','i','o','u','A','E','I','O','U']
        while low<=high:
            while low<high and s[high] not in res:
                high-=1
            while low<high and s[low] not in res:
                low+=1
            s[low],s[high]=s[high],s[low]
            low+=1
            high-=1
        return "".join(s)


#leetcode 524
class Solution524:
    def findLongestWord(self, s: str, d: List[str]) -> str:
        d.sort(key=lambda x:[-len(x),x])
        for word in d:
            a=0
            b=0
            while a<len(s) and b<len(word):
                if s[a]==word[b]:
                    a+=1
                    b+=1
                else:
                    a+=1
            if len(word) ==b:
                return word
        return ''
        
        #leetcode 141
class Solution141:
    def hasCycle(self, head: ListNode) -> bool:
        if not head:
            return head
        slow=head
        quick=head
        while quick and slow:
            slow=slow.next
            if quick.next:
                quick=quick.next.next
            else:
                return False
            if quick is slow:
                return True
        return False

#leetcode 315
class Solution315:
    def countSmaller(self, nums: List[int]) -> List[int]:
        sortns=[]
        res=[]
        for n in reversed(nums):
            idx=bisect.bisect_left(sortns,n)
            res.append(idx)
            sortns.insert(idx,n)
        return res[::-1]


#leetcode 120
class Solution120:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        for r in range(len(triangle)-2,-1,-1):
            for c in range(len(triangle[r])):
                triangle[r][c]+=min(triangle[r+1][c:c+2])
        return triangle[0][0]


#leetcode 96
class Solution96:
    def numTrees(self, n: int) -> int:
        s=[0]*(n+1)
        s[0]=1

        for i in range(1,n+1):
            b=i-1
            for j in range(i//2):
                s[i]+=s[j]*s[b-j]
            s[i]*=2

            if i%2==1:
                s[i]+=s[i//2]**2
        return s[-1]


#leetcode 35
class Solution35:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left,right =0,len(nums)
        while left<right:
            mid=left+(right-left)//2
            if nums[mid]<target:
                left=mid+1
            else:
                right=mid
        return left


#leetcode 312
class Solution312:
    def maxCoins(self, nums: List[int]) -> int:
        nums.insert(0,1)
        nums.insert(len(nums),1)

        store=[[0]*(len(nums)) for i in range(len(nums))]

        def range_best(i,j):
            m=0
            for k in range(i+1,j):
                left=store[i][k]
                right=store[k][j]
                a=left+nums[i]*nums[k]*nums[j]+right
                if a>m:
                    m=a
            store[i][j]=m

        for n in range(2,len(nums)):
            for i in range(0,len(nums)-n):
                range_best(i,i+n)
        return store[0][len(nums)-1]



#leetcode 97
class Solution97:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m,n=len(s1),len(s2)
        if m+n!=len(s3):
            return False
        dp=[[False]*(n+1) for _ in range(m+1)]
        dp[0][0]=True
        for i in range(1,m+1):
            dp[i][0]=dp[i-1][0] and (s3[i-1]==s1[i-1])
        for i in range(1,n+1):
            dp[0][i]=dp[0][i-1] and (s3[i-1]==s2[i-1])

        for i in range(1,m+1):
            for j in range(1,n+1):
                dp[i][j]=(dp[i-1][j] and (s3[i+j-1]== s1[i-1])) or (dp[i][j-1] and (s3[i+j-1]==s2[j-1]))
        return dp[-1][-1]

#leetcode 剑指offer11
class Solutionoffer11:
    def minArray(self, numbers: List[int]) -> int:
        i,j=0,len(numbers)-1
        while i<j:
            m=(i+j)//2
            if numbers[m]>numbers[j]:i=m+1
            elif numbers[m]<numbers[j]:j=m
            else:i-=1
        return numbers[i]


#leetcode64
class Solution64:
    def minPathSum(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i==j==0:continue
                elif i==0:grid[i][j]=grid[i][j-1]+grid[i][j]
                elif j==0:grid[i][j]=grid[i-1][j]+grid[i][j]
                else:grid[i][j]=min(grid[i-1][j],grid[i][j-1])+grid[i][j]
        return grid[-1][-1]


#leetcode 95
# 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 Solution95:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n==0:
            return []
        dct={}

        def left_right(left:int,right:int)->List[TreeNode]:
            if left>right:
                return [None]
            if (left,right) in dct:
                return dct[(left,right)]
            ret=[]

            for i in range(left,right+1):
                left_lst=left_right(left,i-1)
                right_lst=left_right(i+1,right)
                for L in left_lst:
                    for R in right_lst:
                        app_Tree=TreeNode(i)
                        app_Tree.left=L
                        app_Tree.right=R
                        ret.append(app_Tree)
            dct[(left,right)]=ret
            return ret
        left_right(1,n)
        return left_right(1,n)

#leetcode410
class Solution410:
    def splitArray(self, nums: List[int], m: int) -> int:
        n = len(nums)
        f = [[10**18] * (m + 1) for _ in range(n + 1)]
        sub = [0]
        for elem in nums:
            sub.append(sub[-1] + elem)

        f[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, min(i, m) + 1):
                for k in range(i):
                    f[i][j] = min(f[i][j], max(f[k][j - 1], sub[i] - sub[k]))

        return f[n][m]


class Solution329:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        x=len(matrix)
        y=len(matrix[0])
        dp=[[1 for _ in range(y)] for _ in range(x)]
        numsSort=sorted(sum([[(matrix[i][j],i,j) for j in range(y)] for i in range(x)],[]))
        for i,j,k in numsSort:
            dp[j][k]=1+max(dp[j-1][k] if j and matrix[j-1][k]<i else 0,
                           dp[j][k-1] if k and matrix[j][k-1]<i else 0, 
                            dp[j+1][k] if j != x-1 and matrix[j+1][k]<i else 0, 
                            dp[j][k+1] if k != y-1 and matrix[j][k+1]<i else 0)
        
        return max(sum(dp,[]))


#leetcode392
class Solution392:
    def isSubsequence(self, s: str, t: str) -> bool:
        n,m=len(s),len(t)
        inx=-1
        for i in range(n):
            for j in range(inx+1,m):
                if t[j]==s[i]:
                    inx=j
                    break
            else:
                return False
        return True

#leetcode104
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution104:
    def maxDepth(self, root: TreeNode) -> int:
        return 0 if not root else max(self.maxDepth(root.left),self.maxDepth(root.right))+1


#leetcode503
class Solution503:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        length=len(nums)

        nums=nums+nums
        result=[-1]*length
        stack=[0]

        for i in range(1,len(nums)):
            while(stack and nums [stack[-1]]<nums[i]):
                target=stack.pop()
                result[target%length]=nums[i]
            stack.append(i%length)
        return result


#leetcode343
class Solution343:
    def integerBreak(self, n: int) -> int:
        if n <= 3:
            return n-1
        a,b=n//3,n%3
        if b==0:
            return int(math.pow(3,a))
        if b==1:
            return int(math.pow(3,a-1)*4)
        return int(math.pow(3,a)*2)
      
#leetcode328
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution328:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:return head
        odd=head
        even_head=even=head.next
        while odd.next and even.next:
            odd.next=odd.next.next
            even.next=even.next.next
            odd,even=odd.next,even.next
        odd.next=even_head
        return head
 

#leetcode634
import heapq
class Solution634:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        k=len(nums)
        elem_id_index=[(elem[0],id,0) for id,elem in enumerate(nums)]
        heapq.heapify(elem_id_index)
        maxval,minval=1e5,-1e5
        currmaxcal=max(elem_id_index)[0]

        while True:
            currmincal,id,index=heapq.heappop(elem_id_index)
            if currmaxcal-currmincal<maxval-minval:
                maxval=currmaxcal
                minval=currmincal
            if index<len(nums[id])-1:
                val=nums[id][index+1]
                currmaxcal=max(currmaxcal,val)
                heapq.heappush(elem_id_index,(val,id,index+1))
            else:
                break
        return [minval,maxval]


#leetcode114
# 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 Solution114:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        def helper(root,pre):
            if not root:
                return pre
            pre=helper(root.right,pre)
            pre=helper(root.left,pre)

            root.right=pre
            root.left=None
            return root
        helper(root,None)


#leetcode415
class Solution415:
    def addStrings(self, num1: str, num2: str) -> str:
        res=""
        i,j,carry=len(num1)-1,len(num2)-1,0
        while i >=0 or j>=0:
            n1=int(num1[i]) if i>=0 else 0
            n2=int(num2[j]) if j>=0 else 0
            tmp=n1+n2+carry
            carry=tmp//10
            res=str(tmp%10)+res
            i,j=i-1,j-1
        return "1"+res if carry else res

#leetcode207
class Solution207:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        def dfs(i,adjacency,flags):
            if flags[i]==-1:return True
            if flags[i]==1:return False
            flags[i]=1
            for j in adjacency[i]:
                if not dfs(j,adjacency,flags):return False
            flags[i]=-1
            return True
            
        adjacency=[[] for _ in range(numCourses)]
        flags=[0 for _ in range(numCourses)]
        for cur,pre in prerequisites:
            adjacency[pre].append(cur)
        for i in range(numCourses):
            if not dfs(i,adjacency,flags):return False
        return True


#leetcdoe337
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution337:
    def dp(self, cur: TreeNode) -> List[int]:
        if not cur:
            return [0,0]

        l=self.dp(cur.left)
        r=self.dp(cur.right)
        return [max(l)+max(r),cur.val+l[0]+r[0]]

    def rob(self, root: TreeNode) -> int:
        return max(self.dp(root))


#leetcode336
class Solution336:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        lookup={w:i for i,w in enumerate(words)}
        res=[]
        for i,w in enumerate(words):
            for j in range(len(w)+1):
                pre,suf=w[:j],w[j:]
                if pre[::-1]==pre and suf[::-1] != w and suf[::-1] in lookup:
                    res.append([lookup[suf[::-1]],i])
                if suf[::-1] == suf and pre[::-1] != w and pre[::-1] in lookup and j !=len(w):
                    res.append([i,lookup[pre[::-1]]])
        return res
        
#leetcode100
# 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 Solution100:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        def preorder(root):
            if not root:
                return [None]
            else:
                return [root.val]+preorder(root.left)+preorder(root.right)
        return preorder(p)==preorder(q)


#leetcode99
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution99:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        firstNode = None
        secondNode = None
        pre = TreeNode(float("-inf"))

        stack = []
        p = root
        while p or stack:
            while p:
                stack.append(p)
                p = p.left
            p = stack.pop()

            if not firstNode and pre.val > p.val:
                    firstNode = pre
            if firstNode and pre.val > p.val:
                #print(firstNode.val,pre.val, p.val)
                secondNode = p
            pre = p
            p = p.right
        firstNode.val, secondNode.val = secondNode.val, firstNode.val
        
#leetcode93
class Solution93:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res=[]
        n=len(s)

        def backtrack(i,tmp,flag):
            if i==n and flag==0:
                res.append(tmp[:-1])
                return
            if flag<0:
                return
            for j in range(i,i+3):
                if j<n:
                    if i==j and s[j]=="0":
                        backtrack(j+1,tmp+s[j]+".",flag-1)
                        break
                    if 0<int(s[i:j+1])<=255:
                        backtrack(j+1,tmp+s[i:j+1]+".",flag-1)
        backtrack(0,"",4)
        return res

#leetcode696
class Solution696:
    def countBinarySubstrings(self, s: str) -> int:
        length=len(s)
        cur=1
        prev=0
        res=0
        for i in range(1,length):
            if s[i]==s[i-1]:
                cur+=1
            else:
                res+=min(cur,prev)
                prev=cur
                cur=1
        return res+min(cur,prev)


#leetcode130
class Solution130:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]:
            return
        row = len(board)
        col = len(board[0])

        def dfs(i, j):
            board[i][j] = "B"
            for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                tmp_i = i + x
                tmp_j = j + y
                if 1 <= tmp_i < row and 1 <= tmp_j < col and board[tmp_i][tmp_j] == "O":
                    dfs(tmp_i, tmp_j)

        for j in range(col):
            # 第一行
            if board[0][j] == "O":
                dfs(0, j)
            # 最后一行
            if board[row - 1][j] == "O":
                dfs(row - 1, j)

        for i in range(row):
            # 第一列
            if board[i][0] == "O":
                dfs(i, 0)
            # 最后一列
            if board[i][col-1] == "O":
                dfs(i, col - 1)

        for i in range(row):
            for j in range(col):
                # O 变成 X
                if board[i][j] == "O":
                    board[i][j] = "X"
                # B 变成 O
                if board[i][j] == "B":
                    board[i][j] = "O"

#leetcode133
"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = []):
        self.val = val
        self.neighbors = neighbors
"""

class Solution133:
    def cloneGraph(self, node: 'Node') -> 'Node':
        lookup = {}

        def dfs(node):
            #print(node.val)
            if not node: return
            if node in lookup:
                return lookup[node]
            clone = Node(node.val, [])
            lookup[node] = clone
            for n in node.neighbors:
                clone.neighbors.append(dfs(n))
            
            return clone

        return dfs(node)


#leetcode43
class Solution43:
    def str2int(self,s):
        return ord(s)-ord('0')

    def multiply(self, num1: str, num2: str) -> str:
        a=num1[::-1]
        b=num2[::-1]
        result=0


        for i,x in enumerate(a):
            temp_result=0
            for j,y in enumerate(b):
                temp_result+=self.str2int(x)*self.str2int(y)*10**j
            result+=temp_result*10**i

        return str(result)


#leetcode130
class Solution130:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]:
            return
        row = len(board)
        col = len(board[0])

        def dfs(i, j):
            board[i][j] = "B"
            for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                tmp_i = i + x
                tmp_j = j + y
                if 1 <= tmp_i < row and 1 <= tmp_j < col and board[tmp_i][tmp_j] == "O":
                    dfs(tmp_i, tmp_j)

        for j in range(col):
            # 第一行
            if board[0][j] == "O":
                dfs(0, j)
            # 最后一行
            if board[row - 1][j] == "O":
                dfs(row - 1, j)

        for i in range(row):
            # 第一列
            if board[i][0] == "O":
                dfs(i, 0)
            # 最后一列
            if board[i][col-1] == "O":
                dfs(i, col - 1)

        for i in range(row):
            for j in range(col):
                # O 变成 X
                if board[i][j] == "O":
                    board[i][j] = "X"
                # B 变成 O
                if board[i][j] == "B":
                    board[i][j] = "O"


#leetcode546
class Solution546:
    def removeBoxes(self, boxes: List[int]) -> int:
        memo={}

        def dp(l,r,n):
            nonlocal memo,boxes
            if memo.get((l,r,n)):
                return memo[(l,r,n)]

            if l==r-1:
                return (n+1)*(n+1)

            if boxes[l]==boxes[l+1]:
                return dp(l+1,r,n+1)

            res=(n+1)*(n+1)+dp(l+1,r,0)

            for l2 in range(l+2,r):
                if boxes[l2]==boxes[l]:
                    res=max(res,dp(l+1,l2,0)+dp(l2,r,n+1))
            memo[(l,r,n)]=res
            return res
        return dp(0,len(boxes),0)


#leetcode733
class Solution733:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        row, col = len(image), len(image[0])
        p = image[sr][sc]
        deq = deque([(sr, sc)])
        if p == newColor:
            return image
        while deq:
            x, y = deq.popleft()
            if x in {-1, row} or y in {-1, col} or image[x][y] != p:
                continue
            image[x][y] = newColor
            deq.extend([(x-1, y), (x, y-1), (x+1, y), (x, y+1)])
        return image


#leetcode110
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution110:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.recur(root) != -1

    def recur(self,root):
        if not root: return 0
        left=self.recur(root.left)

        if left=-1:
            return -1
        right=self.recur(root.right)

        if right=-1:return -1
        return max(left,right)+1 if abs(left-right)<2 else -1
        
        
#leecode109
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 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 Solution109:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        def findmid(head,tail):
            slow=head
            fast=head
            while fast != tail and fast.next != tail:
                slow=slow.next
                fast=fast.next.next
            return slow

        def helper(head,tail):
            if head==tail:return
            node=findmid(head,tail)
            root=TreeNode(node.val)
            root.left=helper(head,node)
            root.right=helper(node.next,tail)
            return root

        return helper(head,None)



#leetcode647
class Solution647:
    def countSubstrings(self, s: str) -> int:
        """
        （1）思路：动态规划
                我们以dp[i][j]表示区间[i, j]之间的子串是否为回文子串，这样可以思考这样三种情况的回文子串：
                    - 子串长度为1，例如 a 一定为回文子串，即 i=j 的情况
                    - 子串长度为2，且字符相同，例如 aa 一定为回文自传，即 s[i] = s[j] and j-i = 1
                    - 子串长度大于2，符合 abcba 形式的为回文子串，根据回文子串的定义，那么 abcba 去掉两边字符，仍为回文
                    子串，即bcb，转换成方程形式即 dp[i][j] = dp[i+1][j-1] and j-i > 1 and s[i] = s[j]
                剩下的均为不符合条件，即非回文子串。

        （2）复杂度：
            - 时间复杂度：O（N^2）
            - 空间复杂度：O（N^2）
        """
        # 处理特殊情况
        str_len = len(s)
        if str_len == 0 or s is None:
            return 0
        # 定义变量储存结果
        res = 0
        # 定义和初始化dp数组
        dp = [[False for _ in range(str_len)] for _ in range(str_len)]
        # 直接先给对角线赋值为True，防止出现 dp[i][j] = dp[i + 1][j - 1] 时，前值没有，例如，i=0，j=2的时候
        for i in range(str_len):
            dp[i][i] = True
        # 遍历字符串，更新dp数组
        # 注意，由于状态转义方程第三种情况是 dp[i][j] = dp[i + 1][j - 1] ，dp取决于 i+1的状态，但是正常遍历
        # 我们肯定是先有了i的状态才能有i+1的 状态，所以，此处我们遍历以 j 为主
        for j in range(str_len):
            # 因为对角线已经赋初始值，所以直接从i+1开始遍历
            for i in range(0, j):
                # 第一种情况，子串长度为1，例如 a 一定为回文子串，因为已经处理了对角线
                # 这里可以注释
                if j - i == 0:
                    dp[i][j] = True
                # 第二种和第三种可以合并，因为对于s[i]=s[j],中间加一个字符是没有影响的，即aba肯定也是回文子串
                # 所以可以合并为 j-i >= 1 and s[i] == s[j]

                # 第二种情况，子串长度为2，且字符相同，例如 aa 一定为回文自传，即 s[i] = s[j] and j-i = 1
                elif j - i == 1:
                    if s[i] == s[j]:
                        dp[i][j] = True
                # 第三种情况，子串长度大于2，符合 abcba 形式的为回文子串否则不是，即dp[i][j]取决于dp[i + 1][j - 1] 是否
                # 是回文子串
                else:
                    if s[i] == s[j]:
                        dp[i][j] = dp[i + 1][j - 1]
        # 遍历dp数组，数True的个数
        for i in range(str_len):
            for j in range(i, str_len):
                if dp[i][j] is True:
                    res += 1
        return res



#leetcode529
class Solution529:
        def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
            direction = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1))
            if board[click[0]][click[1]] == 'M':
                board[click[0]][click[1]] = 'X'
                return board
            self.m,self.n = len(board), len(board[0])
            check = lambda i, j, char: 0 <= i < m and 0 <= j < n and board[i][j] == char
            def check(i, j):
                cnt = 0
                for x,y in direction:
                    x, y = x + i, y + j
                    if 0 <= x < self.m and 0 <= y < self.n and board[x][y]=='M':
                        cnt += 1
                return cnt    
            def dfs(i, j):
                cnt = check(i, j)
                if not cnt:
                    board[i][j] = 'B'
                    for x, y in direction:
                        x, y = x + i, y + j
                        if  0 <= x < self.m and 0 <= y < self.n and board[x][y]=='E': dfs(x, y)
                else: board[i][j] = str(cnt)
            dfs(click[0],click[1])
            return board


#leetcode111
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution111:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        l, r = self.minDepth(root.left), self.minDepth(root.right)
        if root.left and root.right: return 1 + min(l, r)
        else: return 1 + l + r


#leetcode679
class Solution679:
    def judgePoint24(self, nums: List[int]) -> bool:
        if not nums: return False
        def helper(nums):
            if len(nums) == 1: return abs(nums[0]-24) < 1e-6
            for i in range(len(nums)):
                for j in range(len(nums)):
                    if i != j:
                        newnums = [nums[k] for k in range(len(nums)) if i != k != j]
                        if helper(newnums + [nums[i]+nums[j]]): return True
                        if helper(newnums + [nums[i]-nums[j]]): return True
                        if helper(newnums + [nums[i]*nums[j]]): return True
                        if nums[j] != 0 and helper(newnums + [nums[i]/nums[j]]): return True
            return False
        return helper(nums)



#leetcode201
class Solution201:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        t=0
        while m !=n:
            m>>=1
            n>>=1
            t+=1
        return n<<t


#leetcode459
class Solution459:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n=len(s)
        next=[-1] * n
        for i in range(1,n):
            j=next[i-1]
            while j >=0 and s[j+1] != s[i]:
                j=next[j]

            if s[j+1] == s[i]:
                    next[i]=j+1
        return next[-1]>=0 and n%(n-1-next[-1]) ==0


#leetcode491
class Solution491:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []

        def dfs(nums: List[int], tmp: List[int]) -> None:
            if len(tmp) > 1:
                res.append(tmp)
            curPres = defaultdict(int)
            for inx, i in enumerate(nums):
                if curPres[i]:
                    continue
                if not tmp or i >= tmp[-1]:
                    curPres[i] = 1
                    dfs(nums[inx+1:], tmp+[i])

        dfs(nums, [])
        return res


#leetcode17
class Solution17:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:return []
        phone=['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
        queue=['']
        for digits in digits:
            for _ in range(len(queue)):
                tmp=queue.pop(0)
                for letter in phone[ord(digits)-50]:
                    queue.append(tmp+letter)
        return queue

#leetcode332
class Solution332:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        d=collections.defaultdict(list)
        for f,t in tickets:
            d[f]+=[t]
        for f in d:
            d[f].sort()
        ans=[]
        def dfs(f):
            while d[f]:
                dfs(d[f].pop(0))
            ans.insert(0,f)
        dfs('JFK')
        return ans

#leetcode657
class Solution(object)657:
    def judgeCircle(self, moves):
        x = y = 0
        for move in moves:
            if move == 'U': y -= 1
            elif move == 'D': y += 1
            elif move == 'L': x -= 1
            elif move == 'R': x += 1

        return x == y == 0

#leetcode214
class Solution214:
    def shortestPalindrome(self, s: str) -> str:
        j = 0
        # 找到从头开始，最长的回文子串
        for i in range(len(s) - 1, -1, -1):
            if s[i] == s[j]: j += 1
        if j == len(s): return s
        # 后缀
        suffix = s[j:]
        return suffix[::-1] + self.shortestPalindrome(s[0:j]) + suffix

#leetcode557
class Solution557:
    def reverseWords(self, s: str) -> str:
        return ' '.join(s.split(' ')[::-1])[::-1]
        


#leetcode841
class Solution841:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited,queue={0},[0]
        while queue:
            room_index=queue.pop()
            for key in rooms[room_index]:
                if key not in visited:
                    visited.add(key)
                    queue.insert(0,key)
        return len(visited)==len(rooms)


#leetcode486
class Solution486:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        n=len(nums)
        dp=[[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i]=nums[i]
        for i in range(n-2,-1,-1):
            for j in range(i+1,n):
                dp[i][j]=max(nums[j]-dp[i][j-1],nums[i]-dp[i+1][j])
        return dp[0][-1]>=0
        
        
#leetcode167
class Solution167:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        low, high = 0, len(numbers) - 1
        while low < high:
            total = numbers[low] + numbers[high]
            if total == target:
                return [low + 1, high + 1]
            elif total < target:
                low += 1
            else:
                high -= 1

        return [-1, -1]

#leetcode51
class Solution51:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def generateBoard():
            board = list()
            for i in range(n):
                row[queens[i]] = "Q"
                board.append("".join(row))
                row[queens[i]] = "."
            return board

        def backtrack(row: int):
            if row == n:
                board = generateBoard()
                solutions.append(board)
            else:
                for i in range(n):
                    if i in columns or row - i in diagonal1 or row + i in diagonal2:
                        continue
                    queens[row] = i
                    columns.add(i)
                    diagonal1.add(row - i)
                    diagonal2.add(row + i)
                    backtrack(row + 1)
                    columns.remove(i)
                    diagonal1.remove(row - i)
                    diagonal2.remove(row + i)

        solutions = list()
        queens = [-1] * n
        columns = set()
        diagonal1 = set()
        diagonal2 = set()
        row = ["."] * n
        backtrack(0)
        return solutions


#leetcode378
class Solution378:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)

        def check(mid):
            i, j = n - 1, 0
            num = 0
            while i >= 0 and j < n:
                if matrix[i][j] <= mid:
                    num += i + 1
                    j += 1
                else:
                    i -= 1
            return num >= k

        left, right = matrix[0][0], matrix[-1][-1]
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1

        return left
#leetcode257
class Solution257:
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        def construct_paths(root, path):
            if root:
                path += str(root.val)
                if not root.left and not root.right:  # 当前节点是叶子节点
                    paths.append(path)  # 把路径加入到答案中
                else:
                    path += '->'  # 当前节点不是叶子节点，继续递归遍历
                    construct_paths(root.left, path)
                    construct_paths(root.right, path)

        paths = []
        construct_paths(root, '')
        return paths


#leetcode60
class Solution60:
    def getPermutation(self, n: int, k: int) -> str:
        factorial = [1]
        for i in range(1, n):
            factorial.append(factorial[-1] * i)

        k -= 1
        ans = list()
        valid = [1] * (n + 1)
        for i in range(1, n + 1):
            order = k // factorial[n - i] + 1
            for j in range(1, n + 1):
                order -= valid[j]
                if order == 0:
                    ans.append(str(j))
                    valid[j] = 0
                    break
            k %= factorial[n - i]

        return "".join(ans)


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution107:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        levelOrder = list()
        if not root:
            return levelOrder
        
        q = collections.deque([root])
        while q:
            level = list()
            size = len(q)
            for _ in range(size):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            levelOrder.append(level)

        return levelOrder[::-1]


#leetcdoe347
class Solution347:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        def sift_down(arr, root, k):
            """下沉log(k),如果新的根节点>子节点就一直下沉"""
            val = arr[root] # 用类似插入排序的赋值交换
            while root<<1 < k:
                child = root << 1
                # 选取左右孩子中小的与父节点交换
                if child|1 < k and arr[child|1][1] < arr[child][1]:
                    child |= 1
                # 如果子节点<新节点,交换,如果已经有序break
                if arr[child][1] < val[1]:
                    arr[root] = arr[child]
                    root = child
                else:
                    break
            arr[root] = val

        def sift_up(arr, child):
            """上浮log(k),如果新加入的节点<父节点就一直上浮"""
            val = arr[child]
            while child>>1 > 0 and val[1] < arr[child>>1][1]:
                arr[child] = arr[child>>1]
                child >>= 1
            arr[child] = val

        stat = collections.Counter(nums)
        stat = list(stat.items())
        heap = [(0,0)]

        # 构建规模为k+1的堆,新元素加入堆尾,上浮
        for i in range(k):
            heap.append(stat[i])
            sift_up(heap, len(heap)-1)
        # 维护规模为k+1的堆,如果新元素大于堆顶,入堆,并下沉
        for i in range(k, len(stat)):
            if stat[i][1] > heap[1][1]:
                heap[1] = stat[i]
                sift_down(heap, 1, k+1)
        return [item[0] for item in heap[1:]]


#leetcode77
class Solution77:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        def backtrack(i, k, tmp):
            if k == 0:
                res.append(tmp)
                return
            for j in range(i, n + 1):
                backtrack(j+1, k-1, tmp + [j])
        backtrack(1, k, [])
        return res

#leetcode39
from typing import List


class Solution39:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        def dfs(candidates, begin, size, path, res, target):
            if target == 0:
                res.append(path)
                return

            for index in range(begin, size):
                residue = target - candidates[index]
                if residue < 0:
                    break

                dfs(candidates, index, size, path + [candidates[index]], res, residue)

        size = len(candidates)
        if size == 0:
            return []
        candidates.sort()
        path = []
        res = []
        dfs(candidates, 0, size, path, res, target)
        return res


class Solution40:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(pos: int, rest: int):
            nonlocal sequence
            if rest == 0:
                ans.append(sequence[:])
                return
            if pos == len(freq) or rest < freq[pos][0]:
                return
            
            dfs(pos + 1, rest)

            most = min(rest // freq[pos][0], freq[pos][1])
            for i in range(1, most + 1):
                sequence.append(freq[pos][0])
                dfs(pos + 1, rest - i * freq[pos][0])
            sequence = sequence[:-most]
        
        freq = sorted(collections.Counter(candidates).items())
        ans = list()
        sequence = list()
        dfs(0, target)
        return ans

#leetcode637
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution637:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        def dfs (root:TreeNode,level:int):
            if not root:
                return 
            if level<len(totals):
                totals[level]+=root.val
                counts[level]+=1
            else:
                totals.append(root.val)
                counts.append(1)
            dfs(root.left,level+1)
            dfs(root.right,level+1)
        
        counts=list()
        totals=list()
        dfs(root,0)
        return [total/count for total,count in zip(totals,counts)]

#leetcode79
class Solution79:
    def exist(self, board: List[List[str]], word: str) -> bool:
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def check(i: int, j: int, k: int) -> bool:
            if board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True
            
            visited.add((i, j))
            result = False
            for di, dj in directions:
                newi, newj = i + di, j + dj
                if 0 <= newi < len(board) and 0 <= newj < len(board[0]):
                    if (newi, newj) not in visited:
                        if check(newi, newj, k + 1):
                            result = True
                            break
            
            visited.remove((i, j))
            return result

        h, w = len(board), len(board[0])
        visited = set()
        for i in range(h):
            for j in range(w):
                if check(i, j, 0):
                    return True
        
        return False


#leetcode94
class Solution94:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        White,Gray=0,1
        res=[]
        stack=[(White,root)]
        while stack:
            color,node=stack.pop()
            if node is None:continue
            if color==White:
                stack.append((White,node.right))
                stack.append((Gray,node))
                stack.append((White,node.left))
            else:
                res.append(node.val)
        return res


#leetcode37
class Solution37:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def dfs(pos: int):
            nonlocal valid
            if pos == len(spaces):
                valid = True
                return
            
            i, j = spaces[pos]
            for digit in range(9):
                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
                    board[i][j] = str(digit + 1)
                    dfs(pos + 1)
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False
                if valid:
                    return
            
        line = [[False] * 9 for _ in range(9)]
        column = [[False] * 9 for _ in range(9)]
        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]
        valid = False
        spaces = list()

        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    spaces.append((i, j))
                else:
                    digit = int(board[i][j]) - 1
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True

        dfs(0)