# 双指针，fast 表示 子序列以fast为最右元素
# slow指针判定子序列最左的元素
# 同时从左到右进行遍历
# > tsum 就是减少子序列个数，<tsum 增加子序列个数
# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        n = tsum//2+1
        fast = 2
        slow = 1
        res = []
        while slow<fast and fast <= n:
            curr = (slow+fast)*(fast-slow+1)//2
            if curr == tsum:
                res.append(list(range(slow,fast+1)))
                fast += 1
            elif curr < tsum:
                fast += 1
            else:
                slow += 1
        return res

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        m,n=len(g),len(s)
        g.sort()
        s.sort()
        i,j,count=0,0,0
        while(i<m and j<n):
            if(g[i]<=s[j]):
                count+=1
                i+=1
                j+=1
            else:
                j+=1
        return count

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x:x[1])
        count=1
        end=intervals[0][1]
        for i in range(1,len(intervals)):
            if(intervals[i][0]>=end):
                count+=1
                end=intervals[i][1]
        return len(intervals)-count

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        #求不重叠区间个数，就是飞镖个数
        if not points:
            return 0
        points.sort(key=lambda x:x[1])
        count=1
        end=points[0][1]
        for i in range(1,len(points)):
            if(points[i][0]>end):
                end=points[i][1]
                count+=1
        return count

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #一次交易
        if not prices:
            return 0
        max_profit=0
        min_price=prices[0]
        for i in range(1,len(prices)):
            min_price=min(prices[i],min_price)
            max_profit=max(max_profit,prices[i]-min_price)
        return max_profit

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #多次交易
        if not prices:
            return 0
        sum_profit=0
        for i in range(1,len(prices)):
            if(prices[i]>prices[i-1]):
                sum_profit+=prices[i]-prices[i-1]
        return sum_profit

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        #只需要判断前后即可，防止考虑边界问题，在前后加上[0]，只要连续出现在三个[0]就可以种花
        flowerbed=[0]+flowerbed+[0]
        count=0
        for i in range(1,len(flowerbed)-1):
            if(flowerbed[i-1]==0 and flowerbed[i]==0 and flowerbed[i+1]==0):
                flowerbed[i]=1
                count+=1
        if(count>=n):
            return True
        else:
            return False
        

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        index=-1
        for ele in s:
            index=t.find(ele,index+1)
            if index==-1:
                return False
        return True

class Solution:
    def candy(self , arr ):
        # write code here
        res = [1] * len(arr)
        for i in range(1, len(arr)):
            if arr[i] > arr[i-1]:
                res[i] = res[i-1] + 1
        for i in range(len(arr)-2, -1, -1):
            if arr[i] > arr[i+1]:
                res[i] = max(res[i+1] + 1, res[i])
        return sum(res)

class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        start = list()
        end =list()
        #分别得到活动起始时间
        for i in range(n):
            start.append(startEnd[i][0])
            end.append(startEnd[i][1])
        #分别对开始和结束时间排序
        start.sort()
        end.sort()
        res = 0
        j = 0
        for i in range(n):
            #新开始的节目大于上一轮结束的时间，主持人不变
            if start[i] >= end[j]: 
                j += 1
            else:
                #主持人增加
                res += 1  
        return res

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farest_idx = 0  # 最远可达位置
        for i, jump in enumerate(nums):
            if i <= farest_idx and farest_idx < i + jump:
                farest_idx = i + jump
        return farest_idx >= len(nums) - 1

class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        if not s:
            return True
        stack.append(s[0])
        for i in range(1,len(s)):
            if(len(stack) and ((s[i]==')' and stack[-1]=='(') or (s[i]=='}' and stack[-1]=='{') or (s[i]==']' and stack[-1]=='['))):
                stack.pop()
            else:
                stack.append(s[i])
        if(len(stack)>0):
            return False
        return True

import numpy as np
class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        stack=[]
        res=np.zeros(len(T),np.int)
        stack.append(0)
        for cur_index in range(1,len(T)):
            while(len(stack)!=0 and T[cur_index]>T[stack[-1]]):#判断条件
                pre_index=stack.pop()
                res[pre_index]=cur_index-pre_index
            stack.append(cur_index)
        return res

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        #遍历列表两次，只将第一次的入队列
        list_len=len(nums)
        res=[-1]*list_len
        stack=[]
        for index in range(2*list_len):
            while(len(stack) and nums[index%list_len]>nums[stack[-1]]):
                pre_index=stack.pop()
                res[pre_index]=nums[index%list_len]
            if(index<len(nums)):
                stack.append(index)
        return res

# -*- coding:utf-8 -*-
class Solution:
    '''
    1.当插入时，直接插入 stack1
    2.当弹出时，当 stack2 不为空，弹出 stack2 栈顶元素，
    如果 stack2 为空，将 stack1 中的全部数逐个出栈入栈 stack2，
    再弹出 stack2 栈顶元素
    '''
    def __init__(self):
        self.stack1= []
        self.stack2= []
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        if len(self.stack2)==0:
            while(len(self.stack1)!=0):
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []  #初始化原栈
        self.stack_min = []  #初始化最小值栈
    def push(self, node):
        self.stack.append(node) #往原栈中添加 元素
        if not self.stack_min:    #一开始也往最小值栈中添加元素
            self.stack_min.append(node)
        elif node < self.stack_min[-1]:  #再次添加元素的时候要同最小值栈中元素比较，小于最小值栈中索引-1的对应值，就把node加入；
            self.stack_min.append(node)
        else:
            self.stack_min.append(self.stack_min[-1])  #否则把索引-1的对应值添加到stack_min中
    def pop(self):
        self.stack.pop()                    #弹出栈顶元素则分别获取即可
        self.stack_min.pop()
    def top(self):
        return self.stack[-1]                #栈顶元素从原栈中获取
    def min(self):
        return self.stack_min[-1]              #最小值就直接从最小值栈中获取

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:

        res=[]
        #双端队列
        queue=[]#左边做队首，右边做队尾。做成递减队列

        for i in range(len(num)):
            if len(queue)>0 and i>queue[0]+size-1:#i走到超出原来最大值能覆盖的窗口的位置，那么这个最大值要更新了
                queue.pop(0)

            while len(queue)>0 and num[i]>num[queue[-1]]:#要进队的数数值大，那就删除所有前面小的数，再把它加进去。
                #终止时要加进去的数要么排在第一了，要么就排在比它大的数的后面
                #要加len(queue)>0 这个条件，否则当queue被删空了代码就会出现num[-1]这样索引报错的情况
                queue.pop()
            queue.append(i)

            if i>=size-1:
                res.append(num[queue[0]])               
        return res

class Solution:
    def GetLeastNumbers_Solution(self, a, k):
         import heapq
         return heapq.nsmallest(k,a)

import heapq
class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
         heap = []
         for i in range(n):
             heapq.heappush(heap, -a[i]) # 小顶堆存进去负数
         for i in range(K-1):
             heapq.heappop(heap) #出队前K-1个（最大的）
         return -heapq.heappop(heap) # 相反数

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.li = []

    def Insert(self, num):
        for i in range(len(self.li)):
            if num < self.li[i]:
                self.li.insert(i, num)
                break
        else:
            self.li.append(num)

    def GetMedian(self):
        length = len(self.li)
        if length == 1:
            return self.li[0]
        return (self.li[length//2] + self.li[(length-1)//2]) / 2

 
class Solution:
    def decodeString(self, s):
        stack = []  # (str, int) 记录之前的字符串和括号外的上一个数字
        num = 0
        res = ""  # 实时记录当前可以提取出来的字符串
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == "[":
                stack.append((res, num))
                res, num = "", 0
            elif c == "]":
                top = stack.pop()
                print('===top:', top)
                res = top[0] + res * top[1]
                print('==res:', res)
            else:
                res += c
        return res
 
# s = "3[a]2[bc]"
s = "3[a2[c]]"
sol = Solution()
res = sol.decodeString(s)
print('res:', res)

class Solution:
    def LRU(self , operators: List[List[int]], k: int) -> List[int]:
        stack = [] #有序
        div_kv = {} #无序
        res = []  #结果
        for op in operators:
            if op[0] == 1:#set操作
                if len(stack) >= k: 
                    del div_kv[stack.pop(0)]
                if op[1] in div_kv: 
                    stack.remove(op[1])
                stack.append(op[1])
                div_kv[op[1]] = op[2] 
            elif op[0] == 2:#get操作
                if op[1] not in div_kv:
                    res.append(-1)
                else:
                    stack.remove(op[1])
                    stack.append(op[1])
                    res.append(div_kv[op[1]])
        return res

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if not pushV or len(pushV) != len(popV):
            return False
        stack = []
        for ii in pushV:
            stack.append(ii)
            while len(stack) and stack[-1] == popV[0]:
                stack.pop()
                popV.pop(0)
                
        if len(stack):
            return False
        return True

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        else:
            LD=self.maxDepth(root.left)
            RD=self.maxDepth(root.right)
            return max(LD,RD)+1

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def get_depth(root):
            if not  root:
                return 0
            else:
                LD=get_depth(root.left)
                RD=get_depth(root.right)
                return max(LD,RD)+1
        if not root:
            return True
        LD=get_depth(root.left)
        RD=get_depth(root.right)
        if(abs(LD-RD)>1):
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.max=0
        #最长路径未必经过根节点
        def get_depth(root):
            if not root:
                return 0
            else:
                LD=get_depth(root.left)
                RD=get_depth(root.right)
                self.max=max(LD+RD,self.max)
                return max(LD,RD)+1
        if not root:
            return 0
        else:
            get_depth(root)
            return self.max

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if  root:
            self.invertTree(root.left)
            self.invertTree(root.right)
            temp=root.left
            root.left=root.right
            root.right=temp
        return root

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        #修改之前的树，先序遍历
        if not t1:
            return t2
        if not t2:
            return t1
        else:
            t1.val+=t2.val
            t1.left=self.mergeTrees(t1.left,t2.left)
            t1.right=self.mergeTrees(t1.right,t2.right)
            return t1

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        #与剑指offer一题目类似
        if(not root):
            return False
        if(not root.left and not root.right and root.val==sum):
            return True
        sum-=root.val   
        return self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum)

class Solution:
    def isSubtree(self, root: [TreeNode], subRoot: [TreeNode]) -> bool:
        def is_equal(root, subRoot):
            if not root and not subRoot:
                return True
            if not subRoot or not root:
                return False
            if (root.val == subRoot.val):
                return is_equal(root.left, subRoot.left) and is_equal(root.right, subRoot.right)

        if not root:
            return False

        return is_equal(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool: 
        def dfs(p,q):
            #判断子树是否相同
            if(not p and not q):
                return True
            if(not p or not q):
                return False
            if(p.val==q.val):
                return dfs(p.left,q.right) and dfs(p.right,q.left)
        if not root:
            return True
        return dfs(root.left,root.right)

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        #要注意如果根节点的左或右子树为空的话是构不成子树的。而最小深度是要求从根节点到子树的
        if not root:
            return 0
        elif not root.left:
            return self.minDepth(root.right)+1
        elif not root.right:
            return self.minDepth(root.left)+1
        else:   
            left=self.minDepth(root.left)
            right=self.minDepth(root.right)
            return min(left,right)+1

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        #有点疑惑
        if not root:
            return 0
        sum=0
        if root.left and  not root.left.left and not root.left.right:
            sum=sum+root.left.val+self.sumOfLeftLeaves(root.right)
        else:
            sum=sum+self.sumOfLeftLeaves(root.right)+self.sumOfLeftLeaves(root.left)
        return sum

class Solution:
    def rob(self, root: TreeNode) -> int:
        #后序遍历，树dp,dp[0]代表不抢该节点可以获取的最大值，dp[1]代表抢该节点
        def  dfs(root):
            if not root:
                return [0,0]
            left=dfs(root.left)
            right=dfs(root.right)
            result=[0,0]
            result[0]=max(left[0],left[1])+max(right[0],right[1])
            result[1]=root.val+left[0]+right[0]
            return result
        res=dfs(root)
        return max(res[0],res[1])

class Solution:
    result=[]
    def findSecondMinimumValue(self, root: TreeNode) -> int:
        def pre_order(root,val_list):
            if(root):
                pre_order(root.left,val_list)
                pre_order(root.right,val_list)
                val_list.append(root.val)
        val_list=[]
        pre_order(root,val_list)
        val_list.sort()
        val_2 = list(set(val_list))
        val_2.sort(key = val_list.index)
        if(len(val_2)<2):
            return -1
        return val_2[1]

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        queue,result=[],[]
        queue.append(root)
        while(len(queue)):
            length,temp_len=len(queue),len(queue)
            sum=0
            while(length):
                length-=1
                p=queue.pop(0)
                sum+=p.val
                if(p.left):
                    queue.append(p.left)
                if(p.right):
                    queue.append(p.right)
            result.append(sum/temp_len)
        return result

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        queue=[]
        queue.append(root)
        while(len(queue)):
            #遍历完一层将结果记录下来
            length,temp_len=len(queue),len(queue)
            level_res=[]
            while(length):
                length-=1
                p=queue.pop(0)
                level_res.append(p.val)
                if(p.left):
                    queue.append(p.left)
                if(p.right):
                    queue.append(p.right)
        return level_res[0]

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack=[]
        stack.append(root)
        result=[]
        while(len(stack)>0):
            temp=stack.pop()
            result.append(temp.val)
            if(temp.right):
                stack.append(temp.right)
            if(temp.left):
                stack.append(temp.left)
        return result

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack=[]
        p=root
        result=[]
        while(p or len(stack)):
            if(p):
                stack.append(p)
                p=p.left
            else:
                p=stack.pop()
                result.append(p.val)
                p=p.right
        return result

class Solution:
    def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:
        if not root:
            return None
        elif(root.val>R):
            return self.trimBST(root.left,L,R)
        elif(root.val<L):
            return self.trimBST(root.right,L,R)
        else:         
            root.left=self.trimBST(root.left,L,R)
            root.right=self.trimBST(root.right,L,R)
            return root

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.count=0
        self.res=0
        def in_order(root):
            if not root:
                return
            else:
                in_order(root.left)
                self.count+=1
                if(self.count==k):
                    self.res=root.val
                in_order(root.right)
        in_order(root)
        return self.res

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        self.sum=0
        def in_order(root):
            if root:
                in_order(root.right)
                self.sum+=root.val
                root.val=self.sum
                in_order(root.left)
                return root
        return in_order(root)

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        if(p==root):
            return p
        if(q==root):
            return q
        L=self.lowestCommonAncestor(root.left,p,q)
        R=self.lowestCommonAncestor(root.right,p,q)
        if( L and R):
            return root
        elif not R:
            return L
        else:
            return R

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def mid_build(ele_list,l,r):
            if(l>r):
                return None
            mid=(l+r)>>1
            root=TreeNode(nums[mid])
            root.left=mid_build(ele_list,l,mid-1)
            root.right=mid_build(ele_list,mid+1,r)
            return root
        if not nums:
            return 
        return mid_build(nums,0,len(nums)-1)

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        res_set=set()
        visit=[]
        def in_order(root,target):
            if root:
                if(root.val not in res_set):
                    res_set.add(root.val)
                if(k-root.val in res_set and k!=2*root.val):
                    return True
                L=in_order(root.left,target)
                R=in_order(root.right,target)
                return L or R
        return in_order(root,k)

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        min_value=1000
        res=[]
        stack=[]
        p=root
        while(p or len(stack)):
            if(p):
                stack.append(p)
                p=p.left
            else:
                p=stack.pop()
                if(len(res)):
                    min_value=min(min_value,abs(p.val-res[-1]))
                res.append(p.val)
                p=p.right
        return min_value

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        res_dict={}
        res=[]
        def in_order(root):
            if root:
                in_order(root.left)
                if(root.val not in res_dict):
                    res_dict[root.val]=1
                else:
                    res_dict[root.val]+=1
                in_order(root.right)
        in_order(root)
        if not root:
            return 
        res_list=sorted(res_dict.items(),key=lambda x:x[1],reverse=True)
        num=res_list[0][1]
        res.append(res_list[0][0])
        for ele in res_list[1:]:
            if(ele[1] == num):
                res.append(ele[0])
        return res

class Solution:
    def postorderTraversal(self, root):  #迭代法1
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            # 中结点先处理
            result.append(node.val)
            # 左孩子先入栈
            if node.left:
                stack.append(node.left)
            # 右孩子后入栈
            if node.right:
                stack.append(node.right)
        # 将最终的数组翻转
        return result[::-1]

# 层序遍历的时候加个反向的flag。
class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        # write code here
        if not pRoot: return []
        quene = []
        res = []
        quene.append(pRoot)
        reverseFlag = True
        while quene:
            row = []
            for i in range(len(quene)):
                node = quene.pop(0)
                row.append(node.val)
                if node.left:
                    quene.append(node.left)
                if node.right:
                    quene.append(node.right)
            reverseFlag = not reverseFlag
            if reverseFlag:
                res.append(row[::-1])
            else:
                res.append(row)
        return res

class Solution:

    def inOrderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        return self.inOrderTraversal(root.left) + [root.val] + self.inOrderTraversal(root.right)

    def isValidBST(self , root: TreeNode) -> bool:
        res = self.inOrderTraversal(root)
        if len(res) <= 1:
            return True
        for i in range(len(res)-1):
            if res[i] >= res[i+1]:
                return False
        return True

class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        if root is None:
            return True
        ret = [root]
        while ret:
            cur = ret.pop(0)
            if cur:
                ret.append(cur.left)
                ret.append(cur.right)
            else:
                break
        for i in ret:
            if i:
                return False
        return True

class Solution:
    str1 = []
    def Serialize(self, root):
        # write code here
        if root == None:
            self.str1.append("#")
            return self.str1
        self.str1.append(str(root.val))
        self.Serialize(root.left)
        self.Serialize(root.right)
        return self.str1
    start=-1
    def Deserialize(self, s):
        # write code here
        self.start=self.start+1;
        if self.start>=len(s) or s[self.start]=="#" or s==None :return ;
        cur=TreeNode(int(s[self.start]))
        cur.left=self.Deserialize(s)
        cur.right=self.Deserialize(s)
        return cur

class Solution:
    def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:
        # write code here
        if not pre or not vin:
            return None
        #构造根节点，寻找左右子树的分界线
        root = TreeNode(pre[0])
        n = vin.index(pre[0])
        #构造左右子树，递归调用
        root.left = self.reConstructBinaryTree(pre[1:n + 1], vin[:n])
        root.right = self.reConstructBinaryTree(pre[n + 1:], vin[n + 1:])
        #返回根节点
        return root

 
class Trie:
 
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.word_end = -1
 
    def insert(self, word):
        """
        Inserts a word into the trie.
        """
        curNode = self.root
        for c in word:
            if c not in curNode:
                curNode[c] = {}
            curNode = curNode[c]
        curNode[self.word_end] = True
        # print('==curNode:', curNode)
 
 
    def search(self, word):
        """
        Retu
        rns if the word is in the trie.
        """
        curNode = self.root
        for c in word:
            if c not in curNode:
                return False
            curNode = curNode[c]
        if self.word_end not in curNode:
            return False
        return True
 
 
    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        curNode = self.root
        for c in prefix:
            if c not in curNode:
                return False
            curNode = curNode[c]
        return True
 
word = 'apple'
prefix = 'ad'
obj = Trie()
obj.insert(word='apple')
obj.insert(word='add')
# obj.insert(word='app')
print('tree:', obj.root)
param_2 = obj.search(word)
print('search res:', param_2)
param_3 = obj.startsWith(prefix)
print('==param_3:', param_3)

lass Solution:
    def mySqrt(self, x: int) -> int:
        low,high=0,x
        if x==0 or x==1:
            return x
        while(low<high):
            mid=(low+high)>>1
            val=mid*mid
            val_1=(mid+1)*(mid+1)
            if(val<=x<val_1):
                return mid
            elif(val>=x):
                high=mid
            else:
                low=mid

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        #不需要等于，返回low
        low,high=0,len(letters)-1
        while(low<high):
            mid=(low+high)>>1
            if(target<letters[mid]):
                high=mid-1
            else:
                low=mid+1
        if(letters[low]<=target):
            return letters[(low+1)%len(letters)]    
        return letters[low]

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        low,high=0,len(nums)-1
        while(low<high):
            mid=(low+high)>>1
            if(mid%2):
                mid-=1
            if(nums[mid+1]==nums[mid]):
                low=mid+2
            else:
                high=mid
        return nums[low]

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        low,high=1,n
        while(low<high):
            mid=(low+high)>>1
            if(not isBadVersion(mid)):
                low=mid+1
            else:
                high=mid-1
        if isBadVersion(low):
            return low
        return low+1

class Solution:
    def findMin(self, nums: List[int]) -> int:
        low,high=0,len(nums)-1
        if(len(nums)==1):
            return nums[0]
        while(nums[low]>nums[high]):
            mid=(low+high)>>1
            if(high<low):
                break
            elif(nums[mid]>nums[low]):
                low=mid
            else:
                high=mid
        if(nums[low]<nums[low-1]):
            return nums[low]
        return nums[low+1]

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if(target not in nums):
            return [-1,-1]
        nums=list(map(float,nums))
        def bin_search(nums, target):
            low, high = 0, len(nums) - 1
            while (low < high):
                mid = int((low + high) / 2)
                if (target == nums[mid]):
                    return mid
                elif (target > nums[mid]):
                    low = mid + 1
                else:
                    high = mid - 1
            return low
        a,b=target-0.5,target+0.5
        i,j=bin_search(nums,a),bin_search(nums,b)
        if(nums[i]!=target):
            i=i+1
        if(nums[j]!=target):
            j=j-1
        return [i,j]

class Solution:
    def search(self , nums, target):
        # write code here
        length = len(nums)
        left = 0
        right = length
        if length < 1:
            return -1 
        while  left <= right:
            mid = int((left + right) / 2)
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

class Solution:
    def findPeakElement(self , nums: List[int]) -> int:
        left,right = 0,len(nums)-1
        while left<right:
            mid = (left+right)//2
            if nums[mid] < nums[mid+1]: left = mid+1
            else: right = mid
        return left

def compare(s1, s2):
	s1_val_list, s2_val_list = s1.split('.'),  s2.split('.')
	len_s1, len_s2 = len(s1_val_list), len(s2_val_list)
	max_len = max(len_s1, len_s2)
	if (len_s1 < max_len):
		s1_val_list += [0] * (max_len - len_s1)
	if (len_s2 < max_len):
		s2_val_list += [0] * (max_len - len_s2)
	for i in range(max_len):
		n1 = int(s1_val_list[i])
		n2 = int(s2_val_list[i])
		if(n1 > n2):
			return 1
		if(n1 < n2):
			return 0

versions = ['4.8', '1.7.1', '4.1.9', '5.0.0.0']
for i in range(len(versions)-1, -1, -1):
	for j in range(i):
		if(compare(versions[j], versions[j+1])):
			versions[j], versions[j+1] = versions[j+1], versions[j]

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        #bfs
        queue=[]
        rows,cols=len(grid),len(grid[0])
        if(rows==1 and cols==1 and grid[0][0]==0):
            return 1
        if(grid[0][0]==1 or grid[rows-1][cols-1]==1):
            return -1
        queue.append([0,0])
        level=1
        grid[0][0]=1
        next_step=[[0,1],[1,0],[0,-1],[-1,0],[-1,-1],[1,1],[1,-1],[-1,1]]
        while(queue):
            length=len(queue)
            while(length):
                cur=queue.pop(0)
                x=cur[0]
                y=cur[1]
                length-=1
                if(x==rows-1 and y==cols-1):
                    return level
                for i in range(len(next_step)):
                    x+=next_step[i][0]
                    y+=next_step[i][1]
                    if(x>=0 and x<rows and y>=0 and y<cols and grid[x][y]==0): 
                        queue.append([x,y])
                        grid[x][y]=1
                    else:
                        continue
            level+=1
        return -1

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(grid,i,j):
            if(i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) or grid[i][j]==0):
                return 0
            grid[i][j]=0
            count=1
            count += dfs(grid, i+1, j);
            count += dfs(grid, i-1, j);
            count += dfs(grid, i, j+1);
            count += dfs(grid, i, j-1);
            return count
        max_count=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if(grid[i][j]==0):
                    continue
                else:
                    max_count=max(max_count,dfs(grid,i,j))
        return max_count

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(grid,i,j):
            if(i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) or grid[i][j]=='0' ):
                return
            grid[i][j]='0'
            dfs(grid,i+1,j)
            dfs(grid,i,j+1)
            dfs(grid,i-1,j)
            dfs(grid,i,j-1)
        count=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if(grid[i][j]=='1'):
                    count+=1
                    dfs(grid,i,j)
        return count

class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        #最基本的dfs
        visited=[0]*len(M)
        def dfs(i):
            for j in range(len(M)):
                if(visited[j]==0 and M[i][j]==1):
                    visited[j]=1
                    dfs(j)
        count=0
        for i in range(len(M)):
            if(visited[i]==0):
                count+=1
                dfs(i)
        return count

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        #对边界的那些‘O’进行dfs改变值,t
        def dfs(grad,i,j):
            if(i<0 or i>=len(board) or j<0 or j>=len(board[0]) or board[i][j]!='O'):
                return 
            board[i][j]='-'
            dfs(board,i-1,j)
            dfs(board,i+1,j)
            dfs(board,i,j-1)
            dfs(board,i,j+1)
        for i in range(len(board)):
            for j in range(len(board[0])):
                if((i==0 or i==len(board)-1 or j==0 or j==len(board[0])-1) and board[i][j]=='O'):
                    dfs(board,i,j)
        for i in range(len(board)):
            for j in range(len(board[0])):
                if(board[i][j]=='O'):
                    board[i][j]='X'
                if(board[i][j]=='-'):
                    board[i][j]='O'

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        res=[]
        hash_table={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
        def dfs(index,cur_str):
            if(index==len(digits)):
                res.append(cur_str)
                return
            val=hash_table[digits[index]]
            for i in range(len(val)):
                cur_str=cur_str+val[i]
                dfs(index+1,cur_str)
                cur_str=cur_str[0:-1]
        dfs(0,'')
        return res

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        for i in range(1, 4):
            for j in range(i+1, i + 4):
                for k in range(j+1, j + 4):
                    num_1, num_2, num_3, num_4 = s[0:i], s[i:j], s[j:k], s[k:len(s)]
                    if(len(s)-k>=4):
                        continue
                    try:
                        if((num_1.startswith('0') and len(num_1)!=1) or (num_2.startswith('0') and len(num_2)!=1) or (num_3.startswith('0') and len(num_3)!=1) or (num_4.startswith('0') and len(num_4)!=1)):
                            continue
                        if (0 <= int(num_1) <= 255 and 0 <=int(num_2) <= 255 and 0 <= int(num_3) <= 255 and 0 <= int(num_4) <= 255):
                            res.append(num_1 + '.' + num_2 + '.' + num_3 + '.' + num_4)
                    except:
                        continue
        return res

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.rows,self.cols=len(board),len(board[0])
        def search(i,j,index):
            if(index>=len(word)):
                return True
            if(i>=self.rows or j>=self.cols or i<0 or j<0 or board[i][j]!=word[index]):
                return False
            board[i][j]+='1'#改变之前的，是为了防止同一个单元格的元素多次使用，比如说eae，ea就可以走出eae
            res=(search(i,j+1,index+1) or search(i+1,j,index+1) or search(i,j-1,index+1)or search(i-1,j,index+1))
            board[i][j]=board[i][j][:-1]#改为原来的值
            return res
        for i in range(len(board)):
            for j in range(len(board[0])):
                if(board[i][j]==word[0]):
                    if(search(i,j,0)):
                        return True
        return False

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        #啊哈算法全排列，浅拷贝和深拷贝
        temp_list=[0]*len(nums)
        book=[0]*len(nums)
        res_list=[]
        def dfs(step):
            if(step==len(nums)):
                res_list.append(temp_list.copy())
                return 
            for i in range(len(nums)):
                if(book[i]==0):
                    temp_list[step]=nums[i]
                    book[i]=1
                    dfs(step+1)
                    book[i]=0
        dfs(0)
        return res_list

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        #啊哈算法全排列，浅拷贝和深拷贝
        temp_list=[0]*len(nums)
        book=[0]*len(nums)
        res_list=[]
        def dfs(step):
            if(step==len(nums)):
                res_list.append(temp_list.copy())
                return 
            for i in range(len(nums)):
                if(book[i]==0):
                    temp_list[step]=nums[i]
                    book[i]=1
                    dfs(step+1)
                    book[i]=0
        dfs(0)
        set_list=[]
        for ele in res_list:
            if ele not in set_list:
                set_list.append(ele)
        return set_list

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        temp_val = []
        res_list = []
        def dfs(step):
            if (len(temp_val) == k):
                res_list.append(temp_val.copy())
                return
            else:
                for index in range(step+1, n+1):
                    temp_val.append(index)
                    dfs(index)
                    temp_val.pop()
        dfs(0)
        return res_list

class Solution:
    def recursion(self, string, res, length):
        tmp = "".join(string)
        if len(string) == length:
            res.add(tmp)
            return res
        
        for i in range(len(string)):
            string.insert(i, ')')
            string.insert(i, '(')
            self.recursion(string, res, length)
            string.pop(i)
            string.pop(i)
        
    def generateParenthesis(self , n):
        # write code here
        length = 2*n
        string = ['(',')']
        res = set()
        self.recursion(string, res, length)
        res = list(res)
        return res

class Solution:
    global dirs
    #记录四个方向
    dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]] 
    global n, m
    #深度优先搜索，返回最大单元格数
    def dfs(self, matrix:List[List[int]], dp: List[List[int]], i:int, j:int) :
        if dp[i][j] != 0:
            return dp[i][j]
        dp[i][j] += 1
        for k in range(4):
            nexti = i + dirs[k][0]
            nextj = j + dirs[k][1]
            #判断条件
            if  nexti >= 0 and nexti < n and nextj >= 0 and nextj < m and matrix[nexti][nextj] > matrix[i][j]:
                dp[i][j] = max(dp[i][j], self.dfs(matrix, dp, nexti, nextj) + 1)
        return dp[i][j]
    
    def solve(self , matrix: List[List[int]]) -> int:
        global n,m
        #矩阵不为空
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        res = 0
        n = len(matrix)
        m = len(matrix[0])
        #i，j处的单元格拥有的最长递增路径
        dp = [[0 for col in range(m)] for row in range(n)]  
        for i in range(n):
            for j in range(m):
                #更新最大值
                res = max(res, self.dfs(matrix, dp, i, j)) 
        return res

 
class Solution:
    def canFinish(self, numCourses, prerequisites):
        indegrees = [0] * numCourses  # 入度列表
        print('==indegrees:', indegrees)
        adjacency = [[] for i in range(numCourses)]  # 邻接列表 存储节点的下一个节点
        print('=adjacency:', adjacency)
        #得到入度和每个课程的邻接列表
        for cur, pre in prerequisites:
            indegrees[cur] += 1
            adjacency[pre].append(cur)
        print('====indegrees:', indegrees)
        print('====adjacency:', adjacency)
 
        quene = []
        # 如果度为0　就进入队列
        for i in range(len(indegrees)):
            if indegrees[i] == 0:
                quene.append(i)
        print('==quene:', quene)
        num_nodes = 0
        while quene:
            node = quene.pop(0)
            num_nodes += 1
            for next_node in adjacency[node]:
                indegrees[next_node] -= 1  # 找出下一个点相应的度-1
                if indegrees[next_node] == 0:  # 入度为0
                    quene.append(next_node)
        print('==num_nodes:', num_nodes)
        return num_nodes == numCourses
 

numCourses, prerequisites = 6, [[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]
sol = Solution()
res = sol.canFinish(numCourses, prerequisites)
print('res:', res)

 
class Solution:
    def canFinish(self, numCourses, prerequisites):
        indegrees = [0] * numCourses  # 入度列表
        print('==indegrees:', indegrees)
        adjacency = [[] for i in range(numCourses)]  # 邻接列表
        print('=adjacency:', adjacency)
        #得到入度和每个课程的邻接列表
        for cur, pre in prerequisites:
            indegrees[cur] += 1
            adjacency[pre].append(cur)
        print('====indegrees:', indegrees)
        print('====adjacency:', adjacency)
 
        quene = []
        # 如果度为0　就进入队列
        for i in range(len(indegrees)):
            if indegrees[i] == 0:
                quene.append(i)
        print('==quene:', quene)
        num_nodes = 0
        learn_node = []
        while quene:
            node = quene.pop(0)
            print('=======node', node)
            learn_node.append(node)
            num_nodes += 1
            for next_node in adjacency[node]:
                indegrees[next_node] -= 1  # 找出下一个点相应的度-1
                if indegrees[next_node] == 0:  # 入度为0
                    quene.append(next_node)
        print('==num_nodes:', num_nodes)
        return learn_node if num_nodes == numCourses else []
 
# numCourses, prerequisites = 2, [[1, 0]]
# numCourses, prerequisites = 2, [[1, 0], [0, 1]]
numCourses, prerequisites = 6, [[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]
sol = Solution()
res = sol.canFinish(numCourses, prerequisites)
print('res:', res)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        res=[]
        return_list=[]
        for i in range(len(nums)):
            if((target-nums[i]) in nums and nums.index(target-nums[i])!=i):
                return [i,nums.index(target-nums[i])]
        return []

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        res_set=set()
        for i in range(len(nums)):
            if(nums[i] not in res_set):
                res_set.add(nums[i])
            else:
                return True
        return False

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        res_dict={}
        max_res=0
        for i in range(len(nums)):
            if(nums[i] not in res_dict):
                res_dict[nums[i]]=1
            else:
                res_dict[nums[i]]+=1
        for i in range(1,len(nums)):
            if( (nums[i]-1) in res_dict):
                max_res=max(max_res,res_dict[nums[i]]+res_dict[nums[i]-1])
        return max_res

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        #用set存储然后遍历查找，只往后查找
        ele_set = set()
        max_len = 0
        for ele in nums:
            if (ele not in ele_set):
                ele_set.add(ele)
        for ele in nums:
            if ((ele - 1) not in ele_set):
                cur_num = ele
                temp_len = 0
                while (cur_num in ele_set):
                    temp_len += 1
                    cur_num += 1
                max_len = max(max_len, temp_len)
        return max_len

class Solution:
    def threeSum(self , num: List[int]) -> List[List[int]]:
        # write code here
        if len(num) < 3:
            return []
        help = {}
        res = []
        num = sorted(num)
        for i in range(len(num)-2):
            target = -num[i]
            l = i + 1
            r = len(num) - 1
            while l < r:
                if num[l] + num[r] == target:
                    res.append((num[i], num[l], num[r]))
                    res = list(set(res))
                    l += 1
                elif num[l] + num[r] < target:
                    l += 1
                else:
                    r -= 1
        return res

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s="".join((lambda x:(x.sort(),x)[1])(list(s)))
        t="".join((lambda x:(x.sort(),x)[1])(list(t)))
        if(len(s)!=len(t)):
            return False
        for i in range(len(s)):
            if(s[i]!=t[i]):
                return False
        return True

class Solution:
    def longestPalindrome(self, s: str) -> int:
        count = collections.Counter(s)
        length=0
        for ele in count.values():
            length+=int(ele/2)*2
            if(length%2==0 and ele%2==1):
                length+=1
        return length

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        for i in range(len(s)):
            if(s.find(s[i])==t.find(t[i])):
                continue
            else:
                return False
        return True

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if(x<0):
            return False
        if -1<x<10:
            return True
        s=str(x)
        begin,end=0,len(s)-1
        while(begin<end):
            if(s[begin]!=s[end]):
                return False
            else:
                begin+=1
                end-=1
        return True

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        #从前往后统计每个连续区间相同数字个数
        if(len(s)<2):
            return 0
        count=1
        count_list=[]
        for i in range(1,len(s)):
            if(s[i]==s[i-1]):
                count+=1
            else:
                count_list.append(count)
                count=1
        count_list.append(count)
        if(len(count_list)<2):
            return 0
        sum=0
        for j in range(1,len(count_list)):
            sum+=min(count_list[j],count_list[j-1])
        return sum

class Solution:
    def trans(self , s: str, n: int) -> str:
        # write code here
        s0=[]
        for i in s:
            if i!=' ':
                if i.islower():
                    s0.append(i.upper())
                else:
                    s0.append(i.lower())
            else:
                s0.append(' ')
        s0=''.join(s0).split(' ')
        return ' '.join(s0[::-1])

class Solution:
    def longestCommonPrefix(self , strs: List[str]) -> str:
        # write code here
        if len(strs) == 0:
            return ''
        pre_str = strs[0]
        for string in strs[1:]:
            if pre_str in string:
                continue
            elif string in pre_str:
                pre_str = string
            else:
                while pre_str not in string:
                    pre_str = pre_str[:-1]
        return pre_str

class Solution:
    def solve(self , s: str, t: str) -> str:
        # write code here
        if not s: return t 
        if not t: return s
        res = ''
        carry = 0
        i = len(s) - 1
        j = len(t) - 1
        while i >= 0 or j >= 0:
            n1 = s[i] if i >= 0 else 0
            n2 = t[j] if j >= 0 else 0
            tmp = int(n1) + int(n2) + carry
            carry = tmp // 10
            res = str(tmp % 10) + res
            i -= 1
            j -= 1
        if carry:
            return '1'+res
        else:
            return res

class Solution:
    def ipv4(self, ip: str) -> str:
        flag = True
        for x in ip.split("."):
            if len(x) > 3:
                flag = False
                break
            for xi in x:
                if not "0" <= xi <= "9":
                    flag = False
                    break
            if not flag:
                break
            if x[0] == "0" or int(x) < 0 or int(x) > 255:
                flag = False
                break
        return "IPv4" if flag else "Neither"
    
    def ipv6(self, ip: str) -> str:
        def check(digit):
            try:
                res = int(digit, 16)
                return True
            except Exception:
                return False
        flag = True
        for x in ip.split(":"):
            if not x or len(x) > 4 or not check(x.upper()) or int(x.upper(), 16) < 0 or int(x.upper(), 16) > 65536:
                flag = False
                break
        return "IPv6" if flag else "Neither"
    
    def solve(self , IP: str) -> str:
        # write code here
        if ":" in IP:
            # ip6
            if len(IP.split(":")) != 8: return "Neither"
            return self.ipv6(IP)
        elif "." in IP:
            if len(IP.split(".")) != 4: return "Neither"
            return self.ipv4(IP)
        else:
            return "Neither"

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        count=0
        for ele in nums:
            if(ele!=0):
                count+=1
        k=0
        for i in range(len(nums)):
            if(nums[i]!=0):
                nums[k]=nums[i]
                k+=1
        for i in range(count,len(nums)):
            nums[i]=0

class Solution:
    def matrixReshape(self, nums: List[List[int]], r: int, c: int) -> List[List[int]]:
        if(len(nums)*len(nums[0])<r*c):
            return nums
        new_martix=[]
        row_index,col_index=0,0
        one_row=[]
        for i in range(len(nums)):
            for j in range(len(nums[0])):
                if(col_index<c):
                    one_row.append(nums[i][j])
                    col_index+=1
                else:
                    col_index=0
                    new_martix.append(one_row.copy())
                    one_row=[nums[i][j]]
                    col_index+=1
        new_martix.append(one_row)
        return new_martix

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        if not nums:
            return 0
        count=0
        if(nums[0]==0):
            count=0
        else:
            count=1
        max_count=count
        for i in range(1,len(nums)):
            if(nums[i]==nums[i-1] and nums[i]==1):
                count+=1
                max_count=max(max_count,count)
            elif(nums[i]==1):
                count=1
                max_count=max(max_count,count)

        return max_count

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix:
            return False
        row_index,col_index=0,len(matrix[0])-1
        while(row_index<len(matrix) and col_index >=0 ):
            if(matrix[row_index][col_index]==target):
                return True
            elif(target<matrix[row_index][col_index]):
                col_index-=1
            else:
                row_index+=1
        return False

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
            #其实就是找第一个
            for index in range(len(nums)):
                while(nums[index]!= index+1):
                    #这里终止一定要注意
                    if(nums[index]==nums[nums[index]-1]):
                        break
                    temp=nums[nums[index]-1]
                    nums[nums[index]-1]=nums[index]
                    nums[index]=temp
            for index in range(len(nums)):
                if(nums[index]!= index+1):
                    return [nums[index],index+1]

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        low,high=1,len(nums)-1
        mid=-1
        while(low<high):
            mid=(low+high)>>1
            count=0
            for ele in nums:
                if(ele <= mid):
                    count+=1
            if(count<=mid):
                low=mid+1
            else:
                high=mid
        return low

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        freq,left,right={},{},{}
        for index,ele in enumerate(nums):
            if(ele not in freq):
                freq[ele]=1
                left[ele]=index
            else:
                 freq[ele]+=1
            right[ele]=index
        degree=max(freq.values())
        return min(right[i]-left[i]+1 for i,v in freq.items() if v==degree)
            

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        #只需要判断当前行除了最后一个元素和后一行除了第一个元素是否相等
        rows,cols=len(matrix),len(matrix[0])
        if(rows==1 or cols==1):
            return True
        for index in range(rows-1):
            if(matrix[index][:-1]!=matrix[index+1][1:]):
                return False
        return True

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        #寻找最大长度的环
        max_len=1
        for index in range(len(nums)):
            if(max_len>len(nums)/2):
                return max_len
            start_num=nums[index]
            temp_num=nums[start_num]
            temp_len=1
            while(temp_num!=start_num):
                temp_len+=1
                temp_num=nums[temp_num]
            max_len=max(max_len,temp_len)
        return max_len

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        #当遍历到第i个位置时，如果可以切分为块，那前i个位置的最大值一定等于i。
        #否则，一定有比i小的数划分到后面的块，那块排序后，一定不满足升序。
        max_value,count=-100,0
        for i in range(len(arr)):
            max_value=max(max_value,arr[i])
            if(max_value==i):
                count+=1
        return count

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param matrix int整型二维数组 
# @return int整型一维数组
#
class Solution:
    def spiralOrder(self , matrix: List[List[int]]) -> List[int]:
        # write code here
        if matrix == []:
            return []
        m,n = len(matrix),len(matrix[0])
        up,down = 0,m-1
        left,right = 0,n-1
        res = []
        while left<=right and up<=down:
            for i in range(left,right+1):
                res.append(matrix[up][i])
            up += 1
            if up > down:
                break
            
            for i in range(up,down+1):
                res.append(matrix[i][right])
            right -= 1
            if right < left:
                break

            for i in range(right,left-1,-1):
                res.append(matrix[down][i])
            down -= 1
            if up > down:
                break
            
            for i in range(down,up-1,-1):
                res.append(matrix[i][left])
            left += 1
            if left > right:
                break
        
        return res

class Solution:
    def rotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]:
        for i in range(n):
            for j in range(i):
                temp = mat[i][j]
                mat[i][j] = mat[j][i]
                mat[j][i] = temp
        for i in range(n):
            mat[i].reverse()
        return mat

class Solution:
    def solve(self , n: int, m: int, a: List[int]) -> List[int]:
        m = m % n
        return a[n-m:] + a[:n-m]

# -*- coding:utf-8 -*-
# 不新建数组，类似于冒泡排序
class Solution:
    def reOrderArray(self, array):
        # write code here
        for i in range(0,len(array)):
            for j in range(len(array)-1,i,-1):
                if array[j-1]%2 ==0 and array[j]%2==1:
                    temp = array[j-1]
                    array[j-1] = array[j]
                    array[j] = temp
        return array

# -*- coding:utf-8 -*-
import collections
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        temp = collections.Counter(numbers)
        num = len(numbers)/2
        for k,v in temp.items():
            if v > num:
                return k
        return 0

# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if not numbers:
            return ""
        num=map(str,numbers)
        num.sort(lambda x,y:cmp(x+y,y+x))
        return ''.join(num)

class Solution:
    def multiply(self , A: List[int]) -> List[int]:
        # 初始化数组B
        B = [1 for i in range(len(A))]
        # 先乘左边，从左到右
        for i in range(1, len(A)):
            B[i] = B[i -1] * A[i -1]
        temp = 1
        # 再乘右边，从右到左
        for i in reversed(range(len(A))):
            B[i] *= temp
            temp *= A[i]
        return B

public class Solution {
    public boolean isContinuous(int [] numbers) {
        int[]d = new int[14]; 
        d[0] = -5; 
        int len = numbers.length; 
        if(len==0)
            return false;
        int max = -1; 
        int min = 14; 
        for(int i =0;i<len;i++){
            d[numbers[i]]++; 
            if(numbers[i] == 0){
                continue; 
            }
            if(d[numbers[i]]>1){
                return false; 
            }
            if(numbers[i] >max){
                max = numbers[i]; 
            } 
            if(numbers[i] <min){
                min = numbers[i]; 
            }

        }
        if(max-min<5){
            return true; 
        }
            return false;
        }
}

import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if (m == 0 || n == 0) {
            return -1;
        }
        ArrayList<Integer> data = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            data.add(i);
        }
      int index=0;
      while(data.size()>1){
          index=(index+m-1)%data.size();
          data.remove(index);
      }
      return data.get(0);
    }
}

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
            def quick_sort(nums, l, r, k):
                if (l <=r):
                    temp = nums[l]
                    i, j = l, r
                    while (i != j):
                        while (i < j and temp < nums[j]):
                            j -= 1
                        if (i < j):
                            nums[i] = nums[j]
                            i += 1
                        while (i < j and temp >= nums[i]):
                            i += 1
                        if (i < j):
                            nums[j] = nums[i]
                            j -= 1
                    nums[i] = temp
                    if (i == k - 1):
                        return temp
                    elif (i > k-1):
                        return quick_sort(nums, l, i - 1, k)
                    else:
                        return quick_sort(nums, i + 1, r, k)
            if(k>len(nums)):
                return -1

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        res_dict={}
        res_list=[]
        for ele in nums:
            if(ele not in res_dict):
                res_dict[ele]=1
            else:
                res_dict[ele]+=1
        res=sorted(res_dict.items(),key=lambda x: x[1], reverse=True)
        if(k>len(res)):
            return []
        for index,ele in enumerate(res):
            if(index<k):
                res_list.append(ele[0])
        return res_list

import collections
class Solution:
    def frequencySort(self, s: str) -> str:
        m=collections.Counter(s)
        tmp=[[k,v] for k,v in m.items()]
        tmp.sort(key=lambda x:x[1],reverse=True)
        res=''
        for ele in tmp:
            res=res+ele[0]*ele[1]
        return res
        

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        low,high=0,len(nums)-1
        index=0
        while(index<=high):
            if(nums[index]==0):
                nums[index],nums[low]=nums[low],nums[index]
                low+=1
                index+=1
            elif(nums[index]==1):
                index+=1
            else:
                nums[index],nums[high]=nums[high],nums[index]
                high-=1
        

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        #所有int型整数都是相同位数
        count=0
        while(x or y):
            if((x & 1) != (y & 1)):
                count+=1
            x=x>>1
            y=y>>1
        return count

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #交换律：a ^ b ^ c <=> a ^ c ^ b
        #任何数于0异或为任何数 0 ^ n => n
        #相同的数异或为0: n ^ n => 0
        count=0
        for ele in nums:
            count = count ^ ele
        return count

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res=0
        for ele in range(len(nums)+1):
            res^=ele
        for ele in nums:
            res^=ele
        return res

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        #将数组所有元素进行异或操作
        #找出结果的最高位1，两个数中一个最高位是1，一个是0
        bit_mask=0
        for ele in nums:
            bit_mask ^=ele
        #找到最高位是1的index
        n=len(bin(bit_mask))-3
        i,j=0,0
        for ele in nums:
            if((ele>>n)&1):
                i^=ele
            else:
                j^=ele
        return [i,j]

class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        #n与n-1，如果为0，则是2的幂次方
        if(n<=0):
            return False
        return (n&(n-1))==0

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return num >0 and (num & (num-1)==0) and (num & 0xaaaaaaaa)==0

class Solution(object):
    def hasAlternatingBits(self, n):
        """
        :type n: int
        :rtype: bool
        """
        n=(n ^ (n>>1))
        n=(n&(n+1))
        return n==0
        

class Solution(object):
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        #转换为求掩码过程
        #100000000...作为mask与num相与，找出最高位1
        mask=1<<30
        while((mask & num ==0)):
            mask = mask>>1
        mask=(mask <<1 )-1
        return mask^num 

class Solution(object):
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        # 或|=：两个二进制对应位只要1个为1，结果就是1，否则是0；
        # 与 &=：两个二进制的对应位都为1时，结果为1，否则结果等于0；
        # 异或 ^=：两个二进制的对应位不同，结果为1，否则结果为0。
        value_list=[0]*len(words)
        for i in range(len(words)):
            for char_val in words[i]:
                #向左移动1
                value_list[i] |= 1 << (ord(char_val)-97)
        #只要有一个位置相同，&就不必为0
        return max([len(words[i])*len(words[j]) for i in range(len(words)) for j in range(i+1,len(words)) if not (value_list[i] & value_list[j])] or [0])

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        #动态规划找规律
        #如果是偶数，等于其一半的数中1的数目
        #如果是基数，等于其减去一的数中1的数目
        res=[0]
        for ele in range(1,num+1):
            if(ele %2==0):
                res.append(res[ele/2])
            else:
                res.append(res[ele-1]+1)
        return res

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        # 空链表处理
        if head == None:
            return head
        # 非空链表处理
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        p = ListNode(0)
        p.next = head  # 保证p.next存在
        new_head = p
        cur = None
        i = 1
        while i < n:
            if i < m:
                p = head
                head = head.next
            elif i >= m:
                cur = head.next
                head.next = cur.next  # 保证第n个节点之后的节点不丢失
                cur.next = p.next
                p.next = cur
            i += 1
        return new_head.next

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
class Solution:
    def reverseKGroup(self , head: ListNode, k: int) -> ListNode:
        # write code here
        new_head = ListNode(0)
        new_head.next=head

        c=0
        last=new_head
        cur = new_head
        while cur:
            if c==k:
                cur=self.reverse(last,k)
                last=cur
                c=0
            c+=1

            cur=cur.next
        return new_head.next

    def reverse(self, last, k):
        queue_head=last.next
        for i in range(1, k):
            next=queue_head.next
            queue_head.next=next.next
            next.next=last.next
            last.next=next
        return queue_head

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        h = ListNode(0)
        new = h
        # 为什么要用new？因为h接下来不断在动，new记住了表头！
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                h.next = pHead1
                pHead1 = pHead1.next
            else:
                h.next = pHead2
                pHead2 = pHead2.next
            h = h.next
        else:
            if pHead1:
                h.next = pHead1
            elif pHead2:
                h.next = pHead2
        return new.next

import heapq
class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        vhead = ListNode(-1)
        p = vhead 
        
        heads = [i for i in lists]
        heap = [(n.val,idx) for idx, n in enumerate(lists) if n is not None]
        heapq.heapify(heap)
        
        while heap:
            idx = heapq.heappop(heap)[1] #
            tmp = heads[idx]
            p.next = tmp
            heads[idx] = heads[idx].next
            p = p.next
            if heads[idx]: heapq.heappush(heap,(heads[idx].val, idx)) 
                
        return vhead.next

class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if pHead == None:
            return None
        fast =pHead
        slow = pHead
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        if fast == None&nbs***bsp;fast.next == None:
            return None
        slow = pHead
        while slow != fast:
            slow=slow.next
            fast = fast.next
        return slow

class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int):
        pre = pHead
        suc = pHead
        for i in range(k):
            if suc:
                suc = suc.next
            else:
                return None
        while suc:
            pre = pre.next
            suc = suc.next
        else:
            return pre

class Solution:
    def removeNthFromEnd(self , head, n):
        pre = head
        suc = head
        for i in range(n):
            if suc.next:
                suc = suc.next
            else:
                head = head.next
                return head
        while suc.next:
            pre = pre.next
            suc = suc.next
        else:
            pre.next = pre.next.next
        return head

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # 计算链表长度的函数
        def lenth(pHead: ListNode):
            i = 0
            while pHead:
                i += 1
                pHead = pHead.next
            return i
        
        # 走差值
        l1 = lenth(pHead1)
        l2 = lenth(pHead2)
        if l1 >= l2:
            n = l1-l2
            while n:
                pHead1 = pHead1.next
                n -= 1
        else:
            n = l2-l1
            while n:
                pHead2 = pHead2.next
                n -= 1
     
        # 一起走
        while pHead1:
            if pHead1 == pHead2:
                return pHead1
            else:
                pHead1 = pHead1.next
                pHead2 = pHead2.next
        
        # 没有交点返回空
        return None

class Solution:
    # 反转链表，按照个十百位数顺序相加，carry保存进位数据
    # 时间复杂度：O(n)  空间复杂度：O(1)
    def reverse_list(self, head):
        if not head:
            return None
        cur = head
        pre = None
        while cur:
            temp = cur.next
            cur.next = pre 
            pre = cur
            cur = temp
        return pre 

    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        if not head1:
            return head2
        if not head2:
            return head1
        head1 = self.reverse_list(head1)
        head2 = self.reverse_list(head2)
        res = ListNode(2022)
        head = res
        carry = 0
        while head1 or head2 or carry != 0:
            val1 = 0 if not head1 else head1.val
            val2 = 0 if not head2 else head2.val
            sum_ = val1 + val2 + carry
            carry = sum_ // 10
            temp = sum_ % 10
            head.next = ListNode(temp)
            head = head.next
            if head1:
                head1 = head1.next
            if head2:
                head2 = head2.next
        return self.reverse_list(res.next)

class Solution:
    def sortInList(self , head ):
        # write code here
        list1 = []
        while(head):
            list1.append(head.val)
            head = head.next
        list1.sort()
        temp = ListNode(0)
        pHead = temp
        for i in list1:
            pHead.next = ListNode(i)
            pHead = pHead.next
        return temp.next

class Solution:
    def isPail(self , head):
        res = []
        cur = head 
        while cur:
            res.append(cur.val)
            cur = cur.next
        return res == res[::-1]

class Solution:
    def deleteDuplicates(self , head):
        # write code here
        cur = head
        while cur:
            while cur.next and cur.val == cur.next.val:
                cur.next = cur.next.next
            cur = cur.next
        return head

class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here
        dummy = pre = ListNode(-1)
        while head and head.next:
            if head.val == head.next.val:
                temp = head.val
                while head and head.val == temp:
                    head = head.next
                continue
            else:
                pre.next = head
                pre = pre.next
                head = head.next
        pre.next = head
        return dummy.next

class Solution:
    def Convert(self , pRootOfTree ):
        # write code here
        if not pRootOfTree:return
        #建立左子树的双向链表 返回链表头p
        left=self.Convert(pRootOfTree.left)
        p=left
        #定位到左子树的最右节点
        while left and p.right:
            p=p.right
        #假如存在左子树，和根节点连接成双向链表
        if left:
            p.right=pRootOfTree
            pRootOfTree.left=p 
        #构建右子树的双良链表 
        right=self.Convert(pRootOfTree.right)
        #假如存在柚子树 则和根节点连接成双向链表 
        if right:
            pRootOfTree.right=right 
            right.left=pRootOfTree
        #返回链表
        return left if left else pRootOfTree

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None
        if pNode.right:  #有右子树
            res = pNode.right
            while res.left:
                res = res.left
            return res
        while pNode.next:  #无右子树，则找第一个当前节点是父节点左孩子的节点
            tmp = pNode.next
            if tmp.left == pNode:
                return tmp
            pNode = tmp   #沿着父节点向上遍历
        return None  #到了根节点仍没找到，则返回空