剑指offer题目总结（python）题目分类面试题03. 数组中重复的数字4. 二维数组中的查找5. 替换空格6. 从尾到头打印链表7. 重建二叉树9. 用两个栈实现队列10- I. 斐波那契数列10- II. 青蛙跳台阶问题11. 旋转数组的最小数字12. 矩阵中的路径13. 机器人的运动范围14- I. 剪绳子14- II. 剪绳子 II15. 二进制中1的个数16. 数值的整数次方17. 打印从1到最大的n位数18. 删除链表的节点19. 正则表达式匹配20. 表示数值的字符串21. 调

56 阅读 0 评论 37 点赞

我是靠谱客的博主甜甜宝马，最近开发中收集的这篇文章主要介绍剑指offer题目总结（python）题目分类面试题03. 数组中重复的数字4. 二维数组中的查找5. 替换空格6. 从尾到头打印链表7. 重建二叉树9. 用两个栈实现队列10- I. 斐波那契数列10- II. 青蛙跳台阶问题11. 旋转数组的最小数字12. 矩阵中的路径13. 机器人的运动范围14- I. 剪绳子14- II. 剪绳子 II15. 二进制中1的个数16. 数值的整数次方17. 打印从1到最大的n位数18. 删除链表的节点19. 正则表达式匹配20. 表示数值的字符串21. 调，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

剑指offer题目总结（python）

题目
分类
- - 一、位运算
  - 二、二叉树
  - 三、字符串
  - 四、数组
  - 五、栈和队列
  - 六、链表
  - 七、哈希表
  - 八、递归
  - 九、动态规划
  - 十、二分法
  - 十一、双指针
  - 十二、回溯法
  - 十三、dfs、bfs遍历

题目

题目	类别	备注
面试题03. 数组中重复的数字	哈希表、集合、排序
面试题04. 二维数组中的查找	遍历二维数组
面试题05. 替换空格	内置函数、遍历、数组转字符串
面试题06. 从尾到头打印链表	链表、递归
面试题07. 重建二叉树	二叉树、递归
面试题09. 用两个栈实现队列	栈和队列
面试题10- I. 斐波那契数列	动态规划
面试题10- II. 青蛙跳台阶问题	动态规划
面试题11. 旋转数组的最小数字	内置函数、遍历、二分法
面试题12. 矩阵中的路径	回溯、dfs
面试题13. 机器人的运动范围	dfs、bfs
面试题14- I. 剪绳子	math、动态规划
面试题14- II. 剪绳子 II	math、动态规划
面试题15. 二进制中1的个数	内置函数、位运算
面试题16. 数值的整数次方	递归、位运算
面试题17. 打印从1到最大的n位数	列表
面试题18. 删除链表的节点	链表、双指针
面试题19. 正则表达式匹配	递归
面试题20. 表示数值的字符串	语法
面试题21. 调整数组顺序使奇数位于偶数前面	列表、双指针
面试题22. 链表中倒数第k个节点	链表
面试题24. 反转链表	链表
面试题25. 合并两个排序的链表	链表、递归
面试题26. 树的子结构	二叉树、dfs、递归
面试题27. 二叉树的镜像	二叉树、递归
面试题28. 对称的二叉树	二叉树、递归
面试题29. 顺时针打印矩阵	遍历二维数组
面试题30. 包含min函数的栈	栈
面试题31. 栈的压入、弹出序列	栈
面试题32 - I. 从上到下打印二叉树	二叉树、bfs
面试题32 - II. 从上到下打印二叉树 II	二叉树、bfs
面试题32 - III. 从上到下打印二叉树 III	二叉树、bfs
面试题33. 二叉搜索树的后序遍历序列	二叉树、递归
面试题34. 二叉树中和为某一值的路径	二叉树、递归
面试题35. 复杂链表的复制	内置函数、字典、链表
面试题36. 二叉搜索树与双向链表	二叉树、递归
面试题37. 序列化二叉树	二叉树
面试题38. 字符串的排列	内置函数、dfs
面试题39. 数组中出现次数超过一半的数字	字典、摩尔根投票法
面试题40. 最小的k个数	大顶堆
面试题41. 数据流中的中位数	小顶堆、大顶堆
面试题42. 连续子数组的最大和	动态规划
面试题43. 1～n整数中1出现的次数	递归
面试题44. 数字序列中某一位的数字	递归
面试题45. 把数组排成最小的数	排序
面试题46. 把数字翻译成字符串	动态规划
面试题47. 礼物的最大价值	动态规划
面试题48. 最长不含重复字符的子字符串	滑动窗口
面试题49. 丑数	动态规划
面试题50. 第一个只出现一次的字符	字典
面试题51. 数组中的逆序对	归并排序
面试题52. 两个链表的第一个公共节点	链表、双指针
面试题53 - I. 在排序数组中查找数字 I	二分法
面试题53 - II. 0～n-1中缺失的数字	二分法
面试题54. 二叉搜索树的第k大节点	二叉树、dfs、递归
面试题55 - I. 二叉树的深度	二叉树、dfs、bfs、递归
面试题55 - II. 平衡二叉树	二叉树、递归
面试题56 - I. 数组中数字出现的次数	字典、位运算
面试题56 - II. 数组中数字出现的次数 II	位运算、状态机
面试题57. 和为s的两个数字	字典、双指针、二分
面试题57 - II. 和为s的连续正数序列	数学、滑动窗口
面试题58 - I. 翻转单词顺序	内置函数、双指针
面试题58 - II. 左旋转字符串	字符串、遍历、剪枝
面试题59 - I. 滑动窗口的最大值	切片、列表、字符串
面试题59 - II. 队列的最大值	队列
面试题60. n个骰子的点数	动态规划
面试题61. 扑克牌中的顺子	遍历、排序、集合
面试题62. 圆圈中最后剩下的数字	模拟、数学
面试题63. 股票的最大利润	动态规划、遍历
面试题64. 求1+2+…+n	数学、递归
面试题65. 不用加减乘除做加法	位运算
面试题66. 构建乘积数组	动态规划
面试题67. 把字符串转换成整数	语法、遍历
面试题68 - I. 二叉搜索树的最近公共祖先	二叉树、dfs、递归
面试题68 - II. 二叉树的最近公共祖先	二叉树、dfs、递归

分类

一、位运算

15. 二进制中1的个数
16. 二进制中1的个数
56 - I. 数组中数字出现的次数
56 - II. 数组中数字出现的次数 II
65. 不用加减乘除做加法

二、二叉树

07. 重建二叉树
26. 树的子结构
27. 二叉树的镜像
28. 对称的二叉树
32 - I. 从上到下打印二叉树
32 - II. 从上到下打印二叉树 II
32 - III. 从上到下打印二叉树 III
33. 二叉搜索树的后序遍历序列
34. 二叉树中和为某一值的路径
36. 二叉搜索树与双向链表
37. 序列化二叉树
54. 二叉搜索树的第k大节点
55 - I. 二叉树的深度
55 - II. 平衡二叉树
68 - I. 二叉搜索树的最近公共祖先
68 - II. 二叉树的最近公共祖先

三、字符串

四、数组

五、栈和队列

六、链表

七、哈希表

八、递归

九、动态规划

十、二分法

十一、双指针

十二、回溯法

十三、dfs、bfs遍历

面试题03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：
2 <= n <= 100000

如果遍历，用列表保存查询，会超过时间限制，平方时间复杂度

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        tmp = []
        for i in nums:
            if i not in tmp:
                tmp.append(i)
            else:
                return i

用字典优化

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        d = {}
        for i in nums:
            if i not in d:
                d[i] = 1
            else:
                return i

或者用集合

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        tmp = set()
        for i in nums:
            a = len(tmp)
            tmp.add(i)
            if len(tmp) == a:
                return i

当然也可以sort一下，然后遍历判断相邻两个元素是否相同

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                return nums[i]

4. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:
现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。
给定 target = 20，返回 false。

限制：
0 <= n <= 1000
0 <= m <= 1000

注意：本题与主站 240 题相同：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

第一想法是暴力遍历

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        for i in range(len(matrix[0])):
            for j in range(len(matrix)):
                if matrix[i][j] == target:
                    return True
        return False

然后思考一下，利用一下题中给的已有顺序优化一下，从左下角开始

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        i, j = len(matrix) - 1, 0
        while i >= 0 and j < len(matrix[0]):
            if matrix[i][j] > target: i -= 1
            elif matrix[i][j] < target: j += 1
            else: 
                return True
        return False

5. 替换空格

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

示例 1：

输入：s = “We are happy.”
输出：“We%20are%20happy.”

限制：
0 <= s 的长度 <= 10000

直接用内置函数replace

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

用内置函数然后遍历

class Solution:
    def replaceSpace(self, s: str) -> str:
        res = ''
        s = s.split(' ')
        for i in s:
            res += i + '%20'
        return res[:-3]

不用内置函数，直接遍历

class Solution:
    def replaceSpace(self, s: str) -> str:
        res = []
        for i in s:
            if i == ' ':
                res.append('%20')
            else:
                res.append(i)
        return ''.join(res)  # 数组转字符串

6. 从尾到头打印链表

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

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：
0 <= 链表长度 <= 10000

从头到尾保存到数组，然后切片翻转数组

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        tmp = []
        while head:
            tmp.append(head.val)
            head = head.next
        return tmp[::-1]

递归

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        if not head:
            return []
        return self.reversePrint(head.next) + [head.val]

7. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3
/
9 20
/
15 7

限制：
0 <= 节点个数 <= 5000

注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

用前序遍历找到根结点
用根结点在中序遍历中切开左右子树，递归重建二叉树

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(inorder) == 0:
            return None
        
        # preorder 的第一个结点为根节点
        root = TreeNode(preorder[0])
        # 获取根节点在 inorder 中的索引
        idx = inorder.index(preorder[0])
        # 左子树
        root.left = self.buildTree(preorder[1:idx+1], inorder[:idx])
        # 右子树
        root.right = self.buildTree(preorder[idx+1:], inorder[idx+1:])
        return root

9. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：
1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

用辅助栈，两个栈可以实现队列，可以画个草图

class CQueue:

    def __init__(self):
        self.stackin = []
        self.stackout = []

    def appendTail(self, value: int) -> None:
        self.stackin.append(value)

    def deleteHead(self) -> int:
        if self.stackout: return self.stackout.pop()
        if not self.stackin: return -1
        while self.stackin:
            self.stackout.append(self.stackin.pop())
        return self.stackout.pop()


# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下： >F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

提示：
0 <= n <= 100

注意：本题与主站 509 题相同：https://leetcode-cn.com/problems/fibonacci-number/

动态规划，只需要用两个变量保存信息

class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return a % 1000000007

10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

提示：
0 <= n <= 100
注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/climbing-stairs/

和上一题差不多，用两个变量存。
状态方程：dp[i] = dp[i-1] + dp[i-2]

class Solution:
    def numWays(self, n: int) -> int:
        a, b = 1, 2
        for i in range(n - 1):
            a, b = b, a + b
        return a % 1000000007

11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

输入：[3,4,5,1,2]
输出：1

示例 2：

输入：[2,2,2,0,1]
输出：0

注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

内置函数min

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        return min(numbers)

遍历

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        for i in range(len(numbers) - 1):
            if numbers[i] > numbers[i + 1]:
                return numbers[i + 1]
        return numbers[0]

二分法。需要注意数组可能有相同元素。二分法的时间复杂度为logn，对于排好序的问题优先考虑。

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

12. 矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[[“a”,“b”,“c”,“e”],
[“s”,“f”,“c”,“s”],
[“a”,“d”,“e”,“e”]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例 1：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true

示例 2：

输入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
输出：false

提示：
1 <= board.length <= 200
1 <= board[i].length <= 200
注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/

回溯法，directx和directy是遍历的方向数组，这个很有用。用集合存储已经走过的点，回溯需要注意的是每次不符合要求的点要从集合中去除

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
    #         (x-1,y)
    # (x,y-1) (x,y) (x,y+1)
    #         (x+1,y)
        directx = [-1, 1, 0, 0]
        directy = [0, 0, -1, 1]
        # 每次去寻找下一个位置的字母
        def DFS(x, y, id):
            if id == len(word):
                return True
            for i in range(4):
                newx, newy = x + directx[i], y + directy[i]
                if -1 < newx < len(board) and -1 < newy < len(board[0]):
                    # 没有被访问过的，且是我需要的字母，再次进行搜索
                    if (newx, newy) not in vis and board[newx][newy] == word[id]:
                        vis.add((newx, newy))
                        if DFS(newx, newy, id+1):
                            return True
                        vis.remove((newx, newy))
            return False
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    vis = {(i, j)}
                    if DFS(i, j, id=1):
                        return True
        return False

不用集合存储的写法，将走过的点坐标赋值给tmp，用‘’表示走过的点，回溯的时候就还原

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        directi = [-1, 1, 0, 0]
        directj = [0, 0, -1, 1]
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
            if k == len(word) - 1: return True
            tmp, board[i][j] = board[i][j], '/'
            res = False
            for x in range(4):
                newi, newj = i + directi[x], j + directj[x]
                res |= dfs(newi, newj, k + 1)
                if res == True:
                    return res
            # res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = tmp
            return False

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0): return True
        return False

13. 机器人的运动范围

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

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

示例 2：

输入：m = 3, n = 1, k = 0
输出：1

提示：
1 <= n,m <= 100
0 <= k <= 20

广度优先搜索 BFS

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def sum_rc(row,col):
            tmp = 0
            while row > 0:
                tmp += row % 10
                row //= 10
            while col > 0:
                tmp += col % 10
                col //= 10
            return tmp
        dx, dy = [1, 0], [0, 1]
        vis = set()
        stack = []
        stack.append((0, 0))
        while stack:
            x, y = stack.pop(0)
            if (x, y) not in vis and sum_rc(x, y) <= k:
                vis.add((x, y))
                for i in range(2):
                    if 0 <= x + dx[i] < m and 0 <= y + dy[i] < n:
                        stack.append((x + dx[i], y + dy[i]))
        return len(vis)

深度优先搜索 DFS

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def sum_rc(row,col):
            tmp = 0
            while row > 0:
                tmp += row % 10
                row //= 10
            while col > 0:
                tmp += col % 10
                col //= 10
            return tmp
        def dfs(i, j):
            if i == m or j == n or sum_rc(i, j) > k or (i, j) in vis:
                return
            vis.add((i, j))
            dfs(i + 1, j)
            dfs(i, j + 1)
        vis = set()
        dfs(0, 0)
        return len(vis)

14- I. 剪绳子

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

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：
2 <= n <= 58

注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/

写出前面的一些例子，找规律发现是动态规划问题。
n=2: 1+1 -->11=1; dp[2]=1;
n=3: 2+1 -->21=2; dp[3]=2;
n=4: 2+2 -->22=4; dp[4]=4;
n=5: 3+2 -->32=6; dp[5]=6;
n=6: 3+3 -->33=4; dp[6]=9;
n=7: 4+3 -->43=12;–>dp[4]3=12 dp[7]=12;
n=8: 5+3 -->63=12;–>dp[5]3=18 dp[8]=18;
n=9: 6+3 -->93=12;–>dp[6]3=27 dp[9]=27;
n=10: 7+3 -->123=36;–>dp[7]*3=12 dp[10]=36;

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0 for i in range(n + 6)]
        dp[2], dp[3], dp[4], dp[5], dp[6] = 1, 2, 4, 6, 9
        for i in range(7, n + 1):
            dp[i] = 3 * dp[i - 3]
        return dp[n]

经过数学推导会发现，为使乘积最大，只有长度为 2 和 3 的绳子不应再切分且 3 比 2 更优。具体推导可见（大佬的题解）

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3: 
            return n - 1
        a, b = n // 3, n % 3
        if b == 0: 
            return 3 ** a
        if b == 1: 
            return 3 ** (a - 1) * 2 * 2
        return 3 ** a * 2

14- II. 剪绳子 II

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：
2 <= n <= 1000

注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/

我的理解是和上题差不多…多个了模

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3: 
            return n - 1
        a, b = n // 3, n % 3
        if b == 0: 
            return 3 ** a % 1000000007
        if b == 1: 
            return 3 ** (a - 1) * 4 % 1000000007
        return 3 ** a * 2 % 1000000007

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0 for i in range(n + 6)]
        dp[2], dp[3], dp[4], dp[5], dp[6] = 1, 2, 4, 6, 9
        for i in range(7, n + 1):
            dp[i] = 3 * dp[i - 3]
        return dp[n] % 1000000007

15. 二进制中1的个数

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

示例2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。

示例3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。

注意：本题与主站 191 题相同：https://leetcode-cn.com/problems/number-of-1-bits/

先把数字换成字符串，然后用内置函数count

class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count('1')

一般涉及到二进制都要考虑位运算

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += n&1
            n >>= 1
        return res

可以使用 n & (n - 1)将最低位的1变成0

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            n = n & (n - 1)
            res += 1
        return res

16. 数值的整数次方

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/

数学表达式

class Solution:
    def myPow(self, x: float, n: int) -> float:
        return x ** n

递归

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if not n:
            return 1
        if n < 0:
            return 1/self.myPow(x, -n)
        if n % 2:
            return x*self.myPow(x, n-1)
        return self.myPow(x*x, n//2)

位运算

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        pow = 1
        while n:
            if n & 1:       #判断是否为奇数
                pow *= x    
            x *= x          
            n >>= 1          
            # print(x, n)
        return pow

17. 打印从1到最大的n位数

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

示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明：
用返回一个整数列表来代替打印
n 为正整数

pythonic

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

class Solution:
    def printNumbers(self, n: int) -> List[int]:
        return list(range(1, 10 ** n))

18. 删除链表的节点

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

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：
题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

用哑结点可以省很多事

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        if head.val == val:
            return head.next
        while head and head.next:
            if head.next.val == val:
                head.next = head.next.next
                break
            head = head.next
        return dummy.next

用双指针也可以

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(0) # 假头
        dummy.next = head
        first = dummy # 双指针1
        second = dummy.next # 双指针2
        while True:
            if second.val == val:
                first.next = second.next
                break
            first = first.next
            second = second.next
        return dummy.next

19. 正则表达式匹配

请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

示例 2:

输入:
s = “aa”
p = “a*”
输出: true
解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3:

输入:
s = “ab”
p = “."
输出: true
解释: ".” 表示可匹配零个或多个（’*’）任意字符（’.’）。

示例 4:

输入:
s = “aab”
p = “cab”
输出: true
解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5:

输入:
s = “mississippi”
p = “misisp*.”
输出: false
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 '’。

注意：本题与主站 10 题相同：https://leetcode-cn.com/problems/regular-expression-matching/

递归。遇到x*的情况其实只有2种。
如果首字母不同则舍弃p的x*，s不变；如果首字母相同则舍弃s的首字母，p不变

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p: return not s # 结束条件
        # 第一个字母是否匹配
        first_match = bool(s and p[0] in {s[0],'.'})
        # 如果 p 第二个字母是 *
        if len(p) >= 2 and p[1] == "*":
        # 匹配0个 | 多个
            return self.isMatch(s, p[2:]) or first_match and self.isMatch(s[1:], p)
        else:
        # 处理 `.` ，匹配一个
            return first_match and self.isMatch(s[1:], p[1:])

20. 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、“5e2”、"-123"、“3.1416”、“0123"都表示数值，但"12e”、“1a3.14”、“1.2.3”、“±5”、"-1E-16"及"12e+5.4"都不是。

注意：本题与主站 65 题相同：https://leetcode-cn.com/problems/valid-number/

用float强转

class Solution:
    def isNumber(self, s: str) -> bool:
        try:
            float(s)
            return True
        except:
          return False

还有状态机的方法，还没彻底弄懂…

21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。

提示：
1 <= nums.length <= 50000
1 <= nums[i] <= 10000

创建两个列表，一个放奇数一个放偶数

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        return [i for i in nums if i % 2 == 1] + [i for i in nums if i % 2 == 0]

另一种写法

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        ji, ou = [], []
        for i in nums:
            if i & 1:
                ji.append(i)
            else:
                ou.append(i)
        return ji + ou

用双指针，不使用额外的空间

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        start, end = 0, len(nums) - 1
        while start < end:
            while start < end and nums[start]%2 != 0:
                start += 1
            while start < end and nums[end]%2 ==0:
                end -= 1
            nums[start], nums[end] = nums[end], nums[start]
        return nums

22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

先遍历一次计算整个链表的长度count，然后再遍历一次直到count - k == 0。需要注意本题是从1开始计数的。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        count = 0
        head1 = head
        while head1:
            count += 1
            head1 = head1.next
        count -= k
        tmp = 0
        for i in range(count):
            head = head.next
        return head

也可以用双指针来做。设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是倒数第 K 个节点。

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        if not head: return None
        fast_p = head
        slow_p = head
        for _ in range(k):
            if fast_p:
                fast_p = fast_p.next
            else:
                return None
        while fast_p:
            fast_p = fast_p.next
            slow_p = slow_p.next
        return slow_p

24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：
0 <= 节点个数 <= 5000

注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

很经典的一题，可以在纸上画一下。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            cur.next, pre, cur  = pre, cur, cur.next  # 具有同时性
        return pre

25. 合并两个排序的链表

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

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：
0 <= 链表长度 <= 1000

注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

创建两个哑结点，然后遍历。遍历结束后，l1或者l2有剩余的腰加上。创建两个哑结点的原因是一个一直在动，另一个不动用来返回

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy, head = ListNode(0), ListNode(0)
        dummy.next = head
        while l1 and l2:
            if l1.val < l2.val:
                head.next = l1
                head = head.next
                l1 = l1.next
            else:
                head.next = l2
                head = head.next
                l2 = l2.next
        if l1:
            head.next = l1
        if l2:
            head.next = l2
        return dummy.next.next

也可以用递归来做，

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        if l1.val>l2.val:
            res=ListNode(l2.val)
            res.next=self.mergeTwoLists(l1,l2.next)
        else:
            res = ListNode(l1.val)
            res.next=self.mergeTwoLists(l1.next,l2)
        return res

下面还提供几种写法

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2:
            if l1.val > l2.val: l1, l2 = l2, l1
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1 or l2

26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:
3
/
4 5
/
1 2
给定的树 B：

4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：
0 <= 节点个数 <= 10000

用一个函数判断两颗树是否完全一样，再到递归判定A,B或（A左子树和B) 或（A右子树和B）是否一样。

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not A or not B:
            return False
        return self.dfs(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)

    def dfs(self, A, B):
        if not B:
            return True
        if not A:
            return False
        return A.val == B.val and self.dfs(A.left, B.left) and self.dfs(A.right, B.right)

27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：
        4
    /
  2      7
   /      /
1   3 6 9

镜像输出：
         4
       /
     7     2
   /     /
9     6 3     1

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

限制：
0 <= 节点个数 <= 1000

注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/

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

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

28. 对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
       1
     /
   2       2
  /    /
3   4   4    3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
     1
    /
   2    2

       3     3

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

限制：
0 <= 节点个数 <= 1000

注意：本题与主站 101 题相同：https://leetcode-cn.com/problems/symmetric-tree/

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

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def isMirror(t1, t2):
            if not t1 and not t2:  # 如果都为空，则是对称的
                return True
            if not t1 or not t2:  # 如果其中一个为空另一个不是，则不是对称的
                return False
            return t1.val == t2.val and isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
        return isMirror(root, root)

29. 顺时针打印矩阵

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

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制：
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

注意：本题与主站 54 题相同：https://leetcode-cn.com/problems/spiral-matrix/

这是一个遍历二维数组的问题。主要是模拟过程，往右和往下都是坐标的增加，可以视为一个循环步骤；往右和往下都是坐标的减少，可以视为一个循环步骤。增加和减少可以利用flag来实现，每次循环结束*（-1）。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
        m, n = len(matrix), len(matrix[0])
        i, j = 0, -1
        res = []
        flag = 1
        while m > 0 and n > 0:
            for x in range(n):
                j += flag
                res.append(matrix[i][j])
            for y in range(m - 1):
                i += flag
                res.append(matrix[i][j])
            m -= 1
            n -= 1
            flag *= -1
        return res

30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.

提示：
各函数的调用总次数不超过 20000 次

注意：本题与主站 155 题相同：https://leetcode-cn.com/problems/min-stack/

创建两个列表，一个正常栈操作，一个只保存最小值（minStack），push进来时要看是否比最小值小，如果小则加进去。需要注意pop的时候如果pop出来的元素刚好是最小值，minStack也要pop出来。

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.minStack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.minStack or self.minStack[-1] >= x:
            self.minStack.append(x)

    def pop(self) -> None:
        if not self.stack:
            return -1
        if self.stack.pop() == self.minStack[-1]:          
            self.minStack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def min(self) -> int:
        return self.minStack[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

31. 栈的压入、弹出序列

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

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。

注意：本题与主站 946 题相同：https://leetcode-cn.com/problems/validate-stack-sequences/

借助一个辅助栈模拟压入和弹出的操作。

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        tmp_stack = []
        pointer = 0
        for i in pushed:
            tmp_stack.append(i)
            # while来模拟连续pop的过程
            while tmp_stack[-1] == popped[pointer]:
                tmp_stack.pop()
                pointer += 1
                if len(tmp_stack) == 0:
                    break
        return len(popped) == pointer

32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7],
        3
       /
   9    20
           /
        15 7

返回：
[3,9,20,15,7]

提示：
节点总数 <= 1000

考的就是二叉树的层次遍历，bfs

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

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        res = []
        if not root:
            return []
        queue = [root]        
        while queue:
            node = queue.pop(0)
            res.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return res

32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],
        3
       /
   9    20
           /
        15 7

返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]

提示：
节点总数 <= 1000

注意：本题与主站 102 题相同：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

相较于上一题，需要保存每一层的节点。

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

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root:
            return []
        queue = [root]
        while queue:
            tmp = []
            next = []
            for node in queue:
                tmp.append(node.val)
                if node.left:
                    next.append(node.left)
                if node.right:
                    next.append(node.right)  
            res.append(tmp)  
            queue = next        
        return res

32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],
        3
       /
   9    20
           /
        15 7

返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]

提示：
节点总数 <= 1000

相较于上一题，增加了一个判断，如果是偶数层（对应的count是奇数层），则将保存该层的节点值列表翻转后保存

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

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root:
            return []
        queue = [root]
        count = 0
        while queue:
            tmp = []
            next = []
            for node in queue:
                tmp.append(node.val)
                if node.left:
                    next.append(node.left)
                if node.right:
                    next.append(node.right)  
            if count & 1:
                res.append(tmp[::-1])
            else:
                res.append(tmp)  
            queue = next        
            count += 1
        return res

33. 二叉搜索树的后序遍历序列

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

参考以下这颗二叉搜索树：
      5
       /
      2 6
     /
   1    3

示例 1：

输入: [1,6,3,2,5]
输出: false

示例 2：

输入: [1,3,2,6,5]
输出: true

提示：
数组长度 <= 1000

后序遍历结果额最后一个元素为root节点，后序遍历的左半部分比root小，右半部分比root大。用这个来写递归。

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if len(postorder) <= 1:
            return True
        root = postorder[-1]
        for i in range(len(postorder)):
            if postorder[i] > root:
                break
        for j in range(i, len(postorder) - 1):
            if postorder[j] < root:
                return False
        return self.verifyPostorder(postorder[:i]) and self.verifyPostorder(postorder[i:-1])

34. 二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 sum = 22，

          5
         / 
        4   8
       /   / 
      11  13  4
     /      / 
    7    2  5   1

[
[5,4,11,2],
[5,8,4,5]
]

提示：
节点总数 <= 10000

注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/

先序遍历递归

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        def helper(root, tmp, sum):
            if not root:
                return
            if not root.left and not root.right and sum - root.val == 0:
                tmp += [root.val]
                res.append(tmp)
            helper(root.left, tmp + [root.val], sum - root.val)
            helper(root.right, tmp + [root.val], sum - root.val)
        res = []
        helper(root, [], sum)
        return res

35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

内置函数deepcopy

class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        return copy.deepcopy(head)

dfs。从头结点 head 开始拷贝；
由于一个结点可能被多个指针指到，因此如果该结点已被拷贝，则不需要重复拷贝；
如果还没拷贝该结点，则创建一个新的结点进行拷贝，并将拷贝过的结点保存在哈希表中；
使用递归拷贝所有的 next 结点，再递归拷贝所有的 random 结点。

class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        def dfs(head):
            if not head: return None
            if head in visited:
                return visited[head]
            # 创建新结点
            copy = Node(head.val, None, None)
            visited[head] = copy
            copy.next = dfs(head.next)
            copy.random = dfs(head.random)
            return copy
        visited = {}
        return dfs(head)

36. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

注意：本题与主站 426 题相同：https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

注意：此题对比原题有改动。

考虑使用中序遍历访问树的各节点 curcur ；并在访问每个节点时构建 curcur 和前驱节点 prepre 的引用指向；中序遍历完成后，最后构建头节点和尾节点的引用指向即可。

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def dfs(cur):
            if not cur: return
            dfs(cur.left) # 递归左子树
            if self.pre: # 修改节点引用
                self.pre.right, cur.left = cur, self.pre
            else: # 记录头节点
                self.head = cur
            self.pre = cur # 保存 cur
            dfs(cur.right) # 递归右子树
        
        if not root: return
        self.pre = None
        dfs(root)
        self.head.left, self.pre.right = self.pre, self.head
        return self.head

37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

示例:

你可以将以下二叉树：

序列化为 “[1,2,3,null,null,4,5]”

注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

前序遍历

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        res=[]
        stack=[root]
        while stack:
            node=stack.pop()
            if node:
                res.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
            else:
                res.append(None)  
        return res

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        self.index=0
        def dfs(data):
            if data[self.index]==None:
                self.index+=1
                return 
            root=TreeNode(data[self.index])
            self.index+=1
            root.left=dfs(data)
            root.right=dfs(data)
            return root
        return dfs(data)

38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = “abc”
输出：[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]

限制：
1 <= s 的长度 <= 8

使用内置函数itertools.permutations

class Solution:
    def permutation(self, s: str) -> List[str]:
        import itertools
        tmp = [i for i in s]
        ans = []
        res = list(itertools.permutations(tmp))
        for i in res:
            ans.append(''.join(i))
        ans = list(set(ans))
        return ans

排序+dfs

class Solution:
    def permutation(self, s: str) -> List[str]:
        #思路：dfs同时记录路径，到根节点处统计结果
        s = sorted(list(s))
        res = []
        def dfs(s,road):
            if s == []:
                res.append(''.join(road))
            for i in range(len(s)):
                if i > 0 and s[i] == s[i-1]:
                    continue 
                dfs(s[:i]+s[i+1:], road+[s[i]])
        dfs(s, [])
        return(res)

集合+dfs

class Solution:
    def permutation(self, s: str) -> List[str]:
        # s = sorted(list(s))
        s = list(s)
        res = []
        def dfs(s, road):
            if s == []:
                res.append(''.join(road))
            for i in range(len(s)):
                # if i > 0 and s[i] == s[i -1]:
                #     continue
                dfs(s[:i] + s[i + 1:], road + [s[i]])
        dfs(s, [])
        res = list(set(res))
        return res

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

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：
1 <= 数组长度 <= 50000

注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/

排序后的中间索引

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums) // 2]

字典

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        d = {}
        count = len(nums) // 2
        for i in nums:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
        for i in d:
            if d[i] > count:
                return i

摩尔根投票。由于众数出现的次数超过数组长度的一半；若记众数的票数为 +1 ，非众数的票数为 −1 ，遍历结束后结果一定 >0

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if not nums:
            return
        cand = nums[0]
        count = 0
        for i in nums:
            if count == 0:
                cand = i
                count = 1
                continue
            if cand == i:
                count += 1
                continue
            if cand != i:
                count -= 1
                continue
        return cand

40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

排序

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        return arr[:k]

手写大顶堆，插眼，回来再康康

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k==0:
            return []
        #最小的k个数 最大堆
        #最大堆 顶点最大
        def maxHeapfy(maxHeap,i,n):
            left=2*i+1
            right=2*i+2
            maxPoint=i
            if left<n and maxHeap[left]>maxHeap[maxPoint]:
                maxPoint=left
            if right<n and maxHeap[right]>maxHeap[maxPoint]:
                maxPoint=right
            if maxPoint!=i:
                maxHeap[i],maxHeap[maxPoint]=maxHeap[maxPoint],maxHeap[i]
                maxHeapfy(maxHeap,maxPoint,n)
        #初始化 取前k个树，组成最大堆
        maxHeap=arr[:k]
        #从第一个非叶子节点开始构建最大堆
        n=len(arr)
        for i in range(k//2-1,-1,-1):
            maxHeapfy(maxHeap,i,k)
        #继续调整后面节点
        for i in range(k,n):
            if arr[i]<maxHeap[0]:
                maxHeap[0]=arr[i]
                maxHeapfy(maxHeap,0,k)
        #现在全部构建好了，最后排序一次
        for i in range(k-1,0,-1):
            maxHeap[i],maxHeap[0]=maxHeap[0],maxHeap[i]
            maxHeapfy(maxHeap,0,i)
        return maxHeap

41. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

示例 1：

输入：
[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

示例 2：

输入：
[“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

限制：
最多会对 addNum、findMedia进行 50000 次调用。

注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/

硬着头皮做…

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.l = []

    def addNum(self, num: int) -> None:
        self.l.append(num)
        self.l.sort()

    def findMedian(self) -> float:
        if len(self.l) % 2 == 1:
            return self.l[len(self.l) // 2]
        else:
            return (self.l[len(self.l) // 2 - 1] + self.l[len(self.l) // 2]) / 2

# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

Python 中 heapq 模块是小顶堆。实现大顶堆方法：小顶堆的插入和弹出操作均将元素取反即可。
创建两个堆，小顶堆A存放较大的一半元素，大顶堆B存放较小的一半元素。

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.A = []
        self.B = []

    def addNum(self, num: int) -> None:
        if len(self.A) != len(self.B):
            heappush(self.A, num)
            heappush(self.B, -heappop(self.A))
        else:
            heappush(self.B, -num)
            heappush(self.A, -heappop(self.B))

    def findMedian(self) -> float:
        if len(self.A) != len(self.B):
            return self.A[0]
        else:
            return (self.A[0] - self.B[0]) / 2

# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

42. 连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/

动态规划
当dp[i-1]>0时，dp[i]=dp[i-1]+nums[i]
当dp[i-1]<=0时，dp[i]=nums[i]

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            if nums[i - 1] > 0:
                nums[i] += nums[i - 1]
        return max(nums)

43. 1～n整数中1出现的次数

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12
输出：5

示例 2：

输入：n = 13
输出：6

限制：
1 <= n < 2^31

注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/

神烦这种找规律题目
暴力解超时

class Solution:
    def countDigitOne(self, n: int) -> int:
        s = ''
        while n:
            s += str(n)
            n = n-1
        return s.count('1')

将n拆分为两部分，最高一位的数字high和其他位的数字last，分别判断情况后将结果相加，看例子更加简单。
例子如n=1234，high=1, pow=1000, last=234
可以将数字范围分成两部分1~999和1000~1234
1~999这个范围1的个数是countDigitOne(pow-1)
1000~1234这个范围1的个数需要分为两部分：
千分位是1的个数：千分位为1的个数刚好就是234+1(last+1)，注意，这儿只看千分位，不看其他位
其他位是1的个数：即是234中出现1的个数，为countDigitOne(last)
所以全部加起来是countDigitOne(pow-1) + last + 1 + countDigitOne(last);

例子如3234，high=3, pow=1000, last=234
可以将数字范围分成两部分1~999，1000~1999，2000~2999和3000~3234
1~999这个范围1的个数是countDigitOne(pow-1)
1000~1999这个范围1的个数需要分为两部分：
千分位是1的个数：千分位为1的个数刚好就是pow，注意，这儿只看千分位，不看其他位
其他位是1的个数：即是999中出现1的个数，为countDigitOne(pow-1)
2000~2999这个范围1的个数是countDigitOne(pow-1)
3000~3234这个范围1的个数是countDigitOne(last)
所以全部加起来是pow + high*countDigitOne(pow-1) + countDigitOne(last);

class Solution:
    def countDigitOne(self, n: int) -> int:
        if n <= 0: return 0

        num_s = str(n) 
        high = int(num_s[0])  
        Pow = 10**(len(num_s)-1) 
        last = n - high*Pow
        
        if high == 1:
            return self.countDigitOne(Pow-1)+self.countDigitOne(last)+last+1
        else:
            return Pow+high*self.countDigitOne(Pow-1)+self.countDigitOne(last)

44. 数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

限制：
0 <= n < 2^31

注意：本题与主站 400 题相同：https://leetcode-cn.com/problems/nth-digit/

1-9 19个数字
10-99 290个数字
100-999 3*900个数字
对于第 n 位对应的数字，我们令这个数字对应的数为 target，然后分三步进行。
首先找到这个数字对应的数是几位数，用 digits 表示；
然后确定这个对应的数的数值 target；
最后确定返回值是 target 中的哪个数字。
举个栗子：
比如输入的 n 是 365：
经过第一步计算我们可以得到第 365 个数字表示的数是三位数，n=365−9−90×2=176，digtis = 3。表示目标数字是三位数中的第 176 个数字。
我们设目标数字所在的数为 number，计算得到 number=100+176/3=158，idx 是目标数字在 number 中的索引，如果 idx = 0，表示目标数字是 number 中的最后一个数字。根据步骤2，我们可以计算得到 idx = n % digits = 176 % 3 = 2，说明目标数字应该是 number = 158 中的第二个数字，即输出为 5。

class Solution:
    def findNthDigit(self, n: int) -> int:
        if n == 0:
            return 0
        n -= 1   # 这里的-1很巧妙
        digits = 1
        base = 9
        while n - base * digits > 0:
            n -= base * digits
            digits += 1
            base *= 10
        return int(str(10 ** (digits - 1) + n // digits)[n % digits])

45. 把数组排成最小的数

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

示例 1:

输入: [10,2]
输出: “102”

示例 2:

输入: [3,30,34,5,9]
输出: “3033459”

提示:
0 < nums.length <= 100

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

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        if not nums:
            return None
        for i in range(len(nums)):
            nums[i] = str(nums[i])
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if (nums[i] + nums[j]) > (nums[j] + nums[i]):
                    nums[i], nums[j] = nums[j], nums[i]
        return ''.join(nums)

46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”

提示：
0 <= num < 231

动态规划

class Solution:
    def translateNum(self, num: int) -> int:
        int2str = str(num)
        dp = [1, 1]
        for i in range(len(int2str)-2, -1, -1):
            if int2str[i] != '0' and int2str[i] + int2str[i+1] < '26':
                dp.append(dp[-1] + dp[-2])
            else:
                dp.append(dp[-1])
        return dp[-1]

优化一下空间

class Solution:
   def translateNum(self, num: int) -> int:
       s = str(num)
       a = b = 1
       for i in range(len(s) - 2, -1, -1):
           a, b = (a + b if "10" <= s[i:i + 2] <= "25" else a), a
       return a

从右和从左遍历都是一样的

class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        a = b = 1
        for i in range(2, len(s) + 1):
            a, b = (a + b if "10" <= s[i - 2:i] <= "25" else a), a
        return a

利用数字求余再度优化空间

class Solution:
    def translateNum(self, num: int) -> int:
        a = b = 1
        y = num % 10
        while num != 0:
            num //= 10
            x = num % 10
            a, b = (a + b if 10 <= 10 * x + y <= 25 else a), a
            y = x
        return a

47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示：
0 < grid.length <= 200
0 < grid[0].length <= 200

动态规划
转移方程为 grid[i][j] = max(grid[i][j] + grid[i][j - 1], grid[i][j] + grid[i - 1][j])

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == j == 0:
                    continue
                elif i == 0:
                    grid[i][j] += grid[i][j - 1]
                elif j == 0:
                    grid[i][j] += grid[i - 1][j]
                else:
                    grid[i][j] = max(grid[i][j] + grid[i][j - 1], grid[i][j] + grid[i - 1][j])
        return grid[-1][-1]

48. 最长不含重复字符的子字符串

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

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。

提示：
s.length <= 40000
注意：本题与主站 3 题相同：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

最先想到的就是直接遍历，max比较

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        i, j = 0, 1
        res = 0
        while j <= len(s):
            if len(s[i:j]) == len(set(s[i:j])):
                res = max(res, len(s[i:j]))
            else:
                i += 1
            j += 1
        return res

滑动窗口

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        lookup = []
        res = 0
        # 当前窗口长度
        cur_len = 0
        for i in range(len(s)):
            if s[i] not in lookup:
                lookup.append(s[i])
                cur_len = len(lookup)
            else:
                index = lookup.index(s[i])
                lookup = lookup[index+1:]
                lookup.append(s[i])
                cur_len = len(lookup)
            # 更新res
            res = max(res, cur_len)
        return res

while写滑窗

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        i, j = 0, 1
        res = 0
        while j <= len(s):
            if len(s[i:j]) == len(set(s[i:j])):
                res = max(res, len(s[i:j]))
            else:
                i += s[i:j].index(s[j - 1]) + 1  # 这个index求的是s[i:j]的索引
            j += 1
        return res

49. 丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:
1 是丑数。
n 不超过1690。

注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/

动态规划

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        res = []
        if n <= 1:
            return n
        res = [1] * n
        i2, i3, i5 = 0, 0, 0
        for i in range(1, n):
            res[i] = min(res[i2] * 2, res[i3] * 3, res[i5] * 5)
            if res[i] == res[i2] * 2:
                i2 += 1
            if res[i] == res[i3] * 3:
                i3 += 1
            if res[i] == res[i5] * 5:
                i5 += 1
        return res[-1]

50. 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例:

s = “abaccdeff”
返回 “b”

s = “”
返回 " "

限制：
0 <= s 的长度 <= 50000

字典

class Solution:
    def firstUniqChar(self, s: str) -> str:
        d = {}
        for i in s:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
        for i in d:
            if d[i] == 1:
                return i
        return ' '

字典有个内置函数get

class Solution:
    def firstUniqChar(self, s: str) -> str:
        d = {}
        for i in s:
            d[i] = d.get(i, 0) + 1
        for i in d:
            if d[i] == 1:
                return i
        return ' '

51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：
0 <= 数组长度 <= 50000

暴力解时间超时

归并排序，着实挺难的
可以联想到合并两个有序数组

def mergeTwo(nums1, nums2):
    res = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums[j]:
            res.append(nums[i])
            i += 1
        else:
            res.append(nums[j])
            j += 1
    while i < len(nums1) :
        res.append(num[i])
        i += 1
    while j < len(nums1) :
        res.append(num[j])
        j += 1
    return res

而我们要做的就是在上面的合并过程中统计逆序数。
比如对于左：[1，2，3 ，4]右：[2，5]。其中 i，j 指针如粗体部分。那么逆序数就是 mid - i + 1 也就是 3 - 2 + 1 = 2 即（3，2)和 (4，2)。其原因在于如果 3 大于 2，那么 3 后面不用看了，肯定都大于 2。
之后会变成：[1，2，3，4] 右：[2，5]

其实就是归并排序

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.count = 0
        def merge(nums, start, mid, end):
            i, j, temp = start, mid + 1, []
            while i <= mid and j <= end:
                if nums[i] <= nums[j]:
                    temp.append(nums[i])
                    i += 1
                else:
                    self.count += mid - i + 1
                    temp.append(nums[j])
                    j += 1
            while i <= mid:
                temp.append(nums[i])
                i += 1
            while j <= end:
                temp.append(nums[j])
                j += 1
            
            for i in range(len(temp)):
                nums[start + i] = temp[i]
                    

        def mergeSort(nums, start, end):
            if start >= end: return
            mid = (start + end) >> 1
            mergeSort(nums, start, mid)
            mergeSort(nums, mid + 1, end)
            merge(nums, start, mid,  end)
        mergeSort(nums, 0, len(nums) - 1)
        return self.count

52. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

本题与主站 160 题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。
这样，当它们相遇时，所指向的结点就是第一个公共结点。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p, q = headA, headB
        while p != q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p

之前一直在想为什么不会进入死循环：可以理解为两条链表最后都指向了同一个 null （None）节点，代替了不相交的特殊情况。非常的巧妙。

53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

限制：
0 <= 数组长度 <= 50000

注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

遍历

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        count = 0
        for i in nums:
            if i == target:
                count += 1
        return count

二分法的时间复杂度是logn

class Solution:
    def search(self, nums: [int], target: int) -> int:
        # 搜索右边界 right
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] <= target: i = m + 1
            else: j = m - 1
        right = i
        # 若数组中无 target ，则提前返回
        if j >= 0 and nums[j] != target: return 0
        # 搜索左边界 left
        i = 0
        while i <= j:
            m = (i + j) // 2
            if nums[m] < target: i = m + 1
            else: j = m - 1
        left = j
        return right - left - 1

代码有些冗余，由于数组 numsnums 中元素都为整数，因此可以分别二分查找 target 和 target - 1 的右边界，将两结果相减并返回即可。将过程封装给函数help

class Solution:
    def search(self, nums: [int], target: int) -> int:
        def helper(tar):
            i, j = 0, len(nums) - 1
            while i <= j:
                m = (i + j) // 2
                if nums[m] <= tar: i = m + 1
                else: j = m - 1
            return i
        return helper(target) - helper(target - 1)

53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:
输入: [0,1,3]
输出: 2

示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：
1 <= 数组长度 <= 10000

遍历

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        if nums[0] != 0: 
            return 0
        for i in range(len(nums) - 1):
            if nums[i + 1] - nums[i] != 1:
                return nums[i] + 1
        return len(nums)

也可以使用一下for else语法

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if i != nums[i]:
                return i
        else:
            return len(nums)

二分法的两种模板

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        L = 0
        R = len(nums) - 1
        while L <= R:
            mid = (L+R) >> 1
            if mid == nums[mid]:  # 相等,则说明左边都连续.
                L = mid + 1
            else:
                R = mid - 1
        return L

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        L = 0
        R = len(nums)
        while L < R:
            mid = (L+R) >> 1
            if mid == nums[mid]:  # 相等,则说明左边都连续.
                L = mid + 1
            else:
                R = mid
        return L

54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1

输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3

输出: 4

限制：
1 ≤ k ≤ 二叉搜索树元素个数

中序遍历后将结果存为列表，然后返回列表倒数第k个

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

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        if not root:
            return 
        res = []
        def inorder(root):
            if not root:
                return []
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        inorder(root)
        return res[-k]

改变中序遍历的顺序，先遍历右节点根节点最后左节点。在递归中就存储好res

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

        self.k = k
        dfs(root)
        return self.res

55 - I. 二叉树的深度

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

例如：
给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

提示：
节点总数 <= 10000

注意：本题与主站 104 题相同：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

dfs、递归

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

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

bfs

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: 
            return 0
        level = 0
        queue = [root]
        while queue:
            for i in range(len(queue)):
                cur = queue.pop(0)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            level += 1
        return level

55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:
给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

限制：
1 <= 树的结点个数 <= 10000

注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/

上一题的延伸
函数写在函数里面的时候，不用self，如果写在class里面就加self，有self引用的时候就self.

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

上面的另外一种写法
```python
class Solution:
    def maxDepth(self, root):
            if not root:
                return 0
            left = self.maxDepth(root.left) + 1
            right = self.maxDepth(root.right) + 1
            return max(left, right)
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        if abs(self.maxDepth(root.right) - self.maxDepth(root.left)) >= 2:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：
2 <= nums.length <= 10000

字典

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        d = {}
        res = []
        for i in nums:
            d[i] = d.get(i, 0) + 1
        for i in nums:
            if d[i] == 1:
                res.append(i)
        return res

位运算
题目大意是除了两个数字出现一次，其他都出现了两次，让我们找到这个两个数。
我们进行一次全员异或操作，得到的结果就是那两个只出现一次的不同的数字的异或结果。
我们刚才讲了异或的规律中有一个任何数和本身异或则为0，因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。
分组需要满足两个条件.
两个独特的的数字分成不同组
相同的数字分成相同组
这样每一组的数据进行异或即可得到那两个数字。
问题的关键点是我们怎么进行分组呢？
由于异或的性质是，同一位相同则为 0，不同则为 1. 我们将所有数字异或的结果一定不是 0，也就是说至少有一位是 1.
我们随便取一个，分组的依据就来了，就是你取的那一位是 0 分成 1 组，那一位是 1 的分成一组。
这样肯定能保证2. 相同的数字分成相同组, 不同的数字会被分成不同组么。很明显当然可以，因此我们选择是 1，也就是
说两个独特的的数字在那一位一定是不同的，因此两个独特元素一定会被分成不同组。

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        ret = 0
        a = 0
        b = 0
        for num in nums:
            ret ^= num
        h = 1
        while ret & h == 0:
            h <<= 1
        for num in nums:
            if num & h == 0:
                a ^= num
            else:
                b ^= num
        return [a, b]

56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31

位运算
状态机

推导two的时候要注意，two要根据one_next来推导。
由于是先计算 oneone ，因此应在新 oneone 的基础上计算 twotwo 。
如下图所示，修改为新 oneone 后，得到了新的状态图。

遍历完所有数字后，各二进制位都处于状态 0000 和状态 0101 （取决于 “只出现一次的数字” 的各二进制位是 11 还是 00 ），而此两状态是由 oneone 来记录的（此两状态下 twostwos 恒为 00 ），因此返回 onesones 即可。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones, twos = 0, 0
        for num in nums:
            ones = ones ^ num & ~twos
            twos = twos ^ num & ~ones
        return ones

57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

限制：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6

字典

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i in nums:
            if target - i in d:
                return [target - i, i]
            d[i] = 1
        return -1

双指针

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        start, end = 0, len(nums) - 1
        while start < end:
            if nums[start] + nums[end] > target:
                end -= 1
            elif nums[start] + nums[end] < target:
                start += 1
            else:
                return [nums[start], nums[end]]

二分

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        start, end = 0, len(nums) - 1
        while start < end:
            mid = (start + end) // 2
            if nums[mid] >= target:
                end = mid - 1
            else:
                while start < end:
                    if nums[start] + nums[end] < target:
                        start += 1
                    elif nums[start] + nums[end] > target:
                        end -= 1
                    else:
                        return [nums[start], nums[end]]

57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：
1 <= target <= 10^5

数学

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        res = []
        for i in range(1, target // 2 + 1):
            for j in range(i + 1, target // 2 + 2):
                if (i + j) * (j - i + 1) // 2 == target:
                    res.append(list(range(i, j + 1)))
                    break
                if (i + j) * (j - i + 1) // 2 > target:
                    break
        return res

滑动窗口
滑动窗口的重要性质是：窗口的左边界和右边界永远只能向右移动，而不能向左移动。这是为了保证滑动窗口的时间复杂度是 O(n)。如果左右边界向左移动的话，这叫做“回溯”，算法的时间复杂度就可能不止 O(n)。在这道题中，我们关注的是滑动窗口中所有数的和。当滑动窗口的右边界向右移动时，也就是 j = j + 1，窗口中多了一个数字 j，窗口的和也就要加上 j。当滑动窗口的左边界向右移动时，也就是 i = i + 1，窗口中少了一个数字 i，窗口的和也就要减去 i。滑动窗口只有右边界向右移动（扩大窗口）和左边界向右移动（缩小窗口）两个操作，所以实际上非常简单。

当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动
当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动
当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [i, j)，那么我们已经找到了一个 i 开头的序列，也是唯一一个 i 开头的序列，接下来需要找 i+1开头的序列，所以窗口的左边界要向右移动

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        i = j = 1
        res = []
        cur_sum = 0
        while j <= target // 2 + 1: # 右边界不超过中值
            cur_sum += j
            j += 1
            while cur_sum > target:
                cur_sum -= i
                i += 1
            if cur_sum == target:
                res.append(list(range(i, j)))
        return res

因为是连续的正数序列，i+1 开头的序列一定无解，所以当sum==target时，左边界可以直接向右移动两位，即i += 2，这样子时间复杂度会稍微小一点点。

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        l = 1
        r = 2
        res = []
        
        while l <= target//2:
            sum = (l+r)*(r-l+1)//2  # 等差数列求和公式求sum
            if sum < target:
                r += 1
            elif sum == target:
                add = list(range(l,1+r))
                res.append(add)
                l += 2
            elif sum > target:
                l += 1
        return res

58 - I. 翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。

示例 1：

输入: “the sky is blue”
输出: “blue is sky the”

示例 2：

输入: " hello world! "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

注意：本题与主站 151 题相同：https://leetcode-cn.com/problems/reverse-words-in-a-string/

注意：此题对比原题有改动

内置函数
split函数之后会自动把首尾的空格去掉

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(s.split()[::-1])

双指针

class Solution:
    def reverseWords(self, s: str) -> str:
        s = s.strip() # 删除首尾空格
        i = j = len(s) - 1
        res = []
        while i >= 0:
            while i >= 0 and s[i] != ' ': 
				i -= 1 # 搜索首个空格
            res.append(s[i + 1: j + 1]) # 添加单词
            while s[i] == ' ': 
				i -= 1 # 跳过单词间空格
            j = i # j 指向下个单词的尾字符
        return ' '.join(res) # 拼接并返回

58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：

输入: s = “abcdefg”, k = 2
输出: “cdefgab”

示例 2：

输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”

限制：
1 <= k < s.length <= 10000

切片

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]

列表遍历拼接

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        res = []
        for i in range(n, len(s)):
            res.append(s[i])
        for i in range(n):
            res.append(s[i])
        return ''.join(res)

字符串遍历拼接

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        res = ‘’
        for i in range(n, n + len(s)):
            res += s[i % len(s)]
        return res

59 - I. 滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
  滑动窗口的位置    最大值
  ----------------------- ---------
  [1 3 -1] -3 5 3 6 7     3
  1 [3 -1 -3] 5 3 6 7     3
1 3 [-1 -3 5] 3 6 7     5
1 3 -1 [-3 5 3] 6 7     5
1 3 -1 -3 [5 3 6] 7     6
1 3 -1 -3 5 [3 6 7]     7

提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/

遍历

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return []
        left, right = 0, k
        res = []
        while right <= len(nums):
            res.append(max(nums[left:right]))
            left += 1
            right += 1
        return res

剪枝

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return []
        window, res = [], []
        for i, x in enumerate(nums):
            if i >= k and window[0] <= i - k:
                window.pop(0)
            while window and nums[window[-1]] <= x:
                window.pop()
            window.append(i)
            if i >= k - 1:
                res.append(nums[window[0]])
        return res

59 - II. 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入:
[“MaxQueue”,“push_back”,“push_back”,“max_value”,“pop_front”,“max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

输入:
[“MaxQueue”,“pop_front”,“max_value”]
[[],[],[]]
输出: [null,-1,-1]

限制：
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5

# 数组憨憨做法
class MaxQueue:

    def __init__(self):
        self.queue = []

    def max_value(self) -> int:
        if not self.queue:
            return -1
        return max(self.queue)

    def push_back(self, value: int) -> None:
        self.queue.append(value)

    def pop_front(self) -> int:
        if not self.queue:
            return -1
        return self.queue.pop(0)

用一个辅助队列

class MaxQueue:

    def __init__(self):
        self.queue=[]
        self.max_queue=[]

    def max_value(self) -> int:
        if not self.queue:
            return -1
        return self.max_queue[0]

    def push_back(self, value: int) -> None:
        self.queue.append(value)
        while self.max_queue and value > self.max_queue[-1]:
            self.max_queue.pop()
        self.max_queue.append(value)

    def pop_front(self) -> int:
        if not self.queue:
            return -1
        if self.queue[0] == self.max_queue[0]:
            self.max_queue.pop(0)
        return self.queue.pop(0)

60. n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例 1:

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

示例 2:

输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

限制：
1 <= n <= 11

动态规划
n个骰子，一共有6**n种情况
n=1, 和为s的情况有 F(n,s)=1 s=1,2,3,4,5,6
n>1 , F(n,s) = F(n-1,s-1)+F(n-1,s-2) +F(n-1,s-3)+F(n-1,s-4)+F(n-1,s-5)+F(n-1,s-6)
可以看作是从前(n-1)个骰子投完之后的状态转移过来。
其中F（N,S）表示投第N个骰子时，点数和为S的次数

class Solution:
    def twoSum(self, n: int) -> List[float]:

        dp = [ [0 for _ in range(6*n+1)] for _ in range(n+1)]
        for i in range(1,7):
            dp[1][i] = 1

        for i in range(2,n+1):
            for j in range(i,i*6+1):
                for k in range(1,7):
                    dp[i][j] +=dp[i-1][j-k]
        res = []
        for i in range(n,n*6+1):
            res.append(dp[n][i]*1.0/6**n)
        return res

61. 扑克牌中的顺子

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

限制：
数组长度为 5
数组的数取值为 [0, 13] .

排序 + 遍历

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        joker = 0
        nums.sort() # 数组排序
        for i in range(4):
            if nums[i] == 0: joker += 1 # 统计大小王数量
            elif nums[i] == nums[i + 1]: return False # 若有重复，提前返回 false
        return nums[4] - nums[joker] < 5 # 最大牌 - 最小牌 < 5 则可构成顺子

集合 Set + 遍历

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        repeat = set()
        ma, mi = 0, 14
        for num in nums:
            if num == 0: continue # 跳过大小王
            ma = max(ma, num) # 最大牌
            mi = min(mi, num) # 最小牌
            if num in repeat: return False # 若有重复，提前返回 false
            repeat.add(num) # 添加牌至 Set
        return ma - mi < 5 # 最大牌 - 最小牌 < 5 则可构成顺子

62. 圆圈中最后剩下的数字

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

输入: n = 5, m = 3
输出: 3

示例 2：

输入: n = 10, m = 17
输出: 2

限制：
1 <= n <= 10^5
1 <= m <= 10^6

模拟题目的操作

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        nums, size, start = [i for i in range(n)], n, 0
        while size != 1:
            i = (m + start - 1) % size
            nums.pop(i)
            start = i
            size -= 1
        return nums[0]

约瑟夫环数学公式

# f(n,m) = (f(n-1,m)+m)%n
# f(1) = 0
class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        res = 0
        for i in range(2, n + 1):
            res = (res + m) % i
        return res

63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制：
0 <= 数组长度 <= 10^5

注意：本题与主站 121 题相同：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

硬解也行

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i in range(len(prices) - 1):
            res = max(res, max(prices[i:]) - prices[i])
        return res

在遍历数组的过程中，维护一个最小值，最小值初试为prices[0]
如果prices[i]大于min，则去更新一下利润res
否则说明当前的prices[i]比min还小，则更新min

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        if not prices:
            return res
        min_ = prices[0]
        for i in prices:
            min_ = min(min_, i)
            res = max(res, i - min_)
        return res

64. 求1+2+…+n

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

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：
1 <= n <= 10000

内置函数sum

class Solution:
    def sumNums(self, n: int) -> int:        
        return sum(range(1, n + 1))

数学公式

class Solution:
    def sumNums(self, n: int) -> int:
        return (n ** 2 + n) >> 1

递归

class Solution:
    def sumNums(self, n: int) -> int:
        if n == 1:
            return 1
        n += self.sumNums(n - 1)
        return n

65. 不用加减乘除做加法

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

示例:

输入: a = 1, b = 1
输出: 2

提示：
a, b 均可能是负数或 0
结果不会溢出 32 位整数

无进位加法：a+b = a^b

n=a⊕b
c=a&b<<1

非进位和：异或运算
进位：与运算+左移一位

s=a+b⇒s=n+c

循环求 n 和 c ，直至进位 c = 0；此时 s = n ，返回 n 即可。

正数与边界数 0xffffffff 按位与（&）操作后仍得到这个数本身的真值：
负数与边界数按位与（&）操作后得到的是对应二进制数补码的真值：
通过查看符号位（最高位，即与 0x7ffffffff ）断a为正数还是负数（0x7ffffffff是最大正数的补码） print(hex(1)) # = 0x1 补码
print(hex(-1)) # = -0x1 负号 + 原码（Python 特色，Java 会直接输出补码）
print(hex(1 & 0xffffffff)) # = 0x1 正数补码
print(hex(-1 & 0xffffffff)) # = 0xffffffff 负数补码
python需要获得负数的补码，所以& 0xFFFFFFFF
a ^ 0xFFFFFFFF是将 1 至 32 位按位取反，前面再加_{表示将整个取反，实际上} a ^ 0xFFFFFFFF表示将 32 位以上的位取反，即由 0 变为 1 ， 1 至 32 位不变。

class Solution:
    def add(self, a: int, b: int) -> int:
        while b: 
            a, b = (a ^ b) & 0xFFFFFFFF, ((a & b) << 1) & 0xFFFFFFFF
        return a if a <= 0x7FFFFFFF else ~ a ^ 0xFFFFFFFF

66. 构建乘积数组

给定一个数组 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]。不能使用除法。

示例:

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

提示：
所有元素乘积之和不会溢出 32 位整数
a.length <= 100000

暴力解法超时

左右数组法

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        n = len(a)
        L, R = [1] * n, [1] * n
        for i in range(1, n):
            L[i] = L[i - 1] * a[i - 1]
        for j in reversed(range(n - 1)):  # 这个语法可以注意下，少见
            R[j] = R[j + 1] * a[j + 1]
        for i in range(n):
            L[i] = L[i] * R[i]
        return L

语法：for i in reversed(range(n)):

67. 把字符串转换成整数

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2³¹, 2³¹ − 1]。如果数值超过这个范围，请返回 INT_MAX (2³¹ − 1) 或 INT_MIN (−2³¹) 。

示例 1:

输入: “42”
输出: 42

示例 2:

输入: " -42"
输出: -42
解释: 第一个非空白字符为 ‘-’, 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例 3:

输入: “4193 with words”
输出: 4193
解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字。

示例 4:

输入: “words and 987”
输出: 0
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。
因此无法执行有效的转换。

示例 5:

输入: “-91283472332”
输出: -2147483648
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。
因此返回 INT_MIN (−2³¹) 。

注意：本题与主站 8 题相同：https://leetcode-cn.com/problems/string-to-integer-atoi/

用try except强转

class Solution:
    def strToInt(self, str: str) -> int:
        str = str.lstrip()
        if len(str) == 0:
            return 0
        res = 0
        i = 2 if str[0] == '+' or str[0] == '-' else 1
        while i <= len(str):
            try:
                res = int(str[:i])
                i += 1
            except:
                break
        if res < -2 ** 31:
            return -2 ** 31
        if res > 2 ** 31 - 1:
            return 2 ** 31 - 1
        return res

也可以一步一步来遍历

class Solution:
    def strToInt(self, str: str) -> int:
        str = str.strip() # 删除首尾空格
        if not str: return 0 # 字符串为空则直接返回
        res, i, sign = 0, 1, 1
        int_max, int_min, bndry = 2 ** 31 - 1, -2 ** 31, 2 ** 31 // 10
        if str[0] == '-': sign = -1 # 保存负号
        elif str[0] != '+': i = 0 # 若无符号位，则需从 i = 0 开始数字拼接
        for c in str[i:]:
            if not '0' <= c <= '9' : break # 遇到非数字的字符则跳出
            if res > bndry or res == bndry and c > '7': return int_max if sign == 1 else int_min # 数字越界处理
            res = 10 * res + ord(c) - ord('0') # 数字拼接。“此数字的 ASCII 码” 与 “ 00 的 ASCII 码” 相减
        return sign * res

68 - I. 二叉搜索树的最近公共祖先

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

注意：本题与主站 235 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

dfs递归

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if q.val < root.val > p.val :  # p、q都比root小，查找root.left
            return self.lowestCommonAncestor(root.left, p, q)
        if q.val > root.val < p.val:  # p、q都比root大，查找root.right
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

68 - II. 二叉树的最近公共祖先

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

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

注意：本题与主站 236 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

dfs、递归

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

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root == p or root == q:  # 如果找到了q或者p，则返回root
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if right and left:  # 说明左树和右树都找到，则返回根树
            return root
        if not right:  # 说明左树找到q或p,返回left
            return left
        if not left:  # 同理
            return right