剑指Offer题集（力扣）

剑指Offer题集（力扣题单）

剑指 Offer 03. 数组中重复的数字

难度简单1155

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000

方法一：哈希

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            if(set.contains(num)) return num;
            set.add(num);
        }
        return -1;
    }
}

方法二：原地交换（鸽巢原理）

class Solution {
    // 鸽巢原理，因为出现的元素值 < nums.size(); 所以我们可以将见到的元素 放到索引的位置，
    // 如果交换时，发现索引处已存在该元素，则重复 O(N) 空间 O(1)
    public int findRepeatNumber(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n; i++){
            while(i != nums[i]){
                if(nums[i] == nums[nums[i]]){
                    return nums[i];
                }
                int tmp = nums[i];// 将nums[i] 和 nums[nums[i]] 交换
                nums[i] = nums[tmp];
                nums[tmp] = tmp;
            }
        }
        return -1;
    }
}

剑指 Offer 04. 二维数组中的查找

难度中等937

在一个 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

题解：可以从左上角或者右下角开始查找，等同于n次二分查找

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length == 0 || matrix[0].length == 0)
            return false;
        int n = matrix.length, m = matrix[0].length;
        int i = 0, j = m-1;
        while(i < n && j >= 0){
            if(matrix[i][j] == target) return true;
            else if(matrix[i][j] < target) i++;
            else j--;
        }
        return false;
    }
}

剑指 Offer 05. 替换空格

难度简单466

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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for(char c : s.toCharArray()){
            if(c == ' ') sb.append("%20");
            else sb.append(c);
        }
        return sb.toString();
    }
}

// 使用api
// Java中的replace方法替换任意普通字符串，replaceFirst和replaceAll替换能匹配给定正则表达式的字符串（因此可能较慢）
class Solution {
    public String replaceSpace(String s) {
        return s.replace(" ", "%20");
    }
}

剑指 Offer 06. 从尾到头打印链表

难度简单414

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

方法一：使用递归（递归返回的过程就是从尾到头遍历的过程）

class Solution {
    List<Integer> res = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        dfs(head);
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    public void dfs(ListNode node){
        if(node == null) return;
        dfs(node.next);
        res.add(node.val);
    }
}

方法二：使用栈

class Solution {
    public int[] reversePrint(ListNode head) {
        Deque<Integer> dq = new ArrayDeque<>();
        ListNode p = head;
        while(p != null){
            dq.push(p.val);
            p = p.next;
        }
        int[] res = new int[dq.size()];
        int i = 0;
        while(!dq.isEmpty()){
            res[i++] = dq.poll();
        }
        return res;
    }
}

🎃剑指 Offer 07. 重建二叉树[前序+中序]

难度中等1056

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：

0 <= 节点个数 <= 5000

根据前序和中序可以构造一颗二叉树，根据中序和后续也可以构建一颗二叉树。 反正必须要有中序才能构建，因为没有中序，你没办法确定树的形状。 比如先序和后序是不能构建唯一的一颗二叉树的。 例如： 先序为：[1, 2] 后序为：[2, 1]

可以构建如下

    1 | 1
  /   |	  \
2  	  |	    2

这个面试官也会问的。回到这个题目。

题解：文章来源地址https://www.toymoban.com/news/detail-436225.html

1. 中序遍历根据根节点可以知道左子树、右子树的长度
2. 先序遍历可以知道根节点
   • 创建根节点
   • 获得当前根节点在中序list中的位置（当前根节点左子树的节点个数：idx - in_left）
   • 递归创建根节点左子树：左子树根的索引为 先序中根节点+1
   • 递归创建根节点右子树：右子树根的索引为 先序中的 当前根位置 + 左子树的数量 + 1

class Solution {
    HashMap<Integer, Integer> map = new HashMap<>();//标记中序遍历中元素的位置
    int[] preorder;// 保留的先序遍历，方便递归时依据索引查看先序遍历的值

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        //将中序遍历的值及索引放在map中，方便递归时获取左子树与右子树的数量及其根的索引
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        //三个索引分别为
        //当前根的的索引
        //递归树的左边界，即数组左边界
        //递归树的右边界，即数组右边界
        return recur(0,0,inorder.length-1);
    }

    TreeNode recur(int pre_root, int in_left, int in_right){
        if(in_left > in_right) return null;// 相等的话就是自己
        TreeNode root = new TreeNode(preorder[pre_root]);//获取root节点
        int idx = map.get(preorder[pre_root]);//获取在中序遍历中根节点所在索引，以方便获取左子树的数量（idx - in_left）
        //左子树的根的索引为先序中的根节点+1 
        //递归左子树的左边界为原来的中序in_left
        //递归左子树的右边界为中序中的根节点索引-1
        root.left = recur(pre_root+1, in_left, idx-1);
        //右子树的根的索引为先序中的 当前根位置 + 左子树的数量 + 1
        //递归右子树的左边界为中序中当前根节点+1
        //递归右子树的右边界为中序中原来右子树的边界
        root.right = recur(pre_root + (idx - in_left) + 1, idx+1, in_right);
        return root;

    }
}

106.重建二叉树[后序+中序]

难度中等1002

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder 和 postorder 都由 不同 的值组成
• postorder 中每一个值都在 inorder 中
• inorder 保证是树的中序遍历
• postorder 保证是树的后序遍历

题解：

1. 中序遍历根据根节点可以知道左子树、右子树的长度
2. 后序遍历可以知道根节点
   • 创建根节点
   • 获得当前根节点在中序list中的位置（当前根节点右子树的节点个数：in_right - idx）
   • 递归创建根节点左子树：左子树根的索引为 后序中根节点 - 右子树的节点个数 - 1
   • 递归创建根节点右子树：右子树根的索引为 后序中根节点 - 1

class Solution {
    Map<Integer, Integer> map = new HashMap<>();// 标记中序遍历中元素的位置
    int[] postorder; // 保留的后序遍历，方便递归时依据索引查看后序遍历的值
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        //将中序遍历的值及索引放在map中，方便递归时获取左子树与右子树的数量及其根的索引
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        //三个索引分别为
        //当前根的的索引(后序遍历根索引即为最后一个元素值)
        //递归树的左边界，即数组左边界
        //递归树的右边界，即数组右边界
        return recur(postorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode recur(int post_root, int in_left, int in_right){
        if(in_left > in_right) return null;
        TreeNode root = new TreeNode(postorder[post_root]); //获取root节点
        //获取在中序遍历中根节点所在索引，以方便获取右子树的数量（in_right - idx）
        int idx = map.get(postorder[post_root]);
        //左子树的根的索引为 后序中的根节点- 右子树的数量 - 1 
        root.left = recur(post_root - (in_right - idx) - 1, in_left, idx-1);
        //右子树的根的索引为 后序中的根节点-1 
        root.right = recur(post_root - 1, idx+1, in_right);
        return root;
    }
}

剑指 Offer 09. 用两个栈实现队列

难度简单735

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

示例 1：

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

示例 2：

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

提示：

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

class CQueue {

    Deque<Integer> dq1;
    Deque<Integer> dq2;

    public CQueue() {   
        dq1 = new ArrayDeque<>();
        dq2 = new ArrayDeque<>();
    }
    
    public void appendTail(int value) {
        dq1.push(value);
    }
    
    public int deleteHead() {
        if(dq1.isEmpty()) return -1;
        while(!dq1.isEmpty()){
            dq2.push(dq1.pop());
        }
        int res = dq2.poll();
        while(!dq2.isEmpty()){
            dq1.push(dq2.pop());
        }
        return res;
    }
}

Deque的常用方法

创建对象：Deque<Integer> deque = new ArrayDeque<>();

Deque接口扩展(继承)了 Queue 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：

双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

剑指 Offer 10- I. 斐波那契数列

难度简单474

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(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

记忆化搜索

class Solution {
    private static final int MOD = (int)1e9+7;
    int[] cache;
    public int fib(int n) {
        cache = new int[n+1];
        Arrays.fill(cache, -1);
        return dfs(n);
    }

    public int dfs(int i){
        if(i <= 1) return i; // 递归边界f(0) = 0, f(1) = 1
        if(cache[i] >= 0) return cache[i];
        int res = 0;
        // 状态转移方程：F(N) = F(N - 1) + F(N - 2)
        res = (res + dfs(i-1)) % MOD;
        res = (res + dfs(i-2)) % MOD;
        return cache[i] = res;
    }
}

转递推：

class Solution {
    private static final int MOD = (int)1e9+7;
    public int fib(int n) {
        if(n < 2) return n;
        // 定义f[i] 表示斐波那契数列的第i项
        int[] f = new int[n+1];
        f[0] = 0;
        f[1] = 1;
        for(int i = 2; i <= n; i++){
            f[i] = (f[i-1] + f[i-2]) % MOD;
        }
        return f[n];
    }
}

空间优化：可以看到只用了三个值：f[n]、f[n-1]、f[n-2]

class Solution {
    private static final int MOD = (int)1e9+7;
    public int fib(int n) {
        if(n < 2) return n;
        int a = 0, b = 1; //  a对应f[n-2], b对应f[n-1]
        // 每次递推时更新b为下一次的f[n-1]，即当前的f[n]
        for(int i = 2; i <= n; i++){
            int c = (a + b) % MOD;
            a = b;
            b = c;
        }
        return b;
    }
}

剑指 Offer 10- II. 青蛙跳台阶问题【爬楼梯】

难度简单385

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

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

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

提示：

• 0 <= n <= 100

class Solution {
    /**
    	举个例子，假如，你想跳到第三个台阶，
		那由于题目限制一步一阶或两阶，那就只有两种方法，
		1:通过第三阶的上一步跳一下一阶	
		2:通过第三阶的上两步跳一下两阶
		由此得出，不论是第几阶梯，都只有两种方案能到达 所以f(n)=f(n-1)+f(n-2)
		//##
		站在n台阶的角度理解就行了，能来到n的，上一步要么是n-1，要么是n-2。
		自然就是fn=fn-1 + fn-2了，fn-2代表的是fn的上一步，自然不应该考虑跳一个台阶的情况。
    */
    private static final int MOD = (int)1e9+7;
    public int numWays(int n) {
        if(n == 0) return 1;
        int[] f = new int[n+1];
        f[0] = 1; // 台阶是0的时候，默认有一种方案，就是不用跳
        f[1] = 1;
        for(int i = 2; i <= n; i++){
            f[i] = (f[i-1] + f[i-2]) % MOD;
        }
        return f[n];
    }
}

剑指 Offer 11. 旋转数组的最小数字

难度简单808

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

示例 1：

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

示例 2：

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

提示：

• n == numbers.length
• 1 <= n <= 5000
• -5000 <= numbers[i] <= 5000
• numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

class Solution {
    public int minArray(int[] numbers) {
        int left = 0, right = numbers.length-1;
        while(left < right){
            int mid = (left + right) >> 1;
            // 只要右边比中间大，那右边一定是有序数组
            if(numbers[right] > numbers[mid]) right = mid;
            else if(numbers[right] < numbers[mid]) left = mid + 1; 
            else right--; // 去重
        }
        return numbers[right];
    }
}

剑指 Offer 12. 矩阵中的路径

难度中等787

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例 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

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和word仅由大小写英文字母组成

class Solution {
    int[][] dirts = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    char[][] board;
    char[] s;
    boolean[][] vis;
    int n, m;
    boolean res = false;
    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.s = word.toCharArray();
        n = board.length; m = board[0].length;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(board[i][j] == s[0]){
                    vis = new boolean[n][m];
                    vis[i][j] = true;
                    if(dfs(i, j, 1)) return true;
                }
            }
        } 
        return false;
    }

    public boolean dfs(int i, int j, int idx){
        if(idx == s.length){
            return true;
        }
        boolean res = false;
        for(int[] d : dirts){
            int x = i + d[0], y = j + d[1];
            if(!res && x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && board[x][y] == s[idx]){
                vis[x][y] = true;
                res |= dfs(x, y, idx+1);
                vis[x][y] = false;
            }
        }
        return res;
    }
}

剑指 Offer 13. 机器人的运动范围

难度中等627

地上有一个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

class Solution {
    int[][] dirts = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    boolean[][] vis;
    int n, m, k;
    int res;
    public int movingCount(int m, int n, int k) {
        this.n = n; this.m = m; this.k = k;
        res = 0;
        vis = new boolean[m][n];
        vis[0][0] = true;
        dfs(0, 0, 0);
        return res;
    }

    public void dfs(int i, int j, int cnt){
        res += 1;
        for(int[] d : dirts){
            int x = i + d[0], y = j + d[1];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && cnt(x,y) <= k){
                vis[x][y] = true;
                dfs(x, y, cnt(x, y));
            }
        }
    }

    public int cnt(int x, int y){
        int total = 0;
        while(x != 0){
            total += x % 10;
            x = x / 10;
        }
        while(y != 0){
            total += y % 10;
            y = y / 10;
        }
        return total;
    }
}

🎉剑指 Offer 14- I. 剪绳子

难度中等589

给你一根长度为 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

class Solution {
    /** https://leetcode.cn/problems/jian-sheng-zi-lcof/solution/by-nehzil-w61p/
     * 1. 确定dp数组下标含义 将长度为 i 的绳子剪成至少两段绳子之后，这些绳子长度的最大乘积
     * 2. 递推公式 dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j);
     * 3. 初始化 dp[2] = 1;
     * 4. 遍历顺序 从前向后遍历就可以;
     * 5. 推导结果;
     */
    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        // 0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此 dp[0]=dp[1]=0。
        dp[2] = 1; // 长度为2的绳子可以拆分为1和1
        for(int i = 3; i <= n; i++){
            for(int j = 1; j < i-1; j++){
                // 假设对长度为 i 绳子剪出的第一段绳子长度是 j
                //    方案1：将 i 剪成 j 和 i-j 长度的绳子，且 i−j 不再继续剪，此时的乘积是 j×(i−j) 
                //    方案2：将 i 剪成 j 和 i−j 长度的绳子，且 i−j 继续剪成多段长度的绳子，此时的乘积是 j×dp[i−j] 。
                // 因此，当 j 固定时，有 dp[i]=max(j×(i−j),j×dp[i−j])。由于 j 的取值范围是 1 到 i ，需要遍历所有的 j 得到dp[i]的
                dp[i] = Math.max(dp[i], Math.max((i-j)*j, dp[i-j] * j));
            }
        }
        return dp[n]; // dp[n]的值即为将长度为n的绳子拆分成至少两段绳子之后，这些绳子长度的最大乘积。
    }
}

剑指 Offer 14- II. 剪绳子 II

难度中等252

给你一根长度为 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

这一题已经不能用动态规划了，取余之后max函数就不能用来比大小了。

题解：此题与 面试题14- I. 剪绳子 主体等价，唯一不同在于本题目涉及 “大数越界情况下的求余问题” 。在I 减绳子此基础上，每累积3之后，要取模。

class Solution {
    public int cuttingRope(int n) {
      // 1、所有绳子的长度相等时，乘积最大 
      // 2、最优绳长为3，先按3分段，即n=3*a+b,则b=0,1,2.
      //    b=0则直接返回3^a取余; 
      //    b=1,将一个1+3换成2+2，即返回(3^(a-1)*4)取余; 
      //    b=2,则返回(3^a*2)取余
      if(n==2) return 1;
      if(n==3) return 2;
      long res=1;
      while(n>4){
          res=res*3;
          res=res%1000000007;
          n=n-3;//每次去掉3
      }
        //出来循环只有三种情况，分别是n=2、3、4,每种正好分成2、3、4
        return (int)((res*n)%1000000007);
    }
}

剑指 Offer 15. 二进制中1的个数

难度简单315

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

• 输入必须是长度为 32 的 二进制串 。

题解：把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        //return Integer.bitCount(n);
        int res = 0;
        while(n != 0){
            res++;
            n = n &  (n-1);
        }
        return res;
    }
}

剑指 Offer 16. 数值的整数次方

难度中等410

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

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

提示：

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

题解：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/by-ren-feiye-cgph/

class Solution {
    /**
    快速幂算法原理:
        如需求数据 a 的幂次，此处 a 可以为数也可以为矩阵，常规做法需要对a进行不断的乘积即 a * a * a * ... 此处的时间复杂度将为 O(n)
    [优化步骤1：]
    以求 3^10 的结果为例：3^10 = 3*3*3*3*3*3*3*3*3*3 = 9^5 = 9^4*9 = 81^2*9 = 6561*9
    
    基于以上原理，我们在计算一个数的多次幂时，可以先判断其幂次的奇偶性，然后：
        如果幂次为偶直接 base(底数) 作平方，power(幂次) 除以2
        如果幂次为奇则底数平方，幂次整除于2然后再多乘一次底数

    [优化步骤2：]
    对于以上涉及到 [判断奇偶性] 和 [除以2] 这样的操作。使用系统的位运算比普通运算的效率是高的，因此可以进一步优化：
        把 power % 2 == 1 变为 (power & 1) == 1
        把 power = power / 2 变为 power = power >> 1
     */
    public double myPow(double x, int n) {
        //将正数n和负数n都给转换为正数n
        //注意：Java 代码中 int32 变量n∈[−2147483648,2147483647]
        //因此当 n = -2147483648 时执行 n = -n 会因越界而赋值出错
        //我们此处一开始就把 n 用 long 存储
        long b = n;

        if (n < 0) {
            b = -b;
            x = 1 / x;
        }
        return culc(x, b);
    }

    //快速幂模版
    //递归的进行x的n次方计算
    public double culc(double base, long power) {
        double res = 1.0;

        while (power > 0) {
            //两种情况会进入if语句：
            //1.幂次若为奇数，提前多乘一次x
            //2.当幂次除到1，把x赋值给res
            if ((power & 1) == 1) {
                res *= base;
            }
            //幂次除以2
            power = power >> 1;
            //底数平方
            base = base * base;
        }
        return res;
    }
}

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

难度简单290

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

示例 1:

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

说明：

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

普通解法

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

大数问题解法

在数字很大的情况下，哪怕long类型也无法承载，那必须要用字符串保存。

对于本题其实就是对数字0_{9的**全排列**，从1位数0}9的全排列到n位数0~9的全排列，其中要注意的是数字开头不应该有0。

简单提一下全排列，比如对于数字1，2，3的全排列是:

123, 132, 213, 231, 312, 321

为了能够测试通过，最后把字符串形式变成了int形式，其实应该返回字符串数组

以下是具体步骤

1. 为了避免数字开头出现0，先把首位first固定，first取值范围为1~9
2. 用digit表示要生成的数字的位数，本题要从1位数一直生成到n位数，对每种数字的位数都生成一下首位，所以有个双重for循环
3. 生成首位之后进入递归生成剩下的digit - 1位数，从0~9中取值
4. 递归的中止条件为已经生成了digit位的数字，即index == digit，将此时的数num转为int加到结果res中

class Solution:
    def printNumbers(self, n: int) -> List[int]:
        # 全排列问题（枚举第i位选哪个）
        def dfs(index: int, num: List[int], digit: int):
            if index == digit:
                res.append(int(''.join(num)))
                return
            for i in range(10):
                num.append(str(i))
                dfs(index + 1, num, digit)
                num.pop()
        
        res = []
        for digit in range(1, n+1):
            for first in range(1, 10):
                num = [str(first)]
                dfs(1, num, digit)
        return res

剑指 Offer 18. 删除链表的节点

难度简单306

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

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

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

示例 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(-1)
        dummy.next = head
        p = dummy
        while p.next:
            if p.next.val == val:
                p.next = p.next.next
                break
            p = p.next
        return dummy.next

🎉剑指 Offer 19. 正则表达式匹配

难度困难536

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

示例 1:

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

示例 2:

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

题解：https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/hui-su-dong-tai-gui-hua-by-ml-zimingmeng/

方法一：记忆化搜索

首先，我们考虑只有 '.' 的情况。这种情况会很简单：我们只需要从左到右依次判断 s[i] 和 p[i] 是否匹配。

# 只有 '.' 的情况
def isMatch(self,s:str, p:str) -> bool:
    if not p: return not s # 边界条件

    first_match = s and p[0] in {s[0],'.'} # 比较第一个字符是否匹配

    return first_match and self.isMatch(s[1:], p[1:])

如果有星号，它会出现在 p[1] 的位置，这时有两种情况：

• 星号代表匹配 0 个前面的元素。如 '##' 和 a*##，这时我们直接忽略 p 的 a*，比较 ## 和 ##；
• 星号代表匹配一个或多个前面的元素。如 aaab 和 a*b，这时我们将忽略 s 的第一个元素，比较 aab 和 a*b。

以上任一情况忽略掉元素进行比较时，剩下的如果匹配，我们认为 s 和 p 是匹配的。

class Solution:
    # 模式中的字符'.'表示任意一个【字符】，而'*'表示它前面的【字符】可以出现任意次（含0次）
    def isMatch(self, s: str, p: str) -> bool:
        if not p:
            return not s # 当p空串时，s也应该是空串
        # 第一个字母是否匹配
        first_match = bool(s and p[0] in {s[0], '.'})
        # 如果 p 第二个字母是 *
        if len(p) >= 2 and p[1] == "*":
            # 星号代表匹配 0 个前面的元素,直接忽略 p 的前两个元素
            return self.isMatch(s, p[2:]) or \
            first_match and self.isMatch(s[1:], p)
            # 星号代表匹配一个或多个前面的元素，直接忽略s的第一个元素
        else:
            return first_match and self.isMatch(s[1:], p[1:])

方法二：动态规划

状态：

很容易想到，dp[i][j] 表示的状态是 s 的前 i 项和 p 的前 j 项是否匹配。

转移方程：

现在如果已知了 dp[i-1][j-1] 的状态，我们该如何确定 dp[i][j] 的状态呢？我们可以分三种情况讨论，其中，前两种情况考虑了所有能匹配的情况，剩下的就是不能匹配的情况了：

1. s[i] == p[j] or p[j] == '.'：比如 abb 和 abb，或者 abb 和 ab. ，很容易得到 dp[i][j] = dp[i-1][j-1] = True。因为 ab 和 ab 是匹配的，如果后面分别加一个 b，或者 s 加一个 b 而 p 加一个 . ，仍然是匹配的。
2. p[j] == '*'：当 p[j] 为星号时，由于星号与前面的字符相关，因此我们比较星号前面的字符 p[j-1] 和 s[i] 的关系。根据星号前面的字符与 s[i] 是否相等，又可分为以下两种情况：
   • p[j-1] != s[i]：如果星号前一个字符匹配不上，星号匹配了 0 次，应忽略这两个字符，看 p[j-2] 和 s[i] 是否匹配。 这时 dp[i][j] = dp[i][j-2]。
   • p[j-1] == s[i] or p[j-1] == '.':星号前面的字符可以与 s[i] 匹配，这种情况下，星号可能匹配了前面的字符的 0 个，也可能匹配了前面字符的多个，当匹配 0 个时，如 ab 和 abb*，或者 ab 和 ab.* ，这时我们需要去掉 p 中的 b* 或 .* 后进行比较，即 dp[i][j] = dp[i][j-2]；当匹配多个时，如 abbb 和 ab*，或者 abbb 和 a.*，我们需要将 s[i] 前面的与 p 重新比较，即 dp[i][j] = dp[i-1][j]
3. 其他情况：以上两种情况把能匹配的都考虑全面了，所以其他情况为不匹配，即 dp[i][j] = False

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # 边界条件，考虑 s 或 p 分别为空的情况
        if not p: return not s
        if not s and len(p) == 1: return False
        m, n = len(s), len(p)
        dp = [[False for _ in range(n+1)] for _ in range(m+1)]
        dp[0][0] = True
        dp[0][1] = False
        # 初始化，'*'表示它前面的【字符】可以出现任意次（含0次）
        for c in range(2, n+1):
            j = c - 1
            if p[j] == '*':
                dp[0][c] = dp[0][c-2]
        
        for r in range(1, m+1):
            i = r - 1
            for c in range(1, n+1):
                j = c - 1
                if s[i] == p[j] or p[j] == '.':
                    dp[r][c] = dp[r-1][c-1]
                elif p[j] == '*':  # ‘*’前面的字符匹配s[i] 或者为'.'
                    if p[j - 1] == s[i] or p[j - 1] == '.':
                        dp[r][c] = dp[r-1][c] or dp[r][c-2]
                    else: # ‘*’匹配了0次前面的字符
                        dp[r][c] = dp[r][c-2]
                else:
                    dp[r][c] = False
        return dp[m][n]
        

java

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        // 边界条件，考虑 s 或 p 分别为空的情况
        if(m == 0) return n == 0;
        if(n == 0 && m == 1) return false;
        boolean[][] dp = new boolean[n+1][m+1];
        dp[0][0] = true;
        for(int i = 2; i <= m; i++){
            if(p.charAt(i-1) == '*')
                // 如果星号前一个字符匹配不上，星号匹配了 0 次，应忽略这两个字符，看 p[j-2] 和 s[i] 是否匹配。
                dp[0][i] = dp[0][i-2];
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.')
                    // s的字符和p的字符是匹配的
                    dp[i][j] = dp[i-1][j-1];
                else if(p.charAt(j-1) == '*'){
                    //星号前面的字符可以与 s[i] 匹配,dp[i][j-2]：匹配0个，dp[i-1][j]匹配多个
                    if(p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.'){
                        dp[i][j] = dp[i-1][j] || dp[i][j-2];
                    }else{
                        //如果星号前一个字符匹配不上，星号匹配了 0 次，应忽略p这两个字符，看p[j-2]和s[i]是否匹配。
                        dp[i][j] = dp[i][j-2];
                    }
                }
            }
        }
        return dp[n][m];
    }
}

剑指 Offer 20. 表示数值的字符串

难度中等463

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

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

1. 若干空格
2. 一个 小数 或者 整数
3. （可选）一个 'e' 或 'E' ，后面跟着一个 整数
4. 若干空格

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

1. （可选）一个符号字符（'+' 或 '-'）
2. 下述格式之一：
   1. 至少一位数字，后面跟着一个点 '.'
   2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
   3. 一个点 '.' ，后面跟着至少一位数字

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

1. （可选）一个符号字符（'+' 或 '-'）
2. 至少一位数字

部分数值列举如下：

• ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]

部分非数值列举如下：

• ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

示例 1：

输入：s = "0"
输出：true

示例 2：

输入：s = "e"
输出：false

示例 3：

输入：s = "."
输出：false

示例 4：

输入：s = "    .1  "
输出：true

提示：

• 1 <= s.length <= 20
• s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。

题解：

编码没什么难度，难点在于归纳各种正确的情况

• ‘.’出现正确情况：只出现一次，且在e的前面

• ‘e’出现正确情况：只出现一次，且出现前有数字

• ‘+’‘-’出现正确情况：只能在开头和e后一位

class Solution {
    public boolean isNumber(String s) {
        if (s == null || s.length() == 0) return false;
        //去掉首位空格
        s = s.trim();
        boolean numFlag = false;
        boolean dotFlag = false;
        boolean eFlag = false;
        for (int i = 0; i < s.length(); i++) {
            //判定为数字，则标记numFlag
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                numFlag = true;
                //判定为.  需要没出现过.并且没出现过e
            } else if (s.charAt(i) == '.' && !dotFlag && !eFlag) {
                dotFlag = true;
                //判定为e，需要没出现过e，并且出过数字了
            } else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && !eFlag && numFlag) {
                eFlag = true;
                numFlag = false;//为了避免123e这种请求，出现e之后就标志为false
                //判定为+-符号，只能出现在第一位或者紧接e后面
            } else if ((s.charAt(i) == '+' || s.charAt(i) == '-') && (i == 0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) {

                //其他情况，都是非法的
            } else {
                return false;
            }
        }
        return numFlag;
    }
}

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

难度简单296

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

示例：

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

提示：

1. 0 <= nums.length <= 50000
2. 0 <= nums[i] <= 10000

// Go 用一个下标记录奇数最后一个元素位置，遍历数组，遇到奇数直接和前面最后一个偶数对调直接对调
func exchange(nums []int) []int {
    a := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] % 2 == 1 {
            nums[i], nums[a] = nums[a], nums[i]
            a += 1
        }
    }
    return nums
}
// Python
class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        a, n = 0, len(nums)
        for i in range(n):
            if nums[i] % 2 != 0:
                tmp = nums[a]
                nums[a] = nums[i]
                nums[i] = tmp
                a += 1
        return nums

方法二：快排思想：

对于升序排序我们都知道(除了相等)：将数组分成两半，逻辑上的数组肯定是：左小右大

根据题干要求：所有奇数在数组的前半部分，所有偶数在数组的后半部分

• 根据这个特点可以进行类比 => 左奇右偶

基于快速排序来说：将基准右边比基准小的数与基准左边比基准大的数互换

• 类比左奇右偶来说：将右边的奇数与基准左边的偶数互换
• 基于双指针思路：分别找到右边的奇数和左边的偶数的指针位置，进行交换

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        left, right = 0, len(nums)-1 # 定义左边偶数，右边奇数指针
        while left < right:
            while left < right and (nums[left] % 2 != 0):
                left += 1 # 找到左边的偶数指针
            while left < right and (nums[right] % 2 == 0):
                right -= 1 # 找到右边的奇数指针
            tmp = nums[left] # 进行交换
            nums[left] = nums[right]
            nums[right] = tmp
        return nums

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

难度简单455

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

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

返回链表 4->5.

题解：

方法一：同向双指针（快慢指针）

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head
        p = dummy
        while k > 0:
            p = p.next
            k -= 1
        res = dummy
        while p:
            p = p.next
            res = res.next
        return res

剑指 Offer 24. 反转链表

难度简单570

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

示例:

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

限制：

0 <= 节点个数 <= 5000

递推法：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        newhead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return newhead

迭代法：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        p = head
        res = ListNode(-1)
        while p:
            nxt = p.next
            p.next = res.next
            res.next = p
            p = nxt
        return res.next

剑指 Offer 25. 合并两个排序的链表

难度简单345

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

示例1：

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

限制：

0 <= 链表长度 <= 1000

方法一：迭代

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        i, j = l1, l2
        res = ListNode(-1)
        cur = res
        while i and j:
            if i.val < j.val:
                cur.next = ListNode(i.val)
                cur = cur.next
                i = i.next
            else:
                cur.next = ListNode(j.val)
                cur = cur.next
                j = j.next
        while i:
            cur.next = ListNode(i.val)
            cur = cur.next
            i = i.next
        while j:
            cur.next = ListNode(j.val)
            cur = cur.next
            j = j.next
        return res.next

方法二：递归

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 递归边界：两个链表有一个是空的
        if not l1: # l1为空
            return l2
        if not l2:
            return l1
        pre = None
        # 两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并
        if l1.val < l2.val:
            pre = l1
            pre.next = self.mergeTwoLists(l1.next, l2)
        else:
            pre = l2
            pre.next = self.mergeTwoLists(l1, l2.next)
        return pre

🎉剑指 Offer 26. 树的子结构

难度中等741

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

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

示例 1：

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

示例 2：

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

限制：

0 <= 节点个数 <= 10000

题解：

• 首先，我们函数isSubStructure的作用是判断B是不是A的子结构，如果B为A左子树或右子树的子结构的话，也满足题意，所以递归体现在返回dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
• dfs怎么构建呢？
• 当B的节点为空时，返回true，因为无论对比的A节点是否为空都满足子结构条件。
• 在B的节点不为空时，如果A节点为空则不符合条件为false，不为空则进一步遍历，需要满足根节点的值相等&&遍历左子树的值相等&&遍历右子树的值相等。

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        # 注意区分子结构和子树 572. 另一棵树的子树
        if not A or not B:
            return False
        return self.hasSubStructure(A, B) or \
                self.isSubStructure(A.left, B) or \
                self.isSubStructure(A.right, B)
    
    def hasSubStructure(self, A, B: TreeNode) -> bool:
        if not B:
            return True
        if not A or A.val != B.val:
            return False
        return self.hasSubStructure(A.left, B.left) and \
                self.hasSubStructure(A.right, B.right)

剑指 Offer 27. 二叉树的镜像

难度简单354

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

例如输入：

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

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

剑指 Offer 28. 对称的二叉树

难度简单446

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

例如，二叉树 [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

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def check(node1, node2: TreeNode) -> bool:
            if not node1 and not node2:
                return True
            if not node1 or not node2:
                return False
            return node1.val == node2.val and \
                    check(node1.left, node2.right) and \
                    check(node1.right, node2.left)
        
        if not root:
            return True
        return check(root, root)

剑指 Offer 29. 顺时针打印矩阵

难度简单528

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

示例 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

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 {
        return make([]int, 0)
    }
    l := 0
    r := len(matrix[0])-1
    t := 0
    b := len(matrix)-1
    res := make([]int, (r+1) * (b+1))
    x := 0
    for {
        for i := l; i <= r; i++ {
            res[x] = matrix[t][i]
            x++
        }
        t++
        if t > b {break}
        for i := t; i <= b; i++ {
            res[x] = matrix[i][r]
            x++
        }
        r--
        if l > r {break}
        for i := r; i >= l; i-- {
            res[x] = matrix[b][i]
            x++
        }
        b--
        if t > b {break}
        for i := b; i >= t; i-- {
            res[x] = matrix[i][l]
            x++
        }
        l++
        if l > r {break} 
    }
    return res
}

剑指 Offer 30. 包含min函数的栈

难度简单492

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.

提示：

1. 各函数的调用总次数不超过 20000 次

题解：

维护一个栈，保存当前栈顶元素和栈中最小元素值

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.st = [] # 当前栈顶元素，栈中最小元素值


    def push(self, x: int) -> None:
        if len(self.st) == 0:
            self.st.append((x, x))
            return
        _, m = self.st[-1]
        if m > x: m = x
        self.st.append((x, m))
        return

    def pop(self) -> None:
        self.st.pop()

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

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

剑指 Offer 31. 栈的压入、弹出序列

难度中等443

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {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 之前弹出。

提示：

1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed 是 popped 的排列。

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        i, j = 0, 0
        st = []
        for i in range(len(pushed)):
            st.append(pushed[i])
            while len(st) > 0 and st[-1] == popped[j]:
                st.pop()
                j += 1
        if j != len(popped):
            return False
        return True

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

难度中等273

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

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

    3
   / \
  9  20
    /  \
   15   7

返回：

[3,9,20,15,7]

提示：

1. 节点总数 <= 1000

使用list模拟队列

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

使用queue=collections.deque()双端队列

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        res = []
        if not root:
            return res
        q = collections.deque()
        q.append(root)
        while q:
            size = len(q)
            while size > 0:
                node = q.pop()
                res.append(node.val)
                if node.left: q.appendleft(node.left)
                if node.right: q.appendleft(node.right)
                size -= 1
        return res

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

难度简单288

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

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

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

提示：

1. 节点总数 <= 1000

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

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

难度中等285

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

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

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [20,9],
  [15,7]
]

提示：

1. 节点总数 <= 1000

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root:
            return res
        q = [root]
        depth = 0
        while q:
            nxt = []
            tmp = []
            depth += 1
            for node in q:
                tmp.append(node.val)
                if node.left: nxt.append(node.left)
                if node.right: nxt.append(node.right)
            if depth % 2 == 0: tmp.reverse()
            res.append(tmp)
            q = nxt
        return res

🎃剑指 Offer 33. 二叉搜索树的后序遍历序列

难度中等719

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

参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3

示例 1：

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

示例 2：

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

提示：

1. 数组长度 <= 1000

题解：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/di-gui-he-zhan-liang-chong-fang-shi-jie-jue-zui-ha/

方法一：使用递归

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if len(postorder) == 0:
            return True
        
        def verify(left, right: int) -> bool:
            if left >= right:
                return True
            # 因为数组中最后一个值postorder[right]是根节点，这里从左往右找出第一个比根节点大的值，
            # 他后面的都是根节点的右子节点（包含当前值，不包含最后一个值，因为最后一个是根节点），他前面的都是根节点的左子节点
            mid = left
            root = postorder[right]
            while postorder[mid] < root: mid += 1
            tmp = mid
            # 因为postorder[mid]前面的值都是比根节点root小的，
            # 我们还需要确定postorder[mid]后面的值都要比根节点root大，如果后面有比根节点小的直接返回false
            while tmp < right:
                if postorder[tmp] < root:
                    return False
                tmp += 1
            return verify(left, mid-1) and verify(mid, right-1)

        return verify(0, len(postorder) - 1)

方法二：栈

关于if (cur > parent) return false; 的思考

三个前提

1.两个数如果arr[i]<arr[i+1]，那么arr[i+1]一定是arr[i]的右孩子

2.如果arr[i]>arr[i+1]，那么arr[i+1]一定是arr[0]……arr[i]中某个节点的左孩子，并且这个值是大于arr[i+1]中最小

3.递增栈

当遇到一个值a小于栈顶值时，需要找到该值的父节点b(即栈内最早压栈的且大于该值的值)

找到该值b以后作为parent值, a为b的左孩子

后续再遇到值x，有如下情况：

1.它是栈内某个值的左孩子，那么该值肯定小于等于栈顶值a，(递增栈，栈顶最大)–>x<a<b(parent);

2.它是栈顶值a的右孩子,但是a是b的左孩子，因此它的孩子值也不能大于b --> x<b(parent);

这就是为什么该值X无论如何也不能大于b(parent)的原因。

class Solution:
    """
    二叉搜索树的规律：
        挨着的两个数如果arr[i]<arr[i+1]，那么arr[i+1]一定是arr[i]的右子节点
        如果arr[i]>arr[i+1]，那么arr[i+1]一定是arr[0]……arr[i]中某个节点的左子节点，并且这个值是大于arr[i+1]中最小的。
    
    遍历数组的所有元素，
        如果栈为空，就把当前元素压栈。
        如果栈不为空，并且当前元素大于栈顶元素，说明是升序的，那么就说明当前元素是栈顶元素的右子节点，就把当前元素压栈，如果一直升序，就一直压栈。
        当前元素小于栈顶元素，说明是倒序的，说明当前元素是某个节点的左子节点，我们目的是要找到这个左子节点的父节点，就让栈顶元素出栈，直到栈为空或者栈顶元素小于当前值为止，其中最后一个出栈的就是当前元素的父节点。
    """

    def verifyPostorder(self, postorder: List[int]) -> bool:
        st = []
        fa = inf
        for i, cur in enumerate(postorder[::-1]): # 注意for循环是倒叙遍历的
            # 当如果当前节点小于栈顶元素，说明栈顶元素和当前值构成了倒叙，
            # 说明当前节点是前面某个节点的左子节点，我们要找到他的父节点
            while st and st[-1] > cur:
                fa = st.pop()
            # 只要遇到了某一个左子节点，才会执行上面的代码，才会更新parent的值，否则parent就是一个非常大的值，
            # 也就是说如果一直没有遇到左子节点，那么右子节点可以非常大
            if cur > fa:
                return False
            st.append(cur)
        return True
            

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

难度中等421

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

提示：

• 树中节点总数在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

class Solution:
    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        res = []

        def dfs(node: TreeNode, cur: List[int]) -> None:
            if not node: return
            cur.append(node.val)
            if not node.left and not node.right:
                if sum(cur) == target:
                    res.append(list(cur))   
            if node.left: dfs(node.left, cur)
            if node.right: dfs(node.right, cur)
            cur.pop()

        dfs(root, [])
        return res

剑指 Offer 35. 复杂链表的复制

难度中等722

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

方法一：哈希表

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return None
        m = dict()
        p = head
        while p:
            m[p] = Node(p.val)
            p = p.next
        p = head
        while p:
            m[p].next = m.get(p.next)
            m[p].random = m.get(p.random)
            p = p.next
        return m[head]

方法二：拼接与拆分

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return
        cur = head
        # 1. 复制各节点，并构建拼接链表
        while cur:
            tmp = Node(cur.val)
            tmp.next = cur.next
            cur.next = tmp
            cur = tmp.next
        # 2. 构建各新节点的 random 指向
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        # 3. 拆分两链表
        cur = res = head.next
        pre = head
        while cur.next:
            pre.next = pre.next.next
            cur.next = cur.next.next
            pre = pre.next
            cur = cur.next
        pre.next = None # 单独处理原链表尾节点
        return res      # 返回新链表头节点

🎃剑指 Offer 36. 二叉搜索树与双向链表

难度中等683

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

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

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

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

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

class Solution:
    # 中序遍历二叉排序树 = 遍历有序数组
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root: return root
        self.head = None
        self.pre = None

        def dfs(node: Node) -> None:
            if not node:
                return
            dfs(node.left)
            if self.pre:
                self.pre.right = node
            else: # pre前驱为None，说明是第一次见到最小值节点
                self.head = node
            node.left = self.pre
            self.pre = node
            dfs(node.right)
        
        dfs(root)
        self.head.left = self.pre
        self.pre.right = self.head
        return self.head

🎉剑指 Offer 37. 序列化二叉树

难度困难392

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

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

**提示：**输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例：

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

java

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "";
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        String str = Integer.toString(root.val);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            str += "," + (node.left == null ? "null" : Integer.toString(node.left.val))
                +  "," + (node.right == null ? "null" : Integer.toString(node.right.val));
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        System.out.println(str);
        // input: [1,2,3,null,null,4,5]
        // serialized result: 1,2,3,null,null,4,5,null,null,null,null
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.length() == 0) return null;
        String[] arr = data.split(",");
        if(arr.length == 0) return null;
        TreeNode root = new TreeNode(Integer.valueOf(arr[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int idx = 0;
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            node.left = arr[++idx].equals("null") ? null : new TreeNode(Integer.valueOf(arr[idx]));
            node.right = arr[++idx].equals("null") ? null : new TreeNode(Integer.valueOf(arr[idx]));
            if(node.left != null) q.add(node.left);
            if(node.right != null) q.add(node.right);
        }
        return root;
    }
}

剑指 Offer 38. 字符串的排列

难度中等678

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

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

示例:

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

限制：

1 <= s 的长度 <= 8

class Solution {
    List<String> list;
    StringBuilder sb;
    char[] cs;
    boolean[] vis;
    public String[] permutation(String s) {
        cs = s.toCharArray();
        Arrays.sort(cs);
        list = new ArrayList<>();
        sb = new StringBuilder();
        vis = new boolean[cs.length];
        dfs(0);
        String[] res = new String[list.size()];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public void dfs(int i){
        if(i == cs.length){
            list.add(sb.toString());
            return;
        }
        for(int k = 0; k < cs.length; k++){
            // 如原字符串 abb，其排列不能有两个abb
            if(k > 0 && cs[k] == cs[k-1] && vis[k-1]) continue;
            if(!vis[k]){
                vis[k] = true;
                sb.append(cs[k]);
                dfs(i+1);
                sb.deleteCharAt(sb.length() - 1);
                vis[k] = false;
            }
        }
    }
}

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

难度简单369

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

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

示例 1:

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

限制：

1 <= 数组长度 <= 50000

本题常见的三种解法：

哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N) 。

数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。

摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N) 和 O(1) ，为本题的最佳解法。

方法一：摩尔投票法：

class Solution {
    public int majorityElement(int[] nums) {
        int ans = 0, count = 0;
        for(int i = 0; i < nums.length; i++){
            if(count == 0){
                ans  = nums[i];
                count++;
            }else{
                count += nums[i] == ans ? 1 : -1;
            }
        }
        return ans;
    }
}

剑指 Offer 40. 最小的k个数

难度简单554

输入整数数组 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

四种方法秒杀Topk问题：快排、堆、二叉搜索树、计数排序

https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/solution/3chong-jie-fa-miao-sha-topkkuai-pai-dui-er-cha-sou/

方法一：堆

本题是求前 K 小，因此用一个容量为 K 的大根堆，每次 poll 出最大的数，那堆中保留的就是前 K 小啦（注意不是小根堆！小根堆的话需要把全部的元素都入堆，那是 O(nlogN)😂，就不是O(nlogK)啦～～）

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k == 0) return new int[]{};
        // 求最小的k个数，用最大堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b-a);
        for(int x : arr){
            if(pq.size() < k) pq.add(x);
            else{
                if(pq.peek() > x){
                    pq.poll();
                    pq.add(x);
                }
            }
        }
        int[] res = new int[k];
        for(int i = 0; i < k; i++){
            res[i] = pq.poll();
        }
        return res;
    }
}

方法二：快排

注意找前 K 大/前 K 小问题不需要对整个数组进行 O(nlogn) 的排序！

例如本题，直接通过快排切分排好第 K 小的数（下标为 K-1），那么它左边的数就是比它小的另外 K-1 个数啦～

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k == 0) return new int[]{};
        // 最后一个参数表示我们要找的是下标为k-1的数
        return quickSort(arr, 0, arr.length-1, k-1);
    }

    public int[] quickSort(int[] nums, int low, int high, int k){
        int pivot = Partition(nums, low, high);
        if(pivot == k){
            // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
            return Arrays.copyOf(nums, pivot+1); // [0, pivot]
        }
        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
        return pivot > k ? quickSort(nums, low, pivot-1, k) : quickSort(nums, pivot+1, high, k);
    }

    public int Partition(int[] nums, int low, int high){
        int pivot = nums[low];
        while(low < high){
            while(low < high && nums[high] >= pivot) high--;
            nums[low] = nums[high];
            while(low < high && nums[low] <= pivot) low++;
            nums[high] = nums[low];
        }
        nums[low] = pivot; // 最终位置在low = high; 
        return low;
    }
}

方法三：二叉搜索树

BST 相对于前两种方法没那么常见，但是也很简单，和大根堆的思路差不多～

要提的是，与前两种方法相比，BST 有一个好处是求得的前K大的数字是有序的。

因为有重复的数字，所以用的是 TreeMap 而不是 TreeSet（有的语言的标准库自带 TreeMultiset，也是可以的）。

TreeMap的key 是数字，value 是该数字的个数。

我们遍历数组中的数字，维护一个数字总个数为 K 的 TreeMap：

1.若目前 map 中数字个数小于 K，则将 map 中当前数字对应的个数 +1；

2.否则，判断当前数字与 map 中最大的数字的大小关系：若当前数字大于等于 map 中的最大数字，就直接跳过该数字；若当前数字小于 map 中的最大数字，则将 map 中当前数字对应的个数 +1，并将 map 中最大数字对应的个数减 1。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // TreeMap的key是数字, value是该数字的个数。
        // cnt表示当前map总共存了多少个数字。
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int cnt = 0;
        for (int num: arr) {
            // 1. 遍历数组，若当前map中的数字个数小于k，则map中当前数字对应个数+1
            if (cnt < k) {
                map.put(num, map.getOrDefault(num, 0) + 1);
                cnt++;
                continue;
            } 
            // 2. 否则，取出map中最大的Key（即最大的数字), 判断当前数字与map中最大数字的大小关系：
            //    若当前数字比map中最大的数字还大，就直接忽略；
            //    若当前数字比map中最大的数字小，则将当前数字加入map中，并将map中的最大数字的个数-1。
            Map.Entry<Integer, Integer> entry = map.lastEntry();
            if (entry.getKey() > num) {
                map.put(num, map.getOrDefault(num, 0) + 1);
                if (entry.getValue() == 1) {
                    map.pollLastEntry();
                } else {
                    map.put(entry.getKey(), entry.getValue() - 1);
                }
            }
            
        }

        // 最后返回map中的元素
        int[] res = new int[k];
        int idx = 0;
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            int freq = entry.getValue();
            while (freq-- > 0) {
                res[idx++] = entry.getKey();
            }
        }
        return res;
    }
}

四、计数排序（数据范围有限时直接计数排序就行了）

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 统计每个数字出现的次数
        int[] counter = new int[10001];
        for (int num: arr) {
            counter[num]++;
        }
        // 根据counter数组从头找出k个数作为返回结果
        int[] res = new int[k];
        int idx = 0;
        for (int num = 0; num < counter.length; num++) {
            while (counter[num]-- > 0 && idx < k) {
                res[idx++] = num;
            }
            if (idx == k) {
                break;
            }
        }
        return res;
    }
}

🎉剑指 Offer 41. 数据流中的中位数

难度困难435

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

例如，

[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、findMedian 进行 50000 次调用。

题解：评论区

用大顶堆+小顶堆方法，可以看作大顶堆是普通班，小顶堆是实验班。数量上时刻保持 小顶-大顶<=1（两堆相等或者小顶比大顶多一个）。

新学生先入普通班（大顶堆），此时可能会失去平衡了，于是取大顶堆的第一个（班里最好的学生）加入实验班（小顶堆），判断若数量过多（不是等于或多一个），取第一个（实验班里最差的学生）到普通班（大顶堆）里。 取中位数的时候，若两堆数量相等，则各取堆顶取平均，若小顶比大顶多一，则多的那一个就是中位数。

class MedianFinder {
    // 平衡堆:大顶堆+小顶堆
    PriorityQueue<Integer> left;//大顶(存储左边一半的数据，堆顶为最大值)
    PriorityQueue<Integer> right;//小顶(存储右边一半的数据，堆顶为最小值)
    public MedianFinder() {
        // 数量上时刻保持 小顶-大顶<=1（两堆相等或者小顶比大顶多一个）。
        left=new PriorityQueue<>((n1,n2)->n2-n1);
        right=new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        /**
            添加元素时，先添加左边大顶中，然后左边大顶弹出一个添加到右边小顶中
            如果数量不满足 小顶-大顶<=1， 从右边小顶弹出一个添加到左边大顶中
         */
        left.add(num);
        right.add(left.poll());
        if(right.size() - left.size() >= 2){
            left.add(right.poll());
        }
    }
    
    public double findMedian() {
        if(right.size() > left.size()) return right.peek();
        else return (double)(left.peek() + right.peek())/2;
    }
}

剑指 Offer 42. 连续子数组的最大和

难度简单694

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

要求时间复杂度为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

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # dp思想
        # 如果当前数字接前面数组 s += nums[i]
        # 如果当前数字不接前面数组 s = nums[i]
        # 取较大值
        ans, s = -inf, 0
        for val in nums:
            s = max(s + val, val)
            ans = max(ans, s)
        return ans

拓展：如果真的是从这个题目开始学动态规划，一年后应该给自己提升一点难度。

这个题目其实可以更难一点，例如：让你打印出具有最大连续子数组的和的那个子数组，如果存在多个这样的子数组，把最左边的那个打印出来。

因为我们发现，有很多人只会求出最大连续子数组的和，但是找不出那个子数组，这就很麻烦，只知其一，不知其二。

要想彻底理解这个题目的动态规划，就应该知道整个结果的转移过程，并且分析清楚。

先上代码：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans, s = -inf, 0
        left, right = 0, 0 # 记录最大连续子数组和的那个子数组左右边界
        for i, val in enumerate(nums):
            # 当发现前一个dp值小于等于0的时候，就应该刷新这个idx，
            # 因为将第i个元素拼接上去不会使得这个子数组是最大的，因此我们也没必要再维护这个子数组的起始下标。
            if s + val < val:
                left = right = i
                s = val
            else:
                s = s + val
            # 随后，发现以i元素结尾的dp值比全局res更大，那么就更新left来记录结果的起始和终止下标。
            if ans < s:
                ans = s
                right = i
        print(nums[left : right+1])
        return ans

实际上，就是额外加了一个idx变量，idx是一个动态维护的变量，当发现前一个dp值小于等于0的时候，就应该刷新这个idx，因为将第i个元素拼接上去不会使得这个子数组是最大的，因此我们也没必要再维护这个子数组的起始下标。

反之，我们维持这个idx，不会被i改变，这是因为可以拼接上去，我们要记录下这个子数组的起始。

随后，发现以i元素结尾的dp值比全局res更大，那么就更新全局的mem来记录结果的起始和终止下标。

不难发现，通过维护mem我们就可以知道最大的，但维护res可以记录结果，避免反复计算mem子数组的和。

最后，检验结果是否正确，通过累加mem[0]到mem[1]的结果。

🎉剑指 Offer 43. 1～n 整数中 1 出现的次数【数位DP】

难度困难428

输入一个整数 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

class Solution {
    char[] s;
    int[][] cache;
    public int countDigitOne(int n) {
        s = Integer.toString(n).toCharArray();
        int m = s.length;
        cache = new int[m][m];
        for(int i = 0; i < m; i++) Arrays.fill(cache[i], -1);
        return f(0, 0, true);
    }

    public int f(int i, int cnt1, boolean isLimit){
        if(i == s.length){
            return cnt1;
        }
        if(!isLimit && cache[i][cnt1] != -1) return cache[i][cnt1];
        int res = 0;
        int up = isLimit ? s[i] - '0' : 9;
        for(int d = 0; d <= up; d++){
            res += f(i+1, cnt1 + (d == 1 ? 1 : 0), isLimit && d == up);
        } 
        if(!isLimit) cache[i][cnt1] = res;
        return res;
    }
}

🎃剑指 Offer 44. 数字序列中某一位的数字

难度中等336

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

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

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

限制：

• 0 <= n < 2^31

class Solution {
    public int findNthDigit(int n) {
        int digit = 1; // 记录数位 如10的数位为2
        long start = 1; // 每digit位数的起始数字
        long count = 9; // 在digit数位下 数字的数量为count = 9 * digit * start
        // 1.确定n所在数字的位数digit
        while (n > count) {
            n -= count;
            digit += 1; // 1, 2, 3..
            start *= 10; // 1, 10, 100..
            count = digit * start * 9; // 9, 180, 2700..
        }
        // 2.确定n所在的数字 记为num
        long num = start + (n - 1) / digit;
        // 3.确定所求数位在 num 的哪一数位
        return Long.toString(num).charAt((n - 1) % digit) - '0'; 
    }
}

🎃剑指 Offer 45. 把数组排成最小的数

难度中等633

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

示例 1:

输入: [10,2]
输出: "102"

示例 2:

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

提示:

• 0 < nums.length <= 100

说明:

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

题解：这一题主要是考察排序算法，排序规则是两个字符串str1,str2，如果str1+str2 > str2+str1，说明str1大于str2

class Solution {
    public String minNumber(int[] nums) {
       String[] strs = new String[nums.length];
       for(int i = 0; i < nums.length; i++){
           strs[i] = String.valueOf(nums[i]);
       }
       // x + y > y + x 则 x 大于 y
       // x “小于” y 代表：排序完成后，数组中 x 应在 y 左边；“大于” 则反之。
       Arrays.sort(strs, (x, y) -> (x+y).compareTo(y+x));
       StringBuilder sb = new StringBuilder();
       for(String s : strs){
           sb.append(s);
       }
       return sb.toString();
    }
}

剑指 Offer 46. 把数字翻译成字符串

难度中等568

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

示例 1:

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

提示：

• 0 <= num < 231

题解：

class Solution {
    char[] arr;
    int[] cache;
    /**
    比如字符串 12258
    1 2 分别可以作为一个字符 下一步调用的dfs(2)
    12 可以作为一个字符 下一步调用dfs(2)
    存在重复的计算模式，使用记忆化
    cache[i]表示以 i 为起始字符到 s.length 一共能构造出多少种字符串
    */
    public int translateNum(int num) {
        arr = (num + "").toCharArray();
        cache = new int[arr.length + 1];
        Arrays.fill(cache, -1);
        return dfs(0);
    }

    public int dfs(int i){
        if(i == arr.length){
            return 1;
        } 
        if(cache[i] != -1) return cache[i];
        int cnt = dfs(i+1);
        if(i+1 < arr.length) 
            if((arr[i]-'0' > 0 && arr[i]-'0' <= 1) || 
                (arr[i]-'0' == 2 && arr[i+1]-'0' >= 0 && arr[i+1]-'0' <= 5)){
            cnt += dfs(i+2);
        }
        return cache[i] = cnt;
    }
}