剑指offer

JZ3 数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

from collections import Counter
class Solution:
    def duplicate(self , numbers: List[int]) -> int:
        cnt = Counter(numbers)
        for item in numbers:
            if cnt[item] > 1: return item
        return -1

JZ5 替换空格

请实现一个函数，将一个字符串s中的每个空格替换成“%20”。

例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

class Solution:
    def replaceSpace(self , s: str) -> str:
        s = s.split(' ')
        return '%20'.join(s)

JZ6 从尾到头打印链表

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

#倒序，实质是栈思想
class Solution:
    def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
        lst = []
        while listNode:
            lst.append(listNode.val)
            listNode = listNode.next
        lst.reverse()
        return lst

#递归
import sys
#设置递归深度
sys.setrecursionlimit(100000) 
class Solution:
    def recursion(self, head: ListNode, res: List[int]):
        if head:
            #先往链表深处遍历
            self.recursion(head.next, res) 
            #再填充到数组就是逆序
            res.append(head.val) 
    def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
        res = []
        #递归函数打印
        self.recursion(listNode, res) 
        return res

JZ7 重建二叉树

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

#递归
class Solution:
    def reConstructBinaryTree(self , preOrder: List[int], vinOrder: List[int]) -> TreeNode:
        m, n = len(preOrder), len(vinOrder)
        if m == 0 or n == 0: return
        root = TreeNode(preOrder[0])
        for i in range(n):
            if vinOrder[i] == preOrder[0]:
                leftvin = vinOrder[:i]
                rightvin = vinOrder[i+1:]
                leftpre = preOrder[1:len(leftvin)+1]
                rightpre = preOrder[len(leftvin)+1:]
                root.left = self.reConstructBinaryTree(leftpre,leftvin)
                root.right = self.reConstructBinaryTree(rightpre,rightvin)
        return root

#栈
class Solution:
    def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:
        n = len(pre)
        m = len(vin)
        # 每个遍历都不能为0
        if n == 0 or m == 0: 
            return None
        s = []
        # 首先建立前序第一个即根节点
        root = TreeNode(pre[0]) 
        cur = root
        j = 0
        for i in range(1, n):
            # 要么旁边这个是它的左节点
            if cur.val != vin[j]: 
                cur.left = TreeNode(pre[i])
                s.append(cur)
                cur = cur.left 
            # 要么旁边这个是它的右节点，或者祖先的右节点
            else:
                j += 1
                # 弹出到符合的祖先
                while s and s[-1].val == vin[j]: 
                    cur = s[-1]
                    s.pop()
                    j += 1
                # 添加右节点
                cur.right = TreeNode(pre[i]) 
                cur = cur.right
        return root

JZ8 二叉树的下一个结点

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

class Solution:
    def GetNext(self, pNode):
        if pNode.right:
            cur = pNode.right
            while cur.left: cur = cur.left
            return cur
        else:
            cur = pNode
            while cur.next and cur.next.right == cur: cur = cur.next
            return cur.next

JZ9 用两个栈实现队列

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)

    def pop(self):
        if not self.stack2:
            while self.stack1: self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

JZ10 斐波那契数列

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

class Solution:
    def Fibonacci(self , n: int) -> int:
        if n <= 2: return 1
        a, b = 1, 1
        for _ in range(n-2):
            a, b = b, a+b
        return b

JZ11 旋转数组的最小数字

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

class Solution:
    def minNumberInRotateArray(self , nums: List[int]) -> int:
        l, r = 0, len(nums)-1
        while l < r:
            m = (l+r) // 2
            if nums[m] > nums[r]: l = m + 1
            elif nums[m] < nums[r]: r = m
            else: r -= 1
        return nums[r]

JZ12 矩阵中的路径

请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

class Solution:
    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        if not matrix: return False
        m, n, flag = len(matrix), len(matrix[0]), False
        def dfs(i, j, k):
            nonlocal flag
            if flag: return
            if k == len(word): 
                flag = True
                return
            visit[i][j] = True #标记为已经过
            if i>0 and not visit[i-1][j] and matrix[i-1][j] == word[k]: dfs(i-1, j, k+1)
            if i<m-1 and not visit[i+1][j] and matrix[i+1][j] == word[k]: dfs(i+1, j, k+1)
            if j>0 and not visit[i][j-1] and matrix[i][j-1] == word[k]: dfs(i, j-1, k+1)
            if j<n-1 and not visit[i][j+1] and matrix[i][j+1] == word[k]: dfs(i, j+1, k+1)
            visit[i][j] = False #无路可走，回退，消除标记
            return
        for i in range(m):
            for j in range(n):
                visit = [[False] * n for _ in range(m)]
                if matrix[i][j] == word[0]: dfs(i,j,1)
        return flag

class Solution:
    def dfs(self, matrix: List[List[str]], n: int, m: int, i: int, j: int, word: str, k: int, flag: List[List[bool]]) -> bool:
        if i < 0 or i >= n or j < 0 or j >= m or (matrix[i][j] != word[k]) or flag[i][j]:
            #下标越界、字符不匹配、已经遍历过不能重复
            return False
        #k为记录当前第几个字符
        if k == len(word) - 1:
            return True
        flag[i][j] = True
        #该结点任意方向可行就可
        if (self.dfs(matrix, n, m, i - 1, j, word, k + 1, flag) 
            or self.dfs(matrix, n, m, i + 1, j, word, k + 1, flag) 
            or self.dfs(matrix, n, m, i, j - 1, word, k + 1, flag) 
            or self.dfs(matrix, n, m, i , j + 1, word, k + 1, flag)):
            return True 
        #没找到经过此格的，此格未被占用
        flag[i][j] = False 
        return False

    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        if len(matrix) == 0:
            return False
        n = len(matrix)
        m = len(matrix[0])
        #初始化flag矩阵记录是否走过
        flag = [[False for i in range (m)] for j in range(n)]
        #遍历矩阵找起点
        for i in range(n):
            for j in range(m):
                #通过dfs找到路径
                if self.dfs(matrix, n, m, i, j, word, 0, flag):
                    return True
        return False

JZ13 机器人的运动范围

地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？

class Solution:
    def movingCount(self , threshold: int, rows: int, cols: int) -> int:
        def dfs(i,j):
            if i<0 or i>=rows or j<0 or j>=cols or visit[i][j] or \
               (i%10 + i//10 % 10 + i//100 + j%10 + j//10 % 10 + j//100) > threshold:
                return 0
            visit[i][j] = True
            return dfs(i-1,j) + dfs(i+1,j) + dfs(i,j-1) + dfs(i,j+1) + 1
        visit = [[False] * cols for _ in range(rows)]
        return dfs(0,0)

JZ14 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],…,k[m] 。请问 k[1]k[2]…*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

if n <= 3: return n-1
m, k = n // 3, n % 3
if k == 0: return 3**m
elif k == 1: return 3**(m-1)*4
elif k == 2: return 3**m*2

JZ15 二进制中1的个数

输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。

class Solution:
    def NumberOf1(self , n: int) -> int:
        res = 0
        for _ in range(32):
            if n & 1: res += 1
            n >>= 1
        return res

JZ16 数值的整数次方

实现函数 double Power(double base, int exponent)，求base的exponent次方。

注意：

1.保证base和exponent不同时为0。

2.不得使用库函数，同时不需要考虑大数问题

3.有特殊判题，不用考虑小数点后面0的位数。

class Solution:
    def Power(self , base: float, exponent: int) -> float:
        res = 1
        if exponent < 0:
            base, exponent = 1/base, -exponent
        for _ in range(exponent):
            res *= base
        return res

JZ17 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

1. 用返回一个整数列表来代替打印
2. n 为正整数，0 < n <= 5

class Solution:
    def printNumbers(self , n: int) -> List[int]:
        res = [i for i in range(1,10**n)]
        return res

JZ18 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

1.此题对比原题有改动

2.题目保证链表中节点的值互不相同

3.该题只会输出返回的链表和结果做对比，所以若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

class Solution:
    def deleteNode(self , head: ListNode, val: int) -> ListNode:
        if head.val == val: return head.next #判断头节点
        cur = head
        while cur.next.val != val: cur = cur.next
        cur.next = cur.next.next
        return head

JZ20 表示数值的字符串

请实现一个函数用来判断字符串str是否表示数值（包括科学计数法的数字，小数和整数）。

科学计数法的数字(按顺序）可以分成以下几个部分:

1.若干空格

2.一个整数或者小数

3.（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个整数(可正可负)

4.若干空格

小数（按顺序）可以分成以下几个部分：

1.若干空格

2.（可选）一个符号字符（‘+’ 或 ‘-’）

\3. 可能是以下描述格式之一:

3.1 至少一位数字，后面跟着一个点 ‘.’

3.2 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字

3.3 一个点 ‘.’ ，后面跟着至少一位数字

4.若干空格

整数（按顺序）可以分成以下几个部分：

1.若干空格
2.（可选）一个符号字符（‘+’ 或 ‘-’)

\3. 至少一位数字

4.若干空格

#有限状态机
class Solution:
    def isNumeric(self , str ):
        state = [{' ':0, 's':1, 'd':2, '.':4},
                 {'d':2, '.':4},
                 {'d':2, '.':3, 'e':5, ' ':8},
                 {'d':3, 'e':5, ' ':8},
                 {'d':3},
                 {'s':6, 'd':7},
                 {'d':7},
                 {'d':7, ' ':8},
                 {' ':8}]
        p = 0
        for c in str:
            if '0' <= c <= '9': t = 'd'
            elif c in '+-': t = 's'
            elif c in 'Ee': t = 'e'
            elif c in '. ': t = c
            else: t = '?'
            if t not in state[p]: return False
            p = state[p][t]
        return p in [2,3,7,8]

JZ21 调整数组顺序使奇数位于偶数前面(一)

输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

#时间O(N),空间O(N)
class Solution:
    def reOrderArray(self , array: List[int]) -> List[int]:
        odd, even = [], []
        for m in array:
            if m % 2: odd.append(m)
            else: even.append(m)
        return odd + even

#时间O(N2),空间O(1)
class Solution:
    def reOrderArray(self , array: List[int]) -> List[int]:
        i = 0
        while i < len(array):
            if array[i] % 2:
                while i>0 and array[i-1] % 2 == 0:
                    array[i-1], array[i] = array[i], array[i-1]
                    i -= 1
            i += 1
        return array

JZ22 链表中倒数最后k个结点

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

#单指针
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        node_num = 0
        cur = pHead
        while cur:
            node_num += 1
            cur = cur.next
        if node_num < k: return None
        for _ in range(node_num-k): pHead = pHead.next
        return pHead

#双指针
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        cur = pHead
        for _ in range(k):
            if not cur: return None
            cur = cur.next
        while cur:
            cur = cur.next
            pHead = pHead.next
        return pHead

#栈
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        stk = []
        while pHead:
            stk.append(pHead)
            pHead = pHead.next
        if len(stk) < k: return
        cur = None
        for _ in range(k):
            cur = stk.pop()
        return cur

JZ23 链表中环的入口结点

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

class Solution:
    def EntryNodeOfLoop(self, pHead):
        fast = slow = pHead
        while fast and fast.next: #快慢指针
            fast = fast.next.next
            slow = slow.next
            if fast == slow: 
                fast = pHead #将快指针移到头结点，一起走a步到入口处
                break
        else: return
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast 

JZ24 反转链表

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        pre, tmp =  None, head
        while head:
            head = head.next
            tmp.next = pre
            pre = tmp
            tmp = head
        return pre

JZ25 合并两个排序的链表

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        if not pHead1 and not pHead2:return
        if not pHead2: return pHead1
        if not pHead1: return pHead2
        if pHead1.val > pHead2.val: pHead1, pHead2 = pHead2, pHead1 #保持1链条头节点更小
        pre = cur = pHead1
        pHead1 = pHead1.next
        while pHead1 or pHead2:
            if pHead1 and (not pHead2 or pHead1.val <= pHead2.val):
                cur.next = pHead1
                pHead1 = pHead1.next
            elif pHead2 and (not pHead1 or pHead1.val > pHead2.val):
                cur.next = pHead2
                pHead2 = pHead2.next
            cur = cur.next
        return pre

JZ26 树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）

class Solution:
    def recur(self,a,b): #判断同根树b是否为a的子结构
        if not b: return True #如果b为空，则b过了叶层，返回True
        elif not a or a.val != b.val: return False #如果a为空b不为空，则a过了叶层b没有，返回False
        else: return self.recur(a.left,b.left) and self.recur(a.right,b.right) #都不为空递归左右子树

    def HasSubtree(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool:
        return bool(pRoot1 and pRoot2) and (self.recur(pRoot1, pRoot2) or \
               self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2))

JZ27 二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        def dfs(root):
            if not root: return
            root.left, root.right = root.right, root.left
            dfs(root.left)
            dfs(root.right)
        dfs(pRoot)
        return pRoot

JZ29 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字

class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        if not matrix: return []
        l, r, t, b = 0, len(matrix[0])-1, 0, len(matrix)-1
        res = []
        i = j = 0
        while True:
            for j in range(l,r+1): res.append(matrix[i][j])
            t += 1
            if t > b: break
            for i in range(t,b+1): res.append(matrix[i][j])
            r -= 1
            if l > r: break
            for j in range(r,l-1,-1): res.append(matrix[i][j])
            b -= 1
            if t > b: break
            for i in range(b,t-1,-1): res.append(matrix[i][j])
            l += 1
            if l > r: break
        return res

JZ30 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：

push(value):将value压入栈中

pop():弹出栈顶元素

top():获取栈顶元素

min():获取栈中最小元素

class Solution:
    def __init__(self):
        self.stk = []
        self.min_stk = []

    def push(self, node):
        self.stk.append(node)
        if not self.min_stk or node <= self.min_stk[-1]: self.min_stk.append(node)
        
    def pop(self):
        if self.min_stk[-1] == self.stk[-1]: self.min_stk.pop()
        return self.stk.pop()

    def top(self):
        return self.stk[-1]
        
    def min(self):
        return self.min_stk[-1]

JZ31 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

class Solution:
    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        stk, i = [], 0
        for num in pushV:
            stk.append(num)
            while stk and stk[-1] == popV[i]:
                stk.pop()
                i += 1
        return not stk

JZ32 从上往下打印二叉树

不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。

from collections import deque
class Solution:
    def PrintFromTopToBottom(self , root: TreeNode) -> List[int]:
        #BFS
        if not root: return []
        queue, res = deque([root]), []
        while queue:
            node = queue.popleft()
            res.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        return res

JZ33 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同

class Solution:
    def VerifySquenceOfBST(self , sequence: List[int]) -> bool:
        #分治思想
        if not sequence: return False
        def recur(sequence):
            n = len(sequence)
            if n <= 2: return True
            p = 0
            while sequence[p] < sequence[-1]: p += 1
            m = p
            while sequence[p] > sequence[-1]: p += 1
            return p == n-1 and recur(sequence[:m]) and recur(sequence[m:n-1])
        return recur(sequence)

JZ35 复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        if not pHead: return
        pre = cur = RandomListNode(pHead.label) #pre作为头节点，cur复制pHead
        ran = pHead #加上随机指针
        while cur:
            pHead = pHead.next
            ran = ran.random
            if pHead: 
                tmp = RandomListNode(pHead.label)
                cur.next = tmp
            else: cur.next = None
            if ran:
                tmp = RandomListNode(ran.label)
                cur.random = tmp
            else: cur.random = None
            cur = cur.next
            ran = pHead
        return pre

JZ36 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表

class Solution:
    def Convert(self , pRootOfTree ):
        def dfs(cur): #中序遍历
            if not cur: return
            dfs(cur.left)
            if self.pre:
                self.pre.right = cur
                cur.left = self.pre
            else: self.head = cur #头节点
            self.pre = cur
            dfs(cur.right)
        if not pRootOfTree: return
        self.pre = None #前节点
        dfs(pRootOfTree)
        return self.head

JZ37 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

from collections import deque
class Solution:
    def Serialize(self, root):
        if not root: return
        queue, res = deque([root]), []
        while queue:
            node = queue.popleft()
            if node:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else: queue.append('#')
        return ' '.join(res)
        
    def Deserialize(self, s):
        if not s: return
        s, i = s.split(), 1
        root = TreeNode(int(s[0]))
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if s[i] != '#':
                node.left = TreeNode(int(s[i]))
                queue.append(node.left)
            i += 1
            if s[i] != '#':
                node.right = TreeNode(int(s[i]))
                queue.append(node.right)
            i += 1
        return root

JZ38 字符串的排列

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

class Solution:
    def Permutation(self , str: str) -> List[str]:
        def dfs(x):
            if x == len(str)-1:
                res.append(''.join(str))
                return
            dic = set() #防止重复
            for i in range(x,len(str)):
                if str[i] in dic: continue #重复则跳过
                dic.add(str[i]) 
                str[x], str[i] = str[i], str[x] #交换,把i固定在x位
                dfs(x+1) #递归后续
                str[x], str[i] = str[i], str[x] #还原
        res = []
        str = list(str)
        dfs(0)
        return res

JZ39 数组中出现次数超过一半的数字

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        res, cnt = -1, 0
        for num in numbers:#抵消法
            if cnt == 0: res = num
            if num == res: cnt += 1
            else: cnt -= 1           
        return res

JZ40 最小的K个数

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

#堆
import heapq
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        res = []
        heapq.heapify(input)
        for _ in range(k):
            res.append(heapq.heappop(input))
        return res

JZ41 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

import heapq
class Solution:
    def __init__(self):
        self.large = [] #用最小堆储存大数
        self.small = [] #用最大堆储存小数

    def Insert(self, num):
        if not self.large: self.large.append(num)
        elif len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappushpop(self.large, num))
        elif len(self.large) == len(self.small):
            heapq.heappush(self.large, -heapq.heappushpop(self.small, -num))

    def GetMedian(self):
        if len(self.large) > len(self.small): return self.large[0]
        else: return (self.large[0] -self.small[0]) / 2

JZ43 整数中1出现的次数（从1到n整数中1出现的次数）

输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数
例如， 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次

#暴力求解 时间 nlog_10(n) 空间 1
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        res = 0
        for num in range(1,n+1): 
            while num:
                if num % 10 == 1: res += 1
                num //= 10
        return res

#数位求解
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        digit, res = 1, 0
        h, c, l = n//10, n%10, 0
        while h or c:
            if c == 0: res += h * digit
            elif c == 1: res += h * digit + l + 1
            else: res += (h+1) * digit
            l += c * digit
            c = h % 10
            h //= 10
            digit *= 10
        return res

JZ44 数字序列中某一位的数字

数字以 0123456789101112131415… 的格式作为一个字符序列，在这个序列中第 2 位（从下标 0 开始计算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此类题，请你输出第 n 位对应的数字。

class Solution:
    def findNthDigit(self , n: int) -> int:
        res, digit = 0, 0
        while res < n:
            digit += 1
            res += 9 * digit * 10**(digit-1)
        x, y = (res-n) // digit, (res-n) % digit
        pur =  10**digit - x - 1
        return int(str(pur)[-1-y])

JZ45 把数组排成最小的数

输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。

1.输出结果可能非常大，所以你需要返回一个字符串而不是整数
2.拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

#冒泡排序
class Solution:
    def PrintMinNumber(self , numbers: List[int]) -> str:
        n = len(numbers)
        for k in range(n):
            numbers[k] = str(numbers[k])
        for i in range(n-1):
            for j in range(n-i-1):
                if int(numbers[j]+numbers[j+1]) > int(numbers[j+1]+numbers[j]):
                    numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
        return ''.join(numbers)

#匿名函数
import functools
class Solution:
    def PrintMinNumber(self , numbers: List[int]) -> str:
        #空数组的情况
        if not numbers:
            return ""
        #将数字转成字符
        nums = list(map(str, numbers))
        #重载比较大小
        cmp = lambda a, b: 1 if a + b > b + a else -1
        #排序
        nums.sort(key = functools.cmp_to_key(cmp))
        #字符串叠加
        return "".join(nums)

JZ46 把数字翻译成字符串

有一种将字母编码成数字的方式：‘a’->1, ‘b->2’, … , ‘z->26’。

现在给一串数字，返回有多少种可能的译码结果

class Solution:
    def solve(self , nums: str) -> int:
        nums = '0' + nums
        dp = [0] * (len(nums))
        dp[0] = 1
        for i in range(1,len(nums)):
            if nums[i] == '0':
                if nums[i-1] not in '12': return 0
                else: dp[i] = dp[i-2]
                continue   
            if 11 <= int(nums[i-1:i+1]) <= 26:
                dp[i] = dp[i-2] + dp[i-1]
            else: dp[i] = dp[i-1]
        return dp[-1]

JZ47 礼物的最大价值

class Solution:
    def maxValue(self , grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for j in range(1,n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        for i in range(1,m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
            for j in range(1,n):
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[-1][-1]

JZ48 最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

#动态规划字符串
class Solution:
    def lengthOfLongestSubstring(self , s: str) -> int:
        dp = [''] * len(s)
        dp[0] = s[0]
        res = 1
        for i in range(1,len(s)):
            if s[i] in dp[i-1]:
                dp[i] = dp[i-1][dp[i-1].find(s[i])+1:] + s[i]
            else: dp[i] = dp[i-1] + s[i]
            res = max(res, len(dp[i]))
        return res

#动态规划+哈希表
class Solution:
    def lengthOfLongestSubstring(self , s: str) -> int:
        dp = [0] * len(s)
        dp[0] = 1
        mp = {s[0]:0}
        res = 1
        for i in range(1,len(s)):
            if s[i] not in mp:
                dp[i] = dp[i-1] + 1
            else:
                dp[i] = min(dp[i-1] + 1, i - mp[s[i]])
            mp[s[i]] = i
            res = max(res, dp[i])
        return res

#滑动窗口+哈希表
class Solution:
    def lengthOfLongestSubstring(self , s: str) -> int:
        res = 0
        i = j = 0
        mp = {}
        while j < len(s):
            if s[j] in mp:
                mp[s[j]] += 1
            else: mp[s[j]] = 1
            while mp[s[j]] > 1:
                mp[s[i]] -= 1
                i += 1
            res = max(res, j - i + 1)
            j += 1
        return res

JZ49 丑数

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。

class Solution:
    def GetUglyNumber_Solution(self , index: int) -> int:
        if index == 0: return 0
        dp = [1] * (index)
        a = b = c = 0 #三个指针对应乘2、3、5
        for i in range(1,index):
            n2, n3, n5 = 2*dp[a], 3*dp[b], 5*dp[c]
            dp[i] = min(n2, n3, n5)
            if dp[i] == n2: a += 1 #说明没有其他情况更小，所以指针前进一位
            if dp[i] == n3: b += 1
            if dp[i] == n5: c += 1
        return dp[-1]

#哈希表 时间N，空间N
class Solution:
    def FirstNotRepeatingChar(self , str: str) -> int:
        mp = {}
        for s in str:
            if s not in mp: mp[s] = 1
            else: mp[s] += 1
        for i in range(len(str)):
            if mp[str[i]] == 1: return i
        return -1   
    
#Counter 时间N，空间N
from collections import Counter
class Solution:
    def FirstNotRepeatingChar(self , str: str) -> int:
        cnt = Counter(str)
        for i in range(len(str)):
            if cnt[str[i]] == 1: return i
        return -1    

#暴力，时间N2，空间N，如果用哈希表储存位置的话，时间同样是N
class Solution:
    def FirstNotRepeatingChar(self , str: str) -> int:
        rec = set()
        for i in range(len(str)):
            if str[i] not in str[i+1:] and str[i] not in rec: return i
            else: rec.add(str[i])
        return -1

JZ51 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007

class Solution: #归并排序
    def InversePairs(self , nums: List[int]) -> int:
        def mergesort(l,r):
            if l >= r: return 0
            m = (l+r) // 2
            res = mergesort(l,m) + mergesort(m+1,r)
            tmp = nums[l:r+1]
            i, j = 0, m-l+1
            for k in range(l,r+1):
                if i == m-l+1:
                    nums[k] = tmp[j]
                    j += 1
                elif j == r-l+1 or tmp[i] <= tmp[j]:
                    nums[k] = tmp[i]
                    i += 1
                else:
                    nums[k] = tmp[j]
                    j += 1
                    res = (res + m-l-i+1) % 1_000_000_007
            return res
        return mergesort(0,len(nums)-1)

JZ52 两个链表的第一个公共结点

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

#都走一遍，看看长度，然后再找节点
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        if not pHead1 or not pHead2: return
        def dfs(root):
            num = 0
            while root.next:
                num += 1
                root = root.next
            return num
        gap = dfs(pHead1) - dfs(pHead2)
        if gap < 0: pHead1, pHead2 = pHead2, pHead1
        for _ in range(abs(gap)):
            pHead1 = pHead1.next
        while pHead1 and pHead2 and pHead1 != pHead2:
            pHead1 = pHead1.next
            pHead2 = pHead2.next
        return pHead1

#哈希表
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        if not pHead1 or not pHead2: return
        stk = []
        while pHead1:
            stk.append(pHead1)
            pHead1 = pHead1.next
        while pHead2:
            if pHead2 in stk: break
            pHead2 = pHead2.next
        return pHead2

#双指针
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        if not pHead1 or not pHead2: return
        cur1, cur2 = pHead1, pHead2
        while cur1 != cur2:
            if not cur1: cur1 = pHead2
            else: cur1 = cur1.next
            if not cur2: cur2 = pHead1
            else: cur2 = cur2.next
        return cur1

JZ53 数字在升序数组中出现的次数

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

#使用bisect_left
import bisect
class Solution:
    def GetNumberOfK(self , nums: List[int], k: int) -> int:
        return bisect.bisect(nums,k) - bisect.bisect_left(nums,k)

#直接找比k-0.5大的
import bisect
class Solution:
    def GetNumberOfK(self , nums: List[int], k: int) -> int:
        return bisect.bisect(nums,k) - bisect.bisect(nums,k-0.5)

class Solution:
    def GetNumberOfK(self , nums: List[int], k: int) -> int:
        if len(nums) == 1:
            if nums[0] == k: return 1
            else: return 0
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l+r) // 2
            if nums[m] < k + 0.5: l = m+1
            elif nums[m] > k + 0.5: r = m-1
        j = l
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l+r) // 2
            if nums[m] < k - 0.5: l = m+1
            elif nums[m] > k - 0.5: r = m-1
        return j - l

JZ54 二叉搜索树的第k个节点

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。

1.返回第k小的节点值即可

2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1

3.保证n个节点的值不一样

class Solution:
    def KthNode(self , proot: TreeNode, k: int) -> int:
        def dfs(root):
            nonlocal k, res
            if not root or k < 0: return
            dfs(root.left)
            k -= 1
            if k == 0: res = root.val
            dfs(root.right)
        res = -1
        dfs(proot)
        return res

JZ55 二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，根节点的深度视为 1 。

class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        # 空节点没有深度
        if not root: 
            return 0
        # 返回子树深度+1
        return max([self.maxDepth(root.left), self.maxDepth(root.right)]) + 1

class Solution:
    def TreeDepth(self , pRoot: TreeNode) -> int:
        def dfs(root):
            nonlocal res, dep
            if not root:
                res = max(res, dep)
                return
            dep += 1
            dfs(root.left)
            dfs(root.right)
            dep -= 1
        res = dep = 0
        dfs(pRoot)
        return res

JZ56 数组中只出现一次的两个数字

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

class Solution:
    def FindNumsAppearOnce(self , nums: List[int]) -> List[int]:
        mp = {}
        for num in nums:
            if num in mp: del mp[num]
            else: mp[num] = 1
        res = []
        for num in mp.keys():
            res.append(num)
        res.sort()
        return res

#异或运算
class Solution:
    def FindNumsAppearOnce(self , nums: List[int]) -> List[int]:
        tmp = 0
        for num in nums: tmp ^= num
        k = 1
        while k & tmp == 0:
            k <<= 1
        res = [0, 0]
        for num in nums:
            if k & num: res[0] ^= num
            else: res[1] ^= num
        res.sort()
        return res

JZ57 和为S的两个数字

输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。

class Solution:
    def FindNumbersWithSum(self , array: List[int], sum: int) -> List[int]:
        i, j = 0, len(array)-1
        while i < j:
            if array[i] + array[j] > sum: j -= 1
            elif array[i] + array[j] < sum: i += 1
            else: return [array[i],array[j]]
        return []

JZ58 左旋转字符串

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列 S ，请你把其循环左移 K 位后的序列输出。例如，字符序列 S = ”abcXYZdef” , 要求输出循环左移 3 位后的结果，即 “XYZdefabc”

class Solution:
    def LeftRotateString(self , str: str, n: int) -> str:
        if not str: return ''
        n = n % len(str)
        return str[n:] + str[:n]

JZ59 滑动窗口的最大值

给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。

from collections import deque
class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        if size == 0: return
        que = deque()
        res = []
        i = j = 0
        while j < len(num):
            while que and que[-1] < num[j]: que.pop()
            if not que or que[-1] >= num[j]: que.append(num[j])
            if j >= size-1:
                res.append(que[0])
                if que[0] == num[i]: que.popleft()
                i += 1
            j += 1
        return res

JZ61 扑克牌顺子

现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：
\1. A为1，J为11，Q为12，K为13，A不能视为14
\2. 大、小王为 0，0可以看作任意牌
\3. 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
4.数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]

class Solution:
    def IsContinuous(self , numbers: List[int]) -> bool:
        lst = []
        for num in numbers:
            if num != 0: lst.append(num)
        if len(set(lst)) < len(lst): return False
        if max(lst) - min(lst) > 4: return False
        return True

JZ62 孩子们的游戏(圆圈中最后剩下的数)

每年六一儿童节，牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。其中，有个游戏是这样的：首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续0… m-1报数…这样下去…直到剩下最后一个小朋友，可以不用表演，并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢？

class Solution:
    def LastRemaining_Solution(self , n: int, m: int) -> int:
        x = 0 #约瑟夫环
        for i in range(2,n+1): #第i次代表第i个小朋友
            x = (x + m) % i
        return x

JZ64 求1+2+3+…+n

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

class Solution:
    def Sum_Solution(self, n):
        return n * (n+1) // 2

JZ65 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

class Solution:
    def Add(self , num1: int, num2: int) -> int:
        while num1: #进位都为0时终止
            #将python中的数变为32位数
            num1, num2 = ((num1 & num2) << 1) & 0xffffffff , (num1 ^ num2) & 0xffffffff  #分别为进位和原位
        return num2  if num2 <= 0x7fffffff else ~(num2 ^ 0xffffffff) #将32位数变为python中的数

JZ66 构建乘积数组

给定一个数组 A[0,1,…,n-1] ,请构建一个数组 B[0,1,…,n-1] ,其中 B 的元素 B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]（除 A[i] 以外的全部元素的的乘积）。程序中不能使用除法。（注意：规定 B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2]）

对于 A 长度为 1 的情况，B 无意义，故而无法构建，用例中不包括这种情况。

#暴力
class Solution:
    def multiply(self , A: List[int]) -> List[int]:
        n = len(A)
        B = [1] * n
        for i in range(n):
            for j in range(n):
                if j != i:
                    B[i] *= A[j]
        return B

#上下三角
class Solution:
    def multiply(self , A: List[int]) -> List[int]:
        n = len(A)
        B = [1] * n
        for i in range(1,n):
            B[i] = B[i-1] * A[i-1]
        for i in range(n-2,-1,-1):
            B[i] *= A[i+1]
            A[i] *= A[i+1]
        return B

JZ68 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.

2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值

3.所有节点的值都是唯一的。

4.p、q 为不同节点且均存在于给定的二叉搜索树中。

class Solution:
    def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
        if not root: return 
        if p <= root.val <= q or q <= root.val <= p: return root.val
        else: return self.lowestCommonAncestor(root.left,p,q) or \
                     self.lowestCommonAncestor(root.right,p,q)

JZ69 跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

class Solution:
    def jumpFloor(self , number: int) -> int:
        if number == 1: return 1
        a, b = 1, 1
        for _ in range(number-1):
            a, b = b, a+b
        return b

JZ70 矩形覆盖

我们可以用 21 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 21 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法？

class Solution:
    def rectCover(self, number):
        if number <= 1: return number
        x, y = 1, 1
        for _ in range(number-1):
            x, y = y, x+y
        return y

JZ71 跳台阶扩展问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

class Solution:
    def jumpFloorII(self , number: int) -> int:
        dp = [0] * (number+1)
        dp[0] = 1
        for i in range(1,number+1):
            for j in range(i):
                dp[i] += dp[j]
        return dp[-1]

JZ73 翻转单词序列

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

#python便捷写法
class Solution:
    def ReverseSentence(self , str: str) -> str:
        lst = str.split()[::-1]
        return ' '.join(lst)

#双指针
class Solution:
    def ReverseSentence(self , str: str) -> str:
        if not str: return ''
        n = len(str)
        lst = []
        i = j = 0
        while i < n:
            while str[i] == ' ': i += 1
            j = i
            while j < n-1 and str[j+1] != ' ':  j += 1
            lst.append(str[i:j+1])
            i = j+1
        res = ''
        for _ in range(len(lst)-1):
            res += lst.pop() + ' '
        return res + lst.pop()

JZ74 和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?

#暴力
class Solution:
    def FindContinuousSequence(self , sum: int) -> List[List[int]]:
        res = []
        for i in range(1, sum//2 + 1):
            s = sum
            lst = []
            while s > 0:
                lst.append(i)
                s -= i
                i += 1
            if s == 0: res.append(lst)
        return res

#滑动窗口
class Solution:
    def FindContinuousSequence(self , sum: int) -> List[List[int]]:
        res = []
        i, j = 1, 2
        r = sum//2 + 1
        while i <= r and j <= r:
            s = (i+j)*(j+1-i)//2
            if s == sum:
                res.append([_ for _ in range(i,j+1)])
                i += 1
            elif j <= r-1 and  s < sum: j += 1
            else: i += 1
        return res

JZ75 字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 “go” 时，第一个只出现一次的字符是 “g” 。当从该字符流中读出前六个字符 “google" 时，第一个只出现一次的字符是"l"。

数据范围：字符串长度满足 1≤�≤1000 1≤n≤1000 ，字符串中出现的字符一定在 ASCII 码内。
进阶：空间复杂度 �(�) O(n) ，时间复杂度 �(�) O(n)

后台会用以下方式调用 Insert 和 FirstAppearingOnce 函数

string caseout = “”;

1.读入测试用例字符串casein

2.如果对应语言有Init()函数的话，执行Init() 函数

3.循环遍历字符串里的每一个字符ch {

Insert(ch);

caseout += FirstAppearingOnce()

}

\2. 输出caseout，进行比较。

如果当前字符流没有存在出现一次的字符，返回#字符。

class Solution:
    def __init__(self):
        self.char = ''
        self.cnt = {}
        self.n = 0
    
    def FirstAppearingOnce(self):
        while self.n < len(self.char) and self.cnt[self.char[self.n]] > 1: self.n += 1
        return self.char[self.n] if self.n < len(self.char) else '#'
    
    def Insert(self, char):
        if char in self.cnt:
            self.cnt[char] += 1
        else: 
            self.cnt[char] = 1
            self.char += char

JZ76 删除链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5

#直接删除，无序列表可以考虑哈希表
class Solution:
    def deleteDuplication(self , pHead: ListNode) -> ListNode:
        if not pHead: return
        head = ListNode(0)
        head.next = pHead
        tail = head
        while tail.next and tail.next.next:  
            if tail.next.val == tail.next.next.val:
                val = tail.next.val
                #跳过所有重复值
                while tail.next and tail.next.val == val:
                    tail.next = tail.next.next
            else: tail = tail.next
        return head.next

JZ78 把二叉树打印成多行

给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。

#层级遍历
from collections import deque
class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        if not pRoot: return []
        qe = deque([pRoot])
        res = []
        while qe:
            lst = []
            for _ in range(len(qe)):
                node = qe.popleft()
                lst.append(node.val)
                if node.left: qe.append(node.left)
                if node.right: qe.append(node.right)
            res.append(lst)
        return res

JZ79 判断是不是平衡二叉树

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

#自上而下
class Solution:
    def height(self,pRoot):
        if not pRoot: return 0
        return max(self.height(pRoot.left), self.height(pRoot.right)) + 1

    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        if not pRoot: return True
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right) and\
               abs(self.height(pRoot.left) - self.height(pRoot.right)) <= 1

#自下而上
class Solution:
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        def height(pRoot):
            if not pRoot: return 0
            left = height(pRoot.left)
            if left < 0: return -1
            right = height(pRoot.right)
            if right < 0: return -1
            return -1 if abs(left-right)>1 else 1 + max(left,right)
        return height(pRoot) != -1

JZ81 调整数组顺序使奇数位于偶数前面(二)

输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。

class Solution:
    def reOrderArrayTwo(self , array: List[int]) -> List[int]:
        i, j = 0, len(array)-1
        while i < j:
            while i < j and array[i] % 2 == 1: i += 1
            while i < j and array[j] % 2 == 0: j -= 1
            array[i], array[j] = array[j], array[i]
        return array

JZ83 剪绳子（进阶版）

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],…,k[m] 。请问 k[1]k[2]…*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

由于答案过大，请对 998244353 取模。

#快速幂
class Solution:
    def cutRope(self , number: int) -> int:
        if number <= 3: return number - 1

        def quickpow(a, b):
            res = 1
            while b:
                if b % 2: res = res * a % 998244353
                b >>= 1
                a = a*a % 998244353
            return res

        x, y = number // 3, number % 3
        if y == 0: return quickpow(3,x)
        elif y == 1: return quickpow(3,x-1) * 4 % 998244353
        else: return quickpow(3,x) * 2 % 998244353

JZ84 二叉树中和为某一值的路径(三)

给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。

1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点

2.总节点数目为n

3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)

#两次遍历
class Solution:
    def __init__(self):
        self.path = 0

    def FindPath(self , root: TreeNode, sum: int) -> int:
        def treesum(root,sum):
            if not root: return
            sum -= root.val
            if sum == 0: self.path += 1
            treesum(root.left,sum)
            treesum(root.right,sum)
            sum += root.val
            return
        
        def dfs(root,sum):
            if not root: return
            treesum(root,sum)
            dfs(root.left,sum)
            dfs(root.right,sum)

        dfs(root,sum)
        return self.path

#一次遍历+哈希表
class Solution:
    def __init__(self):
        #记录路径和及条数
        self.mp = dict()
        
    #last为到上一层为止的累加和
    def dfs(self, root: TreeNode, sum: int, last: int) -> int:
        #空结点直接返回
        if root is None: 
            return 0
        res = 0
        #到目前结点为止的累加和
        temp = root.val + last; 
        #如果该累加和减去sum在哈希表中出现过，相当于减去前面的分支
        if (temp - sum) in self.mp:
            #加上有的路径数
            res += self.mp[temp - sum] 
        #增加该次路径和
        if temp in self.mp:
            self.mp[temp] += 1
        else:
            self.mp[temp] = 1 
        #进入子结点
        res += self.dfs(root.left, sum, temp) 
        res += self.dfs(root.right, sum, temp) 
        #回退该路径和，因为别的树枝不需要这边存的路径和
        self.mp[temp] -= 1 
        return res
    
    def FindPath(self , root: TreeNode, sum: int) -> int:
        #路径和为0的有1条
        self.mp[0] = 1
        return self.dfs(root, sum, 0)

JZ85 连续子数组的最大和(二)

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。

1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

2.如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个

3.该题定义的子数组的最小长度为1，不存在为空的子数组，即不存在[]是某个数组的子数组

4.返回的数组不计入空间复杂度计算

#动态规划
class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
        dp = [[array[0]], array[0], 1]
        res = [[array[0]], array[0], 1]
        for i in range(1,n):
            if dp[1] >= 0:
                dp[0] += [array[i]]
                dp[1] += array[i]
                dp[2] += 1
            else: 
                dp[0] = [array[i]]
                dp[1] = array[i]
                dp[2] = 1
            if res[1] < dp[1] or (res[1] == dp[1] and res[2] < dp[2]):
                res = [dp[0].copy(),dp[1],dp[2]]
        return res[0]

#动态规划+滑动窗口
class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
        dp = array[0]
        l = 0 #滑动窗口左端
        maxsum = array[0] #最大子数组和
        resl, resr = 0, 0 #最大子数组左右端
        for r in range(1,len(array)): #r为滑动窗口右端
            if dp >= 0: dp += array[r]
            else:
                dp = array[r]
                l = r
            if dp > maxsum or (dp == maxsum and r-l > resr-resl):
                maxsum = dp
                resl, resr = l, r
        return array[resl:resr+1]

JZ86 在二叉树中找到两个节点的最近公共祖先

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

#找到各自的路径，找到最近公共祖先
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        path = []
        lst1, lst2 = [], []
        def dfs(root,o1,o2):
            if not root: return
            path.append(root.val)
            if root.val == o1:
                for item in path: lst1.append(item)
            if root.val == o2: 
                for item in path: lst2.append(item)
            dfs(root.left,o1,o2)
            dfs(root.right,o1,o2)
            path.pop()
        dfs(root,o1,o2)
        res = []
        for i in range(min(len(lst1),len(lst2))):
            if lst1[i] == lst2[i]: res.append(lst1[i])
        return res[-1]

#递归思想
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        if not root: return
        if root.val == o1 or root.val == o2: return root.val
        left = self.lowestCommonAncestor(root.left,o1,o2)
        right = self.lowestCommonAncestor(root.right,o1,o2)
        if not left and not right: return
        if not left: return right
        if not right: return left
        return root.val