吃透剑指Offer

[cuyu0]

吃透剑指Offer

[剑指 Offer（第 2 版）](https://leetcode.cn/problem-list/xb9nqhhg/)

[剑指 Offer 学习计划](https://leetcode.cn/study-plan/lcof/?progress=bvy7xoe)

个人觉得剑指Offer并不是一个算法入门专辑。虽然它的整体难度不高，但是涉及知识点是很广的，它更像是为了面试而整合的一个算法合辑，包含各个面试可能涉及到的知识点。如果你对基础数据结构和基础算法的基本认识尚且有障碍，上来就写剑指Offer并不是一个好的选择。至少要了解基本数据结构的使用，并且有部分自己的理解，才适合使用这本书复习你所掌握的知识点。

如果非要以此专辑入门，可以按照力扣的剑指offer学习计划进行刷题，同时对于每个知识点还需额外刷题，查缺补漏。

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

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

示例 1：

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

限制：

2 <= n <= 100000

解题思路

简单理解下题意，需要查找重复数字。可知一定可以用哈希来解。

解法一：哈希表

    public int findRepeatNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                return num;
            } else {
                map.put(num, 1);
            }
        }
        return -1;
    }

提交后ac，时间7 ms击败35.99%

内存49.9 MB击败43.62%

观察下代码，发现哈希表的值有些冗余，可直接用set来替代优化。

解法二：Set

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

时间7 ms击败35.99%

内存49.9 MB击败41.93%

效率其实相差不大。

碰见哈希类的问题，我们一般可以用数组来模拟，如用数组的下标与值的映射关系来替代哈希的键值映射关系，可以达到优化程序查找时间的目的。

观察下题干，发现数字的范围在2 <= n <= 100000之间，则可以声明一个大小为100000的数组，代码如下。

解法三：数组模拟

    public int findRepeatNumber(int[] nums) {
        int[] arr = new int[100000];
        for (int num : nums) {
            if (arr[num] != 0) {
                return num;
            } else {
                arr[num] ++;
            }
        }
        return -1;
    }

时间2 ms击败63.5%

内存48.6 MB击败90.70%

发现还是不是最优解。

观察题意，发现数组中的数字的大小范围，要小于数组的长度的值。这意味着我们可以直接在数组上进行原地对应，而不需要声明额外的数组空间。即若当前下标数字，与下标值不等，则交换目标下标处数字至当前下标，直至数字下标对应为止。若出现当前的值，已经对应过的情况，则意味着当前数字为重复数字。

解法四：交换法

    // 交换法
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i < nums.length){
            if (nums[i] != i) {
                int temp = nums[i];
                if (nums[temp] == temp) {
                    return temp;
                }
                nums[i] = nums[temp];
                nums[temp] = temp;
            } else {
                i++;
            }
        }
        return -1;
    }

时间0 ms击败100%

内存49 MB击败63.43%

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

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

解题思路

又是一个查找问题，暴力解的思路就是遍历整个二维数组查找target。代码如下：

解法一：暴力解

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }

时间0 ms击败100%

内存47.1 MB击败89.79%

虽然看上去时间空间复杂度还可以，但是这么写毫无代码美感，再观察题干，发现有一些细节可以用上。利用：每一行都按照从左到右 **非递减** 的顺序排序，每一列都按照从上到下 **非递减** 的顺序排序的性质，以矩阵左下角为顶点，发现矩阵很像一个二叉搜索树。可以利用此性质写出Z字查找的代码。

解法二：Z字查找

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 观察矩阵的性质，发现从左下角开始，向右查找单调递增，向上查找单调递减
        if (matrix.length == 0) {
            return false;
        }
        int left = 0;
        int low = matrix[0].length-1;
        while (left < matrix.length && low >= 0) {
            if (matrix[left][low] > target) {
                low --;
            } else if (matrix[left][low] < target) {
                left ++;
            } else {
                return true;
            }
        }
        return false;
    }

时间0 ms击败100%

内存47 MB击败95.60%

剑指 Offer 05. 替换空格

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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

解题思路

题意就很直白，是需要进行一个替换字符的操作。

熟悉Java的朋友第一时间会想到String的replace或replaceAll库方法，代码如下：

解法一：replace、replaceAll

    public String replaceSpace(String s) {
        return s.replaceAll(" ", "%20");
    }

时间2 ms击败10.90%

内存39.8 MB击败9.29%

    public String replaceSpace(String s) {
        return s.replace(" ", "%20");
    }

时间0 ms击败100%

内存39.2 MB击败81.92%

两者的耗时差距略大，应该是两个库方法的实现导致，可以研究下源码实现。暂时先贴上二者源码对比

    public String replaceAll(String regex, String replacement) {
        return Pattern.compile(regex).matcher(this).replaceAll(replacement);
    }

    public String replace(CharSequence target, CharSequence replacement) {
        return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(
                this).replaceAll(Matcher.quoteReplacement(replacement.toString()));
    }

使用库方法未尝不可，但是也要能掌握不使用库方法的写法，本题使用StringBuilder类进行字符串操作即可，代码如下。

解法二：StringBuilder

    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i<s.length(); i++) {
            if (s.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

时间0 ms击败100%

内存39.6 MB击败33.32%

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

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

解题思路

观察题意，发现题目要求用数组逆序打印链表每个节点的值。看到逆序第一反应就是使用辅助栈来实现。代码如下

解法一：栈

    public int[] reversePrint(ListNode head) {
        Deque<Integer> queue = new LinkedList<>();
        while (head != null) {
            queue.push(head.val);
            head = head.next;
        }
        int[] ans = new int[queue.size()];
        int index = 0;
        while (!queue.isEmpty()) {
            ans[index++] = queue.pop();
        }
        return ans;
    }

时间1 ms击败69.12%

内存42 MB击败59.97%

发现不是最优解，应该是使用栈的原因，那么如何不使用栈来解答本题呢？答案是可以通过将数组从后向前赋值，来达到逆序的目的。需要额外遍历一遍链表来获得数组的初始化长度。代码如下：

解法二：两次遍历

    public int[] reversePrint(ListNode head) {
        ListNode temp = head;
        int len = 0;
        while (temp != null) {
            temp = temp.next;
            len++;
        }
        int[] ans = new int[len];
        while (len > 0) {
            ans[--len] = head.val;
            head = head.next;
        }
        return ans;
    }

时间0 ms击败100%

内存42.3 MB击败24.27%

剑指 Offer 07. 重建二叉树

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

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

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

解题思路

要解这题，首先要会手推重建二叉树。从前序遍历中获得根节点的值后，可从中序遍历中区分出左右子树的范围。所以这题本质上是一个分治问题，即从现有的前序遍历和中序遍历中可以推导出一个新的前序遍历和中序遍历，直到分解成最小问题为止。

例：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

根节点：[3]

他的左子树：preorder = [9], inorder = [9]

他的右子树：preorder = [20,15,7], inorder = [15,20,7]

右子树再次分治

右子树的根：[20]

右子树的左子树：preorder = [15], inorder = [15]

右子树的右子树：preorder = [7], inorder = [7]

解法一：DFS

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }

    public TreeNode dfs(int[] preorder, int p_left, int p_right, int[] inorder, int i_left, int i_right) {
        if (p_left > p_right || i_left > i_right) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[p_left]);
        int index = i_left;
        for (int i = i_left; i <= i_right; i++) {
            if (inorder[i] == preorder[p_left]) {
                index = i;
                break;
            }
        }
        root.left = dfs(preorder, p_left+1, p_left+index-i_left, inorder, i_left, index-1);
        root.right = dfs(preorder, p_left+index-i_left+1, p_right, inorder, index+1, i_right);
        return root;
    }

时间3 ms击败35.8%

内存41.6 MB击败13.65%

观察下代码，发现在中序遍历序列中查找根的位置是一个时间复杂度为O(n)的操作，效率较低，可以使用HashMap将查找根节点位置的效率优化至O(1)，牺牲一点额外内存空间。

解法二：优化DFS

    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return dfs(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }

    public TreeNode dfs(int[] preorder, int p_left, int p_right, int[] inorder, int i_left, int i_right) {
        if (p_left > p_right || i_left > i_right) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[p_left]);
        int index = map.get(preorder[p_left]);
        root.left = dfs(preorder, p_left+1, p_left+index-i_left, inorder, i_left, index-1);
        root.right = dfs(preorder, p_left+index-i_left+1, p_right, inorder, index+1, i_right);
        return root;
    }

时间1 ms击败99.88%

内存41 MB击败70.23%

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

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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 次调用

解题思路

对比下栈和队列的性质，栈先进后出，队列先进先出，使用两个栈，翻转一次栈存入另一个栈即可实现模拟，注意下细节处理，优先pop处理翻转后的栈2，代码如下。

解法一：辅助栈

class CQueue {

    Deque<Integer> stack1;
    Deque<Integer> stack2;
    public CQueue() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if (stack1.isEmpty() && stack2.isEmpty()) {
            return -1;
        } else if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        } else {
            return stack2.pop();
        }
    }
}

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

写一个函数，输入 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

解题思路

根据题意，先写出斐波那契数列递归模板

    public int fib(int n) {
        if (n < 2) {
            return n;
        } else {
            return fib(n-1) + fib(n-2);
        }
    }

由于是暴力递归，重复计算太多，用在本题必定超时

先写出斐波那契数列记忆化递归写法

    Map<Integer, Integer> map = new HashMap<>();
    public int fib(int n) {
        if (map.containsKey(n)) {
            return map.get(n);
        }
        if (n < 2) {
            return n;
        } else {
            int res = fib(n-2) + fib(n-1);
            map.put(n, res);
            return res;
        }
    }

题目要求答案对1000000007取模，解答如下

解法一：记忆化递归

    Map<Integer, Integer> map = new HashMap<>();
    public int fib(int n) {
        if (map.containsKey(n)) {
            return map.get(n);
        }
        if (n < 2) {
            return n;
        } else {
            int res = (fib(n-2) + fib(n-1))%1000000007;
            map.put(n, res);
            return res;
        }
    }

时间0 ms击败100%

内存38.2 MB击败71.88%

记忆化递归可以转换为dp写法，两种写法都要掌握，首先写出斐波那契数列简单dp模板

    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

补充对答案的取模操作即可。

解法二：动态规划

    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2])%1000000007;
        }
        return dp[n];
    }

时间0 ms击败100%

内存38.5 MB击败22.53%

看下代码，其实本题不需要用dp数组来记录，只需保存前两次的计算结果即可，优化如下

解法三：动态规划优化

    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int a = 0;
        int b = 1;
        for (int i = 2; i <= n; i++) {
            int sum = (a + b)%1000000007;
            a = b;
            b = sum;
        }
        return b;
    }

剑指 Offer 10- II. 青蛙跳台阶问题

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

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

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

提示：

• 0 <= n <= 100

解题思路

青蛙跳台阶问题本质上就是一个斐波那契数列。将上题代码稍加修改即可，不多做阐述

解法一：记忆化递归

    Map<Integer, Integer> map = new HashMap<>();
    public int numWays(int n) {
        if (map.containsKey(n)) {
            return map.get(n);
        }
        if (n == 0) {
            return 1;
        } else if (n <= 2) {
            return n;
        } else {
            int res = (numWays(n-2) + numWays(n-1))%1000000007;
            map.put(n, res);
            return res;
        }
    }

时间0 ms击败100%

内存38.3 MB击败49.22%

解法二：动态规划

    public int numWays(int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 2) {
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2])%1000000007;
        }
        return dp[n];
    }

时间0 ms击败100%

内存38.1 MB击败75%

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

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

给你一个可能存在 重复 元素值的数组 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 次旋转

解题思路

阅读本题，可知数组是一个升序排序数组的旋转数组，需要查找数组中最小的元素。

首先本题暴力解的思路就是遍历数组更新最小元素值。这样的话，题目中数组升序的条件就没有用上，而无论是什么数组，暴力查找最小值的时间复杂度都为O(n)，在此不多阐述。

本题的目标数组是一个有序数组的旋转，而此类问题一般都为二分查找问题的变种。利用二分可以达到O(logn)的查找效率。

梳理下本题的解题思路，就是二分法去比较mid元素和right元素的大小，进行分析。

nums[mid] > nums[right]和nums[mid] < nums[right]的两种情况都好进行分析，关键点在于，若nums[mid] == nums[right]时，例如[3,1,3,3,3]和[3,3,3,1,3]的情况，我们无法判断出最小值在哪个区间内，故只能收缩右边界的范围，再次进行二分查找。代码如下：

解法一：二分查找

    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length-1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (numbers[mid] > numbers[right]) {
                left = mid + 1;
            } else if (numbers[mid] < numbers[right]){
                right = mid;
            } else {
                right--;
            }
        }
        return numbers[right];
    }

时间0 ms击败100%

内存41.1 MB击败79.73%

剑指 Offer 12. 矩阵中的路径

给定一个 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仅由大小写英文字母组成

解题思路

根据题意，易得出解法，即从矩阵每个元素出发，进行暴力DFS，直至查找到target为止。

为了方便暴力搜索，我们需要几个变量辅助。

方向数组

        int[][] directions = new int[][]{
            {0, -1},
            {0, 1},
            {-1, 0},
            {1, 0}
        };

访问记录数组

boolean[][] visited = new boolean[board.length][board[0].length];

矩阵坐标

int i, int j

字符串索引

int index

回溯的关键点在于，需要在一次递归搜索后，将当前矩阵访问记录清除。写出代码

解法一：DFS

    boolean res = false;
    public boolean exist(char[][] board, String word) {
        int[][] directions = new int[][]{
            {0, -1},
            {0, 1},
            {-1, 0},
            {1, 0}
        };
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (res) {
                    return res;
                }
                dfs(board, word, 0, i, j, directions, visited);
            }
        }
        return res;
    }

    public void dfs(char[][] board, String word, int index, int i, int j, int[][] directions, boolean[][] visited) {
        if (board[i][j] != word.charAt(index)) {
            return;
        }
        if (index == word.length()-1) {
            res = true;
            return;
        }
        visited[i][j] = true;
        for (int[] direction : directions) {
            int new_i = i + direction[0];
            int new_j = j + direction[1];
            if (new_i >= 0 && new_i < board.length && new_j >=0 && new_j < board[0].length && !visited[new_i][new_j]) {
                dfs(board, word, index+1, new_i, new_j, directions, visited);
            }
        }
        visited[i][j] = false;
    }

时间114 ms击败28.6%

内存39.5 MB击败62.78%

暂时没有好的优化思路，感觉和100%通过的dfs解法时间复杂度其实差不多。

剑指 Offer 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

解题思路

观察题意，题目要求长度为n的绳子，剪成段后各绳长的最大乘积。

解法一：动态规划

关键点：长度为3的绳子最大乘积为1 * 2 = 2，但是长度为6的绳子最大乘积为3 * 3 = 9, 易得：计算当前长度绳长的最大乘积，需要去比较剪成段的长度所获得的最长乘积，和段的长度本身的比较。如6，去计算就不能用count(3)*count(3)，而是用3 * 3。

    public int cuttingRope(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * dp[i-j], j * (i-j)));
            }
        }
        return dp[n];
    }

时间1 ms击败48.82%

内存38.6 MB击败13.12%

解法二：贪心

具体解析见[面试题14- I. 剪绳子（数学推导 / 贪心思想，清晰图解）](https://leetcode.cn/problems/jian-sheng-zi-lcof/solutions/104809/mian-shi-ti-14-i-jian-sheng-zi-tan-xin-si-xiang-by/)

摘抄一部分推导：

切分规则：

最优： 3 。把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0,1,2三种情况。

次优： 2 。若最后一段绳子长度为 2 ；则保留，不再拆为1+1。

最差： 1 。若最后一段绳子长度为 1；则应把一份 3+1 替换为2+2，因为 2×2>3×1。

给出代码：

    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int a = n / 3;
        int b = n % 3;
        if (b == 0) {
            // 3直接乘上3
            return (int)Math.pow(3, a);
        } else if (b == 1) {
            // 4拆成2*2
            return (int)Math.pow(3,a-1) * 4;
        } else {
            // 2直接乘上2
            return (int)Math.pow(3,a) * 2;
        }
    }

时间0 ms击败100%

内存38.3 MB击败57.21%

剑指 Offer 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

解题思路

这题和上一题的区别在于n的取值范围不同，在n较大的情况下，需要考虑结果越界问题，所以需要对在计算过程中，对乘积进行取模。解法和上题一致。但动态规划可能较为麻烦，因为要计算考虑数组每个数的越界情况。这里只提供贪心解。

解法一：循环求余法

关键点：注意对MOD求余时，符号的优先级问题，注意添加括号。

写法一

    final int MOD = 1000000007;
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        long ans = 1;
        while (n > 4) {
            ans = ans * 3 % MOD;
            n -= 3;
        }
        return (int)(ans * n % MOD);
    }

写法二

    final int MOD = 1000000007;
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        long ans = 1;
        int a = n / 3;
        int b = n % 3;
        for (int i = 1; i < a; i++) {
            // 少乘一次，方便计算
            ans = ans * 3 % MOD;
        }
        if (b == 1) {
            return (int)(ans * 4 % MOD);
        } else if (b == 2) {
            return (int)(ans * 6 % MOD);
        } else {
            return (int)(ans * 3 % MOD);
        }
    }

解法二：循环求余法---快速幂优化

由于要求3的幂，一次次乘法计算效率较低，这里可以使用快速幂，提升计算幂的效率。

    final int MOD = 1000000007;
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        long ans = 1;
        // 乘数
        long x = 3;
        int b = n % 3;
        for (int a = n/3-1; a > 0; a/=2) {
            // 少乘一次，方便计算
            // 计算快速幂
            if (a % 2 == 1) {
                ans = (ans * x) % MOD;
            }
            x = (x * x) % MOD;
        }
        if (b == 1) {
            return (int)(ans * 4 % MOD);
        } else if (b == 2) {
            return (int)(ans * 6 % MOD);
        } else {
            return (int)(ans * 3 % MOD);
        }
    }

[cuyu0]

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

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 [汉明重量](http://en.wikipedia.org/wiki/Hamming_weight)).）。

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用 [二进制补码](https://baike.baidu.com/item/%E4%BA%8C%E8%BF%9B%E5%88%B6%E8%A1%A5%E7%A0%81/5295284) 记法来表示有符号整数。因此，在上面的 示例 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 的 二进制串 。

解题思路

熟悉Java Integer库的朋友第一时间应该能想到Integer.bitcount()这个方法，专门用于计算整型的二进制位为1的个数。

解法一：Integer.bitCount()

    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }

如果不用库方法，可以将n的每一位二进制位都与1进行&操作。结果为1时，count++;

解法二：按位&

首先写出第一版代码

    public int hammingWeight(int n) {
        int count = 0;
        while (n > 0) {
            if ((n & 1) == 1) {
                count++;
            }
            n >>= 1;
        }
        return count;
    }

发现，所有的负数用例都通过不了，题目的要求是要计算补码位的1，所以需要使用无符号右移。

简单介绍下无符号右移的概念。

无符号右移运算符（>>>）（零填充右移）将左操作数计算为无符号数，并将该数字的二进制表示形式移位为右操作数指定的位数，取模 32。向右移动的多余位将被丢弃，零位从左移入。其符号位变为 0，因此结果始终为非负数。与其他按位运算符不同，零填充右移返回一个无符号 32 位整数。

Tips:

">>>"无符号右移

操作规则：无论正负数，前面补零。

">>"右移

操作规则：正数前面补零，负数前面补1

"<<"左移

操作规则：无论正负数，后面补零。

修改后代码如下：

    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                count++;
            }
            n >>>= 1;
        }
        return count;
    }

时间0 ms击败100%

内存38.7 MB击败36.62%

解法三：n&(n-1)

解释如下：

• (n−1) 解析： 二进制数字 n 最右边的 1 变成 0 ，此 1 右边的 0 都变成 1 。
• n&(n−1) 解析： 二进制数字 n 最右边的 1 变成 0 ，其余不变

    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n &= (n - 1);
        }
        return count;
    }

时间0 ms击败100%

内存38.6 MB击败57.78%

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

实现 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

解题思路

题意就是要自己实现一个计算幂的方法。当幂小于0时，需要将x转换为1/x来进行计算。由于幂的范围较大，需要采用快速幂的方法来优化计算效率，下面提供快速幂的两种解法。

解法一：递归快速幂

    // 递归写法
    public double myPow(double x, int n) {
       if (n == 0) {
           return 1;
       }
       if (n == 1) {
           return x;
       }
       if (n == -1) {
           return 1/x;
       }
       double half = myPow(x, n/2);
       double rest = myPow(x, n%2);
       return half * half * rest;
    }

时间0 ms击败100%

内存40.8 MB击败

47.3%

解法二：非递归快速幂

    // 非递归写法
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        // 由于n的范围为-2^31 <= n <= 2^31-1
        // 将n取反操作可能越界
        // 需要一个long来保存n
        long nn = n;
        if (nn < 0) {
            nn = -nn;
            x = 1/x;
        }
        double res = 1;
        for (; nn>0; nn/=2) {
            if (nn % 2 == 1) {
                // 更新res
                res *= x;
            }
            x *= x;
        }
        return res;
    }

时间0 ms击败100%

内存40.7 MB击败57%

剑指 Offer 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 为正整数

解题思路

可能是为了让我们熟悉数组的初始化吧...

解法一：暴力

    public int[] printNumbers(int n) {
        int len = (int)Math.pow(10,n) - 1;
        int[] res = new int[len];
        for (int i = 1; i <= len; i++) {
            res[i-1] = i;
        }
        return res;
    }

时间1 ms击败72.59%

内存49 MB击败68.34%

感觉还可以用快速幂优化下计算10^n的效率。代码如下

    public int[] printNumbers(int n) {
        int len = 1;
        int x = 10;
        // 简单替换下快速幂的写法，逻辑一样
        for (; n>0; n>>=1) {
            if ((n & 1) == 1) {
                len *= x;
            }
            x *= x;
        }
        int[] res = new int[len];
        for (int i = 1; i < len; i++) {
            res[i-1] = i;
        }
        return res;
    }

时间1 ms击败72.59%

内存49 MB击败59.22%

效率没有提升，应该是n范围较小的原因。

这题没通过100%应该是力扣计算规则的出入。

剑指 Offer 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 被删除的节点

解题思路

没啥逻辑，就遍历链表查找next.val==target，注意点是需要用前置节点/哑节点来遍历，并且return pre.next。

解法一：暴力

    public ListNode deleteNode(ListNode head, int val) {
        ListNode pre = new ListNode(0, head);
        ListNode ans = pre;
        while (pre.next != null) {
            if (pre.next.val == val) {
                pre.next = pre.next.next;
            } else {
                pre = pre.next;
            }
        }
        return ans.next;
    }

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

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含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' 重复了一次。

示例 3:

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

示例 4:

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

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

解题思路

本题单的第一道困难题，确实也很困难。

参考下官方解答：[正则表达式匹配](https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solutions/521347/zheng-ze-biao-da-shi-pi-pei-by-leetcode-s3jgn/)

首先明确动态数组的含义：dp[i][j]表示s的前i位字符串能否匹配p的前j位字符串

用动态规划去解，难点在于如何匹配*。

字母 + 星号的组合在匹配的过程中，本质上只会有两种情况：

• 匹配 s 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配；

• 不匹配字符，将该组合扔掉，不再进行匹配。

同时，为了方便处理本题，需要抽出一个matches函数来判断当前位是否匹配。

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j-1) == '.') {
            return true;
        }
        return s.charAt(i-1) == p.charAt(j-1);
    }

解法一：动态规划

    public boolean isMatch(String s, String p) {
        // dp[i][j]表示s的前i位字符串能否匹配p的前j位字符串
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        // 可能存在s为空，但是匹配'任意字符'+'*'的情况
        // 所以i从0开始遍历
        // 但是j从1开始遍历
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j-1) == '*') {
                    // p的第j个字符为'*'
                    if (matches(s,p,i,j-1)) {
                        // 查看p的前一位和当前s是否匹配
                        // 匹配的话，查看是匹配多次还是丢掉
                        dp[i][j] = dp[i-1][j] || dp[i][j-2];
                    } else {
                        // 不匹配的话，直接去掉p的这两位
                        dp[i][j] = dp[i][j-2];
                    }
                } else {
                    if (matches(s,p,i,j)){
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j-1) == '.') {
            return true;
        }
        return s.charAt(i-1) == p.charAt(j-1);
    }

时间1 ms击败100%

内存40.4 MB击败32.95%

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

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

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

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），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。

解题思路

整个剑指Offer最恶心的题目。

解法一：抖机灵NumberFormatException

    public boolean isNumber(String s) {
        if (s.contains("f")) {
            return false;
        }
        if (s.contains("F")) {
            return false;
        }
        if (s.contains("d")) {
            return false;
        }
        if (s.contains("D")) {
            return false;
        }
        try {
            Double.parseDouble(s);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }

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

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

示例：

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

提示：

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

解题思路

经典双指针的应用。左右指针分别从两头出发寻找奇偶数，并交换。注意右指针先出发（左指针先出发也能过，不影响）。有点像快速排序的双指针交换部分。

解法一：双指针

    public int[] exchange(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        while (left < right) {
            while (left < right && nums[right] % 2 == 0) {
                right--;
            }
            while (left < right && nums[left] % 2 == 1) {
                left++;
            }
            int temp = nums[right];
            nums[right] = nums[left];
            nums[left] = temp;
        }
        return nums;
    }

时间1 ms击败100%

内存49.4 MB击败38.17%

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

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

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

示例：

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

返回链表 4->5.

解题思路

由于链表不能反向遍历，顺序遍历获得链表的长度后，再次遍历输出倒数第k个节点。

解法一：两次遍历

    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode temp = head;
        int len = 0;
        while (temp!=null) {
            len++;
            temp = temp.next;
        }
        int i = 0;
        while (i < len-k) {
            head = head.next;
            i++;
        }
        return head;
    }

时间0 ms击败100%

内存39.7 MB击败27.2%

两次遍历缺乏编程之美，可以考虑用快慢指针的方法替代两次遍历，无需计算链表长度。

解法二：快慢指针

    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        while (fast!=null) {
            fast = fast.next;
            head = head.next;
        }
        return head;
    }

时间0 ms击败100%

内存39.7 MB击败34.61%

剑指 Offer 24. 反转链表

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

示例:

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

限制：

0 <= 节点个数 <= 5000

解题思路

链表最经典的题目，必会。关键点在于需要前置空节点来辅助翻转过程，画图易得链表翻转后节点指向。

解法一：迭代

    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while (head!=null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

时间0 ms击败100%

内存40.9 MB击败57.65%

解法二：递归

    public ListNode reverseList(ListNode head) {
        return recur(head, null);
    }

    public ListNode recur(ListNode head, ListNode pre) {
        if (head == null) {
            return pre;
        }
        ListNode res = recur(head.next, head);
        head.next = pre;
        return res;
    }

时间0 ms击败100%

内存40.9 MB击败53.93%

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

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

示例1：

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

限制：

0 <= 链表长度 <= 1000

解题思路

双指针分别遍历这两条节点并重建一条新链就好了，要注意合并长链表未合并的部分。

解法一：双指针

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode temp = pre;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                temp.next = l2;
                l2 = l2.next;
            } else {
                temp.next = l1;
                l1 = l1.next;
            }
            temp = temp.next;
        }
        if (l1 != null) {
            temp.next = l1;
        }
        if (l2 != null) {
            temp.next = l2;
        }
        return pre.next;
    }

时间0 ms击败100%

内存41.2 MB击败91.46%

剑指 Offer 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

解题思路

如何判断B为A的子结构呢？

遍历A找到B的根节点。

遍历A和B，如果A.val!=B.val，return false。

如果B==null，return true。

如果A==null，return false。

解法一：DFS

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        boolean res = false;
        if (A.val == B.val) {
            res = isSub(A, B);
        }
        return isSubStructure(A.left, B) || isSubStructure(A.right, B) || res;
    }

    public boolean isSub(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        } else if (A == null){
            return false;
        } else {
            return A.val == B.val && isSub(A.left, B.left) && isSub(A.right, B.right);
        }
    }

时间0 ms击败100%

内存43.4 MB击败88.10%

剑指 Offer 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

解题思路

这题还卡了我一会儿...可能因为关键点在于不能原地修改，需要重建一个新的镜像树

解法一：DFS

    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode ans = new TreeNode(root.val);
        ans.left = mirrorTree(root.right);
        ans.right = mirrorTree(root.left);
        return ans;
    }

时间0 ms击败100%

内存38.9 MB击败62.23%

剑指 Offer 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

解题思路

上题就是求二叉树的镜像，所以这题的笨方法就是重建一个镜像树，然后遍历这树判断是否每个节点都相等。太笨了...就懒得写。

换个思路，其实就是比较左子树的左节点值等于右子树的右节点值和左子树的右节点值等于右子树的左节点值嘛，写个辅助函数来深度优先遍历就好了。

这破题居然也卡了一会儿...

解法一：DFS

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSym(root.left, root.right);
    }

    public boolean isSym(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        } else {
            return left.val == right.val && isSym(left.left, right.right) && isSym(left.right, right.left);
        }
    }

时间0 ms击败100%

内存39.8 MB击败36.43%

剑指 Offer 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

解题思路

简单模拟题。思路是保存下上下左右四个边界，每一轮遍历完成后需缩小对应的边界。

    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        int left = 0;
        int right = matrix[0].length;
        int up = 0;
        int bot = matrix.length;
        int[] ans = new int[right * bot];
        int index = 0;
        while (index < ans.length) {
            // 向右
            for (int i = left; i < right; i++) {
                ans[index] = matrix[up][i];
                index++;
            }
            if (index == ans.length) {
                break;
            }
            // 上边界缩小1
            up++;
            // 向下
            for (int i = up; i < bot; i++) {
                ans[index] = matrix[i][right-1];
                index++;
            }
            if (index == ans.length) {
                break;
            }
            // 右边界缩小1
            right--;
            // 向左
            for (int i = right-1; i >= left; i--) {
                ans[index] = matrix[bot-1][i];
                index++;
            }
            if (index == ans.length) {
                break;
            }
            // 下边界缩小1
            bot--;
            // 向上
            for (int i = bot-1; i >= up; i--) {
                ans[index] = matrix[i][left];
                index++;
            }
            if (index == ans.length) {
                break;
            }
            // 左边界缩小1
            left++;
        }
        return ans;
    }

时间1 ms击败61.83%

内存43.3 MB击败48.70%

剑指 Offer 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.

提示：

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

解题思路

仔细读题，题目要求调用min的时间复杂度都是 O(1)，如果每次调用min方法时重新计算min是达不到O(1)的时间复杂度的，所以一定是需要一个辅助最小栈来保存当前栈中最小值。

解法一：辅助最小栈

class MinStack {

    Deque<Integer> deque1;
    Deque<Integer> deque2;
    /** initialize your data structure here. */
    public MinStack() {
        deque1 = new LinkedList<>();
        deque2 = new LinkedList<>();
    }

    public void push(int x) {
        deque1.push(x);
        if (deque2.isEmpty() || deque2.peek() > x) {
            deque2.push(x);
        } else {
            deque2.push(deque2.peek());
        }
    }

    public void pop() {
        deque1.pop();
        deque2.pop();
    }

    public int top() {
        if (deque1.isEmpty()) {
            return -1;
        }
        return deque1.peek();
    }

    public int min() {
        if (deque2.isEmpty()) {
            return -1;
        }
        return deque2.peek();
    }
}

剑指 Offer 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 之前弹出。

提示：

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

解题思路

这题看似比较复杂，其实只需要用栈来模拟一遍push和pop操作即可。

注意每次push完元素后，都尝试去pop。代码如下：

解法一：栈模拟

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<>();
        int index = 0;
        for (int i = 0; i < pushed.length; i++) {
            if (stack.isEmpty() || stack.peek() != popped[index]) {
                stack.push(pushed[i]);
            }
            while (!stack.isEmpty() && stack.peek() == popped[index]) {
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }

时间1 ms击败97.3%

内存41.3 MB击败41.72%

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

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

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

    3
   / \
  9  20
    /  \
   15   7
返回：

[3,9,20,15,7]

提示：

节点总数 <= 1000

解题思路

简单层序遍历，提供迭代解法和递归解法。

解法一：BFS---迭代解法

    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> stack = new LinkedList<>();
        stack.offer(root);
        while (!stack.isEmpty()) {
            int size = stack.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = stack.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    stack.offer(cur.left);
                }
                if (cur.right != null) {
                    stack.offer(cur.right);
                }
            }
        }
        int[] ans = new int[list.size()];
        int index = 0;
        for (int val : list) {
            ans[index] = val;
            index++;
        }
        return ans;
    }

时间1 ms击败96.96%

内存41.2 MB击败77.37%

若使用递归解法，需要记录层数，根据层数往对应层数的list中进行插入操作。相对较麻烦一点。

解法二：DFS---递归解法

    List<List<Integer>> list = new ArrayList<>();
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        dfs(root, 0);
        int len = 0;
        for (int i = 0; i < list.size(); i++) {
            len += list.get(i).size();
        }
        int[] ans = new int[len];
        int index = 0;
        for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < list.get(i).size(); j++) {
                ans[index++] = list.get(i).get(j);
            }
        }
        return ans;
    }  

    public void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        if (depth > list.size()-1) {
            list.add(new ArrayList<>());
        }
        list.get(depth).add(root.val);
        dfs(root.left, depth+1);
        dfs(root.right, depth+1);
    }

时间1 ms击败96.96%

内存41.5 MB击败43.15%

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

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

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

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

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

提示：

节点总数 <= 1000

解题思路

这题的思路和上题一致，并且由于少了初始化int[]数组的麻烦，写起来要更简洁些。提供BFS和DFS解。

解法一：BFS---迭代解法

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> stack = new LinkedList<>();
        stack.offer(root);
        while (!stack.isEmpty()) {
            int size = stack.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = stack.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    stack.offer(cur.left);
                }
                if (cur.right != null) {
                    stack.offer(cur.right);
                }
            }
            ans.add(list);
        }
        return ans;
    }

时间1 ms击败71.82%

内存41.5 MB击败66.32%

解法二：DFS---递归解法

    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return list;
        }
        dfs(root, 0);
        return list;
    }

    public void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        if (depth > list.size()-1) {
            list.add(new ArrayList<>());
        }
        list.get(depth).add(root.val);
        dfs(root.left, depth+1);
        dfs(root.right, depth+1);
    }

时间0 ms击败100%

内存41.7 MB击败27.37%

[cuyu0]

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

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

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

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

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

提示：

节点总数 <= 1000

解题思路

打印节点值的时候，注意下根据层数，区分下打印顺序即可。

解法一：BFS---迭代解法

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> stack = new LinkedList<>();
        stack.offer(root);
        while (!stack.isEmpty()) {
            int size = stack.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = stack.poll();
                if (ans.size() % 2 == 1) {
                    list.add(0, cur.val);
                } else {
                    list.add(cur.val);
                }
                if (cur.left != null) {
                    stack.offer(cur.left);
                }
                if (cur.right != null) {
                    stack.offer(cur.right);
                }
            }
            ans.add(list);
        }
        return ans;
    }

时间1 ms击败96.38%

内存41.6 MB击败54.2%

解法二：DFS---递归解法

    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return list;
        }
        dfs(root, 0);
        return list;
    }

    public void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        if (depth > list.size()-1) {
            list.add(new ArrayList<>());
        }
        if (depth % 2 == 1) {
            list.get(depth).add(0, root.val);
        } else {
            list.get(depth).add(root.val);
        }
        dfs(root.left, depth+1);
        dfs(root.right, depth+1);
    }

时间0 ms击败100%

内存41.5 MB击败57.45%

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

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

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

     5
    / \
   2   6
  / \
 1   3
示例 1：

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

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

提示：

数组长度 <= 1000

解题思路

这道题关键点在于，这是一个二叉搜索树。

二叉搜索树的性质是左节点小于根节点，右节点大于根节点。并且二叉树内的每个节点都满足该性质。

所以要根据二叉搜索树的性质，进行分治递归，递归解法有点类似于剑指 Offer 07. 重建二叉树的解法。

关键点在于，既要区分出左子树，也要验证右子树的正确性。其实验证判断的关键点就在于检查右子树内是否有小于根节点的节点。

解法一：分治---DFS

    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length-1);
    }

    public boolean recur(int[] postorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        // 根据根的大小来区分左右子树
        int mid = left;
        while (postorder[mid] < postorder[right]) {
            mid++;
        }
        int r = mid;
        while (postorder[r] > postorder[right]) {
            r++;
        }
        return r == right && recur(postorder, left, mid-1) && recur(postorder, mid, right-1);
    }

时间0 ms击败100%

内存39.1 MB击败39.80%

二叉树所有的题，基本上都可以用递归和迭代两种方式来解答，这道题也不例外。不是很好理解，提供代码。

解法二：单调栈---BFS

    public boolean verifyPostorder(int[] postorder) {
        Deque<Integer> stack = new LinkedList<>();
        int parent = Integer.MAX_VALUE;
        for (int i = postorder.length-1; i >= 0; i--) {
            int cur = postorder[i];
            // 当如果前节点小于栈顶元素，说明栈顶元素和当前值构成了倒序
            // 说明当前节点是前面某个节点的左子节点，我们要找到他的父节点
            // 只有当前节点是parent的左节点，才会进行更新
            while (!stack.isEmpty() && stack.peek() > cur) {
                parent = stack.pop();
            }
            // 若出现左节点大于parent，则return false
            if (cur > parent) {
                return false;
            }
            stack.push(cur);
        }
        return true;
    }

时间1 ms击败22.85%

内存38.9 MB击败72.25%

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

给你二叉树的根节点 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

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

解题思路

这题解法就是暴力回溯。关键点在于需要特判一下叶子节点，因为要求路径是根到叶子的路径。

关键点：

        if (target == 0 && root.left == null && root.right == null) {
            ans.add(new ArrayList<>(list));
        }

这段代码不可提前return，因为后续还需要回溯操作。

解法一：回溯

    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null){
            return ans;
        }
        dfs(root, target, new ArrayList<>());
        return ans;
    }

    public void dfs(TreeNode root, int target, List<Integer> list) {
        if (root == null) {
            return;
        }
        target -= root.val;
        list.add(root.val);
        if (target == 0 && root.left == null && root.right == null) {
            ans.add(new ArrayList<>(list));
        }
        dfs(root.left, target, list);
        dfs(root.right, target, list);
        list.remove(list.size()-1);
    }

时间1 ms击败99.97%

内存42 MB击败28.20%

剑指 Offer 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 。

解题思路

题目要求对链表进行深拷贝。但是本题的node有两个指向。所以需要两次遍历来重建节点的两个指向。

那么问题来了，如何在第二次遍历链表时，知道新链的random的新指向呢？

这就需要在第一次next遍历构建新链时，保存下原链和新链的对应关系，这样在第二次遍历时，我们就知道原链的next和random对应的新链节点，就可以串联起来了。

解法一：哈希表---两次遍历

    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node temp = head;
        while (temp != null) {
            Node cur = new Node(temp.val);
            map.put(temp, cur);
            temp = temp.next;
        }
        temp = head;
        while (temp != null) {
            Node cur = map.get(temp);
            cur.next = map.get(temp.next);
            cur.random = map.get(temp.random);
            temp = temp.next;
        }
        return map.get(head);
    }

时间0 ms击败100%

内存41 MB击败67.79%

解法二：哈希表---DFS

    Map<Node, Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = new Node(head.val);
        map.put(head, cur);
        cur.next = copyRandomList(head.next);
        cur.random = map.get(head.random);
        return map.get(head);
    }

时间0 ms击败100%

内存40.9 MB击败84.51%

解法三：拼接链表 + 拆分---迭代

由于哈希表还需要声明额外的内存空间来保存对应关系，实际上可以省去这部分内存来进行原地更改

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node temp = head;
        // 一次遍历，复制链表
        while (temp != null) {
            Node newNode = new Node(temp.val);
            newNode.next = temp.next;
            temp.next = newNode;
            temp = newNode.next;
        }
        temp = head;
        // 当前节点的next（复制节点）的random等于当前节点的random的next
        // 二次遍历，构建random引用
        while (temp != null) {
            if (temp.random != null) {
                temp.next.random = temp.random.next;
            }
            temp = temp.next.next;
        }
        // 拆分出复制的链表
        temp = head.next;
        // 拆原链
        Node pre = head;
        Node res = head.next;
        while(temp.next != null) {
            pre.next = pre.next.next;
            temp.next = temp.next.next;
            pre = pre.next;
            temp = temp.next;
        }
        pre.next = null; // 单独处理原链表尾节点
        return res;      // 返回新链表头节点
    }

时间0 ms击败100%

内存41.2 MB击败37.26%

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

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

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

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

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

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

解题思路

梳理下题意先：

题目要求将二叉搜索树转换为双向链表，指的是left节点做链表pre节点，right节点做链表next节点。

二叉搜索树的中序遍历即为有序序列。故在中序遍历的基础上更改节点的指向即可。

摘抄一部分题解：[字节题库 - #剑36 - 中等 - 二叉搜索树与双向链表 - 1刷](https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solutions/446583/zi-jie-ti-ku-jian-36-zhong-deng-er-cha-sou-suo-shu/)

这题乍一看感觉好难，又是树又是链表的，还是双向循环排序链表。其实真滴不难，且看分析。

首先观察到题目给的是一棵 BST，这就意味着我们只需要用中序遍历就能实现排序的链表了。

最终得到的链表的头节点必然是 BST 最左边的节点（题目示例中就是 1）；尾节点必然是 BST 最右边的节点（题目示例中就是 5）。

我们先定义 tail 和 head，初始它们都是 nullptr，到最后则会一个指向尾节点一个指向头节点。

所以我们中序遍历，首先 root 一直往左走，走到了最左边的 1 处，此时 tail 还是 nullptr，并且整个遍历过程中只有这个时候 tail 会是 nullptr。这个时候我们让 head = root，也就找到了链表的头节点。

然后我们更新 tail = root（也就是 1），root 会回溯到上一级也就是 2。这时我们就写 tail -> right = root; 和 root -> left = tail;。

我们此时接着更新 tail = root（也就是 2）。如此往复。

中序遍历走完之后，链表也就构造完了，除了 head 和 tail 之间的连接，我们再连接一下就好了（代码对应处有注释）。

解法一：中序遍历---DFS

    // 声明头节点和尾节点
    Node head = null;
    Node tail = null;
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        dfs(root);
        // 循环链接
        head.left = tail;
        tail.right = head;
        return head;
    }

    public void dfs(Node root) {
        if (root == null) {
            return;
        }
        // 中序遍历先遍历左节点
        dfs(root.left);
        if (tail == null) {
            // 到达最左节点，只有这时tail才为空
            head = root;
        } else {
            tail.right = root; // 前一个尾节点的下一个节点是当前节点
            root.left = tail; // 双向链接，当前节点上一个节点是前一个尾节点
        }
        tail = root;
        dfs(root.right);
    }

时间0 ms击败100%

内存40.8 MB击败72.55%

剑指 Offer 37. 序列化二叉树

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

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

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 [LeetCode 序列化二叉树的格式](https://support.leetcode-cn.com/hc/kb/article/1567641/)。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例：

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

解题思路

这题虽然是道困难，但是却是简单题的难度，不要被标签所吓唬到。

经常在力扣调试测试用例的朋友应该知道，力扣在用例中对树的可视化序列表达，就是一个包含空值的列表。

这题要求打印成字符串，所以这题serialize函数就是将树包含空值进行层序遍历打印。deserialize函数就是将包含空值的字符串重构成树。

解法一：模拟

    // Encodes a tree to a single string.
    // 就是个层序遍历输出 + null值存储
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i<size; i++) {
                TreeNode cur = queue.poll();
                if (cur == null) {
                    sb.append("null").append(",");
                } else {
                    sb.append(cur.val).append(",");
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] elements = data.split(",");
        if (elements[0].equals("null")) {
            return null;
        }
        int index = 0;
        TreeNode root = new TreeNode(Integer.parseInt(elements[index]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        index++;
        while (index < elements.length) {
            int size = queue.size();
            for (int i = 0; i<size; i++) {
                TreeNode cur = queue.poll();
                if (elements[index].equals("null")) {
                    cur.left = null;
                } else {
                    cur.left = new TreeNode(Integer.parseInt(elements[index]));
                    queue.offer(cur.left);
                }
                index++;
                if (elements[index].equals("null")) {
                    cur.right = null;
                } else {
                    cur.right = new TreeNode(Integer.parseInt(elements[index]));
                    queue.offer(cur.right);
                }
                index++;
            }
        }
        return root;
    }

时间13 ms击败75.94%

内存42.9 MB击败81.61%

[cuyu0]

剑指 Offer 38. 字符串的排列

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

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

示例:

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

限制：

1 <= s 的长度 <= 8

解题思路

回溯经典题，必会。

    List<String> ans = new ArrayList<>();
    public String[] permutation(String s) {
        char[] c = s.toCharArray();
        dfs(c, new StringBuilder());
        String[] res = new String[ans.size()];
        int i = 0;
        for (String str: ans) {
            res[i] = str;
            i++;
        }
        return res;
    }

    public void dfs(char[] c, StringBuilder sb) {
        if (sb.length() == c.length) {
            if (!ans.contains(sb.toString())) {
                ans.add(sb.toString());
            }
            return;
        }
        for (char value : c) {
            if ("".equals(sb.toString()) || sb.indexOf(String.valueOf(value)) == -1) {
                sb.append(value);
                dfs(c, sb);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }

写的第一版代码，没有考虑到s本身就包含重复元素的情况，解答错误。使用辅助visited数组，来记录是否使用对应index处元素。用list来保存排列后的字符串也会导致超时，这里使用set来去重可以免于判断。

解法一：Set去重+visited数组---回溯

    Set<String> ans = new HashSet<>();
    public String[] permutation(String s) {
        char[] c = s.toCharArray();
        dfs(c, new StringBuilder(), new boolean[s.length()]);
        return ans.toArray(new String[0]);
    }

    public void dfs(char[] c, StringBuilder sb, boolean[] visited) {
        if (sb.length() == c.length) {
            ans.add(sb.toString());
            return;
        }
        for (int i = 0; i < c.length; i++) {
            if (visited[i]) {
                continue;
            }
            sb.append(c[i]);
            visited[i] = true;
            dfs(c, sb, visited);
            sb.deleteCharAt(sb.length() - 1);
            visited[i] = false;
        }
    }

时间28 ms击败32.62%

内存46.6 MB击败42.39%

效率不高，可想办法剪枝。若s本身就包含重复元素的情况，该重复元素只做一次计算即可。这样就不用使用set来去重了。

解法二：排序+剪枝优化---回溯

    List<String> ans = new ArrayList<>();
    public String[] permutation(String s) {
        char[] c = s.toCharArray();
        Arrays.sort(c);
        dfs(c, new StringBuilder(), new boolean[s.length()]);
        return ans.toArray(new String[0]);
    }

    public void dfs(char[] c, StringBuilder sb, boolean[] visited) {
        if (sb.length() == c.length) {
            ans.add(sb.toString());
            return;
        }
        for (int i = 0; i < c.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (i > 0 && c[i] == c[i - 1] && !visited[i - 1]) {
                continue;
            }
            sb.append(c[i]);
            visited[i] = true;
            dfs(c, sb, visited);
            sb.deleteCharAt(sb.length() - 1);
            visited[i] = false;
        }
    }

时间6 ms击败95.94%

内存46.1 MB击败73.34%

还有其他优化方案，可以参考以下题解：

[剑指 Offer 38. 字符串的排列（回溯法，清晰图解）](https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/solutions/178988/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/?orderBy=hot)

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

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

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

示例 1:

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

限制：

1 <= 数组长度 <= 50000

解题思路

如果这题要求时间复杂度为O(1)，那么就不是简单题的难度。

解法一：排序

    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }   

时间2 ms击败57.41%

内存44.7 MB击败80.50%

若众数出现的次数大于数组长度的一半，可以使用摩尔投票法来计算众数。

博耶-摩尔多数投票算法（英语：Boyer–Moore majority vote algorithm）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法由罗伯特·S·博耶（英语：Robert S. Boyer）和J·斯特罗瑟·摩尔（英语：J Strother Moore）在1981年发表，也是处理数据流（英语：streaming algorithm）的一种典型算法。

x轴为计数器中存储的元素，而下方y轴为输入的元素序列。遇到相同元素或者计数器中没有元素，计数器加入重复元素，如果遇到不同元素计数器消除一个元素。

这一算法应用的问题原型是在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上；在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素，那么第一次的结果就可能是无效的随机元素。对于数据流而言，则不太可能在亚线性空间复杂度的情况下中就寻找到出现频率最高的元素；而对于序列，其元素的重复次数也有可能很低。

解法二：摩尔投票法

Tips:

不同候选人的选票之间，可以一一抵消。

若当前胜利者存在多张选票时，不同的候选人的票，只能抵消一张当前胜利者的票。

若当前双方的选票被抵消为零，下一次抽出的候选人，将作为暂时的胜利者领先。

摩尔投票法 我愿称之为 同归于尽法

    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }

时间1 ms击败99.97%

内存44.7 MB击败82.39%

解法三：分治法

分治部分和归并排序的分治部分一样。每次分治都返回当前分组的众数，再比较左右两个分组中挑选出的众数即可。

    public int majorityElement(int[] nums) {
        return getMajorityElement(nums, 0, nums.length-1);
    }

    public int getMajorityElement(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = (left + right) >>> 1;
        int leftNum = getMajorityElement(nums, left, mid);
        int rightNum = getMajorityElement(nums, mid+1, right);
        if (leftNum == rightNum) {
            return leftNum;
        }
        int leftCount = 0;
        int rightCount = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] == leftNum) {
                leftCount++;
            }
        }
        for (int i = left; i <= right; i++) {
            if (nums[i] == rightNum) {
                rightCount++;
            }
        }
        return leftCount > rightCount ? leftNum : rightNum;
    }

时间1 ms击败99.97% 时间复杂度：O(nlog⁡n)

内存45 MB击败53.62%

剑指 Offer 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

解题思路

解法一：优先队列

    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o));
        for (int num : arr) {
            priorityQueue.offer(num);
        }
        int[] ans = new int[k];
        for (int i = 0; i<k; i++){
            ans[i] = priorityQueue.poll();
        }
        return ans;
    }

时间18 ms击败16.33%

内存43.1 MB击败7.14%

效率过低。。。

解法二：排序+输出(没啥写的必要)

    public int[] getLeastNumbers(int[] arr, int k) {
        int[] ans = new int[k];
        Arrays.sort(arr);
        for (int i = 0; i < k; ++i) {
            ans[i] = arr[i];
        }
        return ans;
    }

时间7 ms击败71.16%

内存42.6 MB击败33.78%

解法三：基于快速排序的数组划分

参考题解：[剑指 Offer 40. 最小的 k 个数（基于快速排序的数组划分，清晰图解）](https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/solutions/594591/jian-zhi-offer-40-zui-xiao-de-k-ge-shu-j-9yze/)

摘抄一部分解题思路：

题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。因此，只需要将数组划分为 最小的 kkk 个数 和 其他数字 两部分即可，而快速排序的哨兵划分可完成此目标。

根据快速排序原理，如果某次哨兵划分后 基准数正好是第 k+1k+1k+1 小的数字 ，那么此时基准数左边的所有数字便是题目所求的 最小的 k 个数 。

根据此思路，考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于 kkk ，若 truetruetrue 则直接返回此时数组的前 kkk 个数字即可。

    public int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length) {
            return arr;
        }
        return quickSort(arr, k, 0, arr.length-1);
    }

    public int[] quickSort(int[] arr, int k, int left, int right) {
        // 当pivot下标为k时，返回pivot前面数组即可
        int l = left;
        int r = right;
        int pivot = arr[left];
        while (l < r) {
            while (l < r && arr[r] >= pivot) {
                r--;
            }
            while (l < r && arr[l] <= pivot) {
                l++;
            }
            swap(arr, l, r);
        }
        swap(arr, l, left);
        if (l > k) {
            return quickSort(arr, k, left, l-1);
        }
        if (l < k) {
            return quickSort(arr, k, l+1, right);
        }
        return Arrays.copyOf(arr, k);
    }

    // 临时变量法
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

时间2 ms击败93.8%

内存43.2 MB击败5.7%

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

解题思路

这题可以利用大顶堆、小顶堆的性质。大顶堆保存较小的半边，小顶堆保存较大的半边。

解法一：优先队列

class MedianFinder {

    Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }
    public void addNum(int num) {
        if(A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }

}

时间77 ms击败18.99%

内存52.5 MB击败46.14%

剑指 Offer 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

解题思路

简单dp背包问题。首先明确dp数组的含义，dp[i]表示nums[i:]的最大连续子数组和。

明确递推公式：dp[i] = Math.max(dp[i-1]+nums[i], nums[i])

写出代码

解法一：动态规划

    public int maxSubArray(int[] nums) {
        // dp[i]表示nums[i:]的最大连续子数组和
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }

时间1 ms击败42.82%

内存48.2 MB击败42.34%

由于这题不需要保留最大连续子数组和的历史记录，可以省略掉dp数组的内存。代码优化如下

    public int maxSubArray(int[] nums) {
        // dp[i]表示nums[i:]的最大连续子数组和
        int cur = 0;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            cur = Math.max(cur + num, num);
            max = Math.max(max, cur);
        }
        return max;
    }

时间0 ms击败100%

内存48.5 MB击败7.49%

[cuyu0]

剑指 Offer 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

解题思路

考虑dp[i]表示i中1出现的次数。写出递推公式：dp[i] = dp[i/10] + dp[i%10]。代码如下：

    public int countDigitOne(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        int sum = 1;
        for (int i = 2; i <= n; i++) {
            if (i < 10) {
                dp[i] = 0;
            } else {
                dp[i] = dp[i/10] + dp[i%10];
            }
            sum += dp[i];
        }
        return sum;
    }

超出内存限制，35/39，824883294这个测试用例未通过。

解法一：数位拆分

参照题解：[思路+多语言代码10分钟讲清楚！](https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solutions/691431/python3si-lu-dai-ma-10fen-zhong-jiang-qi-9btr/)

以3101592举例说明。

1-3101592中，出现1的次数为：从个位到百万位，每位中出现1的次数之和。

所以这道题就转换为了一道，计算每位数字中，1的出现次数。

以百位为例。将3101592划分成四部分：

cur表示百位数字：5；

base表示当前基数：100；

a表示百位之前的数字：3101

b表示百位之后的数字：92

给出规律，具体推导见上述题解。

cur > 1 [3101 ] 5 [92]

变化范围：[0-3101] 1 [0-99] 总个数： (a+1) * base

cur == 1 [310] 1 [592]

分为两种情况:

1. 变化范围 [0-309] 1 [0-999] a * base
2. 变化范围 [310] 1 [0-592] 1 (b+1) 总个数：a base + (b + 1)

cur < 1 [31] 0 [1592]

变化范围 [0-30] 1 [0-9999] 总个数 a * base

代码如下：

    public int countDigitOne(int n) {
        long base = 1;
        int res = 0;
        while (base <= n) {
            // 计算a
            long a = n / base / 10;
            // 计算cur
            long cur = (n / base) % 10;
            // 计算b
            long b = n % base;
            if (cur > 1) {
                res += (a + 1) * base;
            } else if (cur == 1) {
                res += a * base + b + 1;
            } else {
                res += a * base;
            }
            base *= 10;
        }
        return res;
    }

时间0 ms击败100%

内存38.6 MB击败18.26%

这题难点主要在于分析的过程，是一道很经典的数位拆分题，需要熟练掌握。

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

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

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

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

限制：

• 0 <= n < 2^31

解题思路

其实和上题类似，也是一道数位拆分的题目。

此类题还是需要多加推导，总结规律。除此之外只能通过多刷题来提升自己的通过率。如果是初次碰见，实在是不好推导。

参考题解：[字节题库 - #剑44 - 中等 - 数字序列中某一位的数字 - 1刷](https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solutions/473940/zi-jie-ti-ku-jian-44-zhong-deng-shu-zi-xu-lie-zhon/?orderBy=hot)

关键点在于这题要拆分出几个变量（摘自上述题解）：

1. digit。表示数位，比如个位，digit = 1；十位，digit = 2；百位，digit = 3；以此类推。
2. start。表示该数位的所有数的起始点数。比如个位，start = 1（0 做特例处理，不算在内）；十位，start = 10；千位，start = 1000；以此类推。
3. index_count。表示该数位一共有的索引个数。比如个位，index_count = 9（1-9）；十位，index_count = 180（10-99）；百位，index_count = 2700（100-999）；以此类推。我们可以总结出这么一条规律：index_count = digit 9 start。比如十位，index_count = 2 9 10 = 180。

解法一：数位拆分

    public int findNthDigit(int n) {
        if (n == 0) {
            return 0;
        }
        // 数位
        int digit = 1;
        // 该数位起始索引
        long start = 1;
        // 该数位总数
        long index_count = digit * 9 * start;
        while(n > index_count ) {
            // 找到n属于的数位
            n -= index_count;
            digit++;
            start *= 10;
            index_count = digit * 9 * start;
        }
        // 上述循环完成后，找到n属于的数位及该数位总数
        // 剩余的n表示在该数位总数上的索引
        long num = start + (n - 1) / digit;
        int remainder = (n - 1) % digit;
        // 转换成字符串好找到对应位置数字
        return Long.toString(num).charAt(remainder) - '0';
    }

时间0 ms击败100%

内存38.2 MB击败70.58%

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

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

示例 1:

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

提示：

• 0 <= num < 2^31

解题思路

这题其实是一道有条件的跳台阶问题变种。即：

若 num <= 25 && num >= 0, 则一次可以跳两格台阶。

其他情况，一次只能跳一格台阶。

解法一：动态规划

    // 跳台阶变种
    // 有条件的跳台阶问题
    public int translateNum(int num) {
        String str = String.valueOf(num);
        int len = str.length();
        int[] dp = new int[len+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= len; i++) {
            int value = Integer.parseInt(str.substring(i-2, i));
            if (value < 26 && value >= 10) {
                dp[i] = dp[i-1] + dp[i-2];
            } else {
                dp[i] = dp[i-1];
            }
        }
        return dp[len];
    }

时间0 ms击败100%

内存38.1 MB击败86.35%

compareTo写法

    // 跳台阶变种
    // 有条件的跳台阶问题
    public int translateNum(int num) {
        String str = String.valueOf(num);
        int len = str.length();
        int[] dp = new int[len+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= len; i++) {
            String s = str.substring(i - 2, i);
            if (s.compareTo("10") >= 0 && s.compareTo("25") <= 0) {
                dp[i] = dp[i-1] + dp[i-2];
            } else {
                dp[i] = dp[i-1];
            }
        }
        return dp[len];
    }
}

时间0 ms击败100%

内存38.1 MB击败85.1%

剑指 Offer 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

解题思路

简单dp问题，每次取左上最大值即可。

解法一：动态规划

    public int maxValue(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];
                } else if (i == 0) {
                    dp[i][j] = grid[i][j] + dp[i][j-1];
                } else if (j == 0) {
                    dp[i][j] = grid[i][j] + dp[i-1][j];
                } else {
                    dp[i][j] = grid[i][j] + Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }

时间3 ms击败18.48%

内存43.9 MB击败77.74%

效率有点低啊。。。怎么肥四。。。

改成原地更改

代码如下：

    public int maxValue(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i == 0 && j == 0) {
                    continue;
                } else if (i == 0) {
                    grid[i][j] += grid[i][j-1];
                } else if (j == 0) {
                    grid[i][j] += grid[i-1][j];
                } else {
                    grid[i][j] += Math.max(grid[i][j-1], grid[i-1][j]);
                }
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }

时间2 ms击败97.93%

内存43.7 MB击败97.71%

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• s.length <= 40000

解题思路

经典滑窗，必会。

关键点在于：

满足条件时（无重复字符子串），right++;

不满足条件时（重复字符子串），left++;

解法一：双指针---滑动窗口

    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0;
        int right = 0;
        int max = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            if (!set.contains(c)) {
                set.add(c);
                max = Math.max(set.size(), max);
                right++;
            } else {
                set.remove(s.charAt(left));
                left++;
            }
        }
        return max;
    }

时间5 ms击败53.97%

内存41.3 MB击败81.83%

效率较低，想办法优化效率。实际上不需要HashSet来保存字符，只需要在right右移时，不断查找left-right区间内，是否存在为nums[right]的元素，若有，则更新left的值。持续计算max。代码如下：

    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        int max = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            for (int i = left; i < right; i++) {
                if (s.charAt(i) == c) {
                    left = i + 1;
                    break;
                }
            }
            max = Math.max(right-left+1, max);
            right++;
        }
        return max;
    }

时间1 ms击败100%

内存41.1 MB击败98.15%

剑指 Offer 49. 丑数★

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

示例:

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

说明:

1. 1 是丑数。
2. n 不超过1690。

解题思路

关键点：一个丑数，一定由另一个丑数乘上2，3，5中的一个获得。

解法一：优先队列+去重

    public int nthUglyNumber(int n) {
        int[] factors = new int[]{2,3,5};
        // 小顶堆
        PriorityQueue<Long> queue = new PriorityQueue<>();
        queue.offer(1L);
        long ugly = 0;
        for (int i = 0; i < n; i++) {
            ugly = queue.poll();
            for (int factor : factors) {
                long next = ugly * factor;
                if (!queue.contains(next)) {
                    queue.offer(next);
                }
            }
        }
        return (int)ugly;
    }

时间255 ms击败5.4%

内存41.2 MB击败16.13%

这个解法过于厚重，勉强能过。

优化思路：三指针维护dp数组

解法二：三指针 + 动态规划

    public int nthUglyNumber(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        // 三指针
        int p2 = 1;
        int p3 = 1;
        int p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int num5 = dp[p5] * 5;
            dp[i] = Math.min(num2, Math.min(num3, num5));
            if (num2 == dp[i]) {
                p2++;
            }
            if (num3 == dp[i]) {
                p3++;
            }
            if (num5 == dp[i]) {
                p5++;
            }
        }
        return dp[n];
    }

时间2 ms击败98.38%

内存39.3 MB击败88.58%

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

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

示例 1:

输入：s = "abaccdeff"
输出：'b'

示例 2:

输入：s = "" 
输出：' '

限制：

0 <= s 的长度 <= 50000

解题思路

这题和剑指 Offer 03. 数组中重复的数字很相似，但是这题是求第一个只出现一次的字符。简单模拟下。

解法一：模拟

    public char firstUniqChar(String s) {
        int[] chars = new int[26];
        for (int i = 0; i<s.length(); i++) {
            chars[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (chars[c - 'a'] == 1) {
                return c;
            }
        }
        return ' ';
    }

时间5 ms击败85.34%

内存42.1 MB击败37.92%

剑指 Offer 51. 数组中的逆序对★

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

解题思路

归并排序变种。查找数组中逆序对总数的过程可以分治成：两两数组元素之间比较大小的子问题。这其实就是归并排序过程中包含的子问题。

解法一：归并排序+计数

    int count = 0; // 归并模板上添加语句
    public int reversePairs(int[] nums) {
        mergeSort(nums, 0, nums.length-1);
        return count;
    }

    public void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) >>> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);
        sort(nums, left, mid, right);
    }

    public void sort(int[] nums, int left, int mid, int right) {
        int p1 = left;
        int p2 = mid + 1;
        int[] temp = new int[right-left+1];
        int index = 0;
        while (p1 <= mid && p2 <= right) {
            if (nums[p1] > nums[p2]) {
                // 因为已排序，所以从p1开始到mid全部都为逆序对
                count += (mid - p1 + 1); // 归并模板上添加语句
                temp[index] = nums[p2];
                p2++;
            } else {
                temp[index] = nums[p1];
                p1++;
            }
            index++;
        }
        while (p1 <= mid) {
            temp[index] = nums[p1];
            p1++;
            index++;
        }
        while (p2 <= right) {
            temp[index] = nums[p2];
            p2++;
            index++;
        }
        index = 0;
        for (int i = left; i <= right; i++) {
            nums[i] = temp[index];
            index++;
        }
    }

时间31 ms击败66.28%

内存48.6 MB击败96.89%

剑指 Offer 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) 内存。

解题思路

这题的暴力解思路就是存储链表的节点，遍历两个链表时若出现重复节点，则将其返回。此写法过于简单不多做阐述。

提供下双指针解法的思路：

p1、p2分别指向两条链的起点，遍历两个链表。

若p1为null，将p1指向head2继续遍历；

若p2为null，将p2指向head1继续遍历；

若两者相等，将该节点返回。

解法一：双指针

    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != p2) {
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }
        return p1;
    }

时间1 ms击败98.31%

内存44.7 MB击败10.79%

剑指 Offer 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 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

解题思路

经典二分查找变种。

关键点：二分查找target的插入位置。分别查找target及target+1的插入位置。二者相减并返回。

解法一：二分查找

    public int search(int[] nums, int target) {
        return binarySearch(nums, target + 1) - binarySearch(nums, target);
    }

    public int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

时间0 ms击败100%

内存44.5 MB击败41.70%

剑指 Offer 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

解题思路

这题题意表达不清楚，需要补充下，要求返回nums的长度。

暴力解的思路就是找到下标和元素值不匹配的数字。给出代码

解法一：暴力解

    public int missingNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return nums.length;
    }

时间0 ms击败100%

内存42.1 MB击败71.14%

虽然通过100%。。。但是其实这题可以用二分查找来优化下查找效率

解法二：二分查找

    public int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums.length;
    }

时间0 ms击败100%

内存42.5 MB击败18.20%

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

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

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4
示例 2:

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

限制：

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

解题思路

这题的关键点在于：是去查找二叉搜索树的第K大节点。

中序遍历即可获得二叉搜索树节点值的增序序列。

解法一：中序遍历

    List<Integer> list = new ArrayList<>();
    public int kthLargest(TreeNode root, int k) {
        dfs(root);
        return list.get(list.size() - k);
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }

时间1 ms击败32.34%

内存41.9 MB击败14.51%

效率略低，考虑dfs直接查找。右根左序列即二叉搜索树的单调递减序列。

解法二：右-根-左-遍历

    int count = 0;
    int index;
    public int kthLargest(TreeNode root, int k) {
        index = k;
        dfs(root);
        return count;
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.right);
        if (index == 1) {
            count = root.val;
        }
        index--;
        dfs(root.left);
    }

时间0 ms击败100%

内存41.1 MB击败77.32%

剑指 Offer 55 - I. 二叉树的深度

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

例如：

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

提示：

节点总数 <= 10000

解题思路

给出递归两种写法和迭代一种写法

解法一：dfs---自顶而下

    int maxDepth = 0;
    public int maxDepth(TreeNode root) {
        dfs(root, 0);
        return maxDepth;
    }

    public void dfs(TreeNode root, int depth) {
        if (root == null) {
            maxDepth = Math.max(depth, maxDepth);
            return;
        }
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }

时间0 ms击败100%

内存41.3 MB击败37.54%

解法二：dfs---自底而上

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }

时间0 ms击败100%

内存41.2 MB击败53.84%

解法三：bfs

    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
        return depth;
    }

时间1 ms击败19.17%

内存40.9 MB击败90.45%

剑指 Offer 55 - II. 平衡二叉树

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

示例 1:

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

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

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

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

限制：

0 <= 树的结点个数 <= 10000

解题思路

这题可以利用上题dfs的写法。遍历每个节点计算左右子树的高度差。

解法一：dfs---自底而上

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    public int getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getDepth(root.left), getDepth(root.right))+1;
    }

时间1 ms击败52.86%

内存41.3 MB击败25.23%

效率不是很高，还可以再次优化下。

    boolean flag = true;
    public boolean isBalanced(TreeNode root) {
        getDepth(root);
        return flag;
    }

    public int getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        if (Math.abs(left - right) > 1) {
            flag = false;
        }
        return Math.max(left, right)+1;
    }

时间0 ms击败100%

内存41.3 MB击败24.52%

时间复杂度由O(n^2)优化至O(n)

[cuyu0]

剑指 Offer 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

解题思路

出现两次的元素两两抵消，返回剩下元素即可。

解法一：set去重

    public int[] singleNumbers(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                set.remove(num);
            } else {
                set.add(num);
            }
        }
        return set.stream().mapToInt(Integer::intValue).toArray();
    }

时间12 ms击败6.80%

内存43.3 MB击败20.54%

效率过低，考虑利用异或的性质来求解。

首先已知 x xor x = 0, 即相同数字异或的结果为0；

故对nums遍历，每个数字异或一遍，最后结果是两个只出现一次的数字的异或值。

找到这个值，第一个为1的数位。

用得到得这个数位的值，去遍历&上每个数组元素，结果分成两组。

&结果为0的部分，得出一个异或值。

&结果为1的部分，得出另一个异或值。

即题目要求的两个数字。

解法二：xor 和 & 分组

    public int[] singleNumbers(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        // 找到任意一个为1的数位
        int div = 1;
        while ((div & res) == 0) {
            div <<= 1;
        }
        int a = 0;
        int b = 0;
        for (int num : nums) {
            if ((num & div) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }

时间1 ms击败100%

内存42.7 MB击败92.91%

剑指 Offer 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

解题思路

解法一：暴力解

    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap();
        for(int i = 0; i < nums.length; i++){
            int key = nums[i];
            if(!map.containsKey(key)){
                map.put(key, 1);
            }else{
                map.put(key, map.get(key) + 1);
            }
        }
        for(Map.Entry<Integer, Integer> entry: map.entrySet()){
            if(entry.getValue() == 1){
                return entry.getKey();
            }
        }
        return -1;
    }

时间14 ms击败24.71%

内存42.6 MB击败61.61%

一个容易理解的思路：把数组中所有数字的二进制表示的每一位加起来，如果某一位的和可以被 3 整除，那么那个只出现一次的数字二进制表示中对应的那一位是 0，否则是 1。

参考题解：[Java实现剑指思路 位运算+逐位统计,思路+代码详细解析](https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solutions/292995/javashi-xian-jian-zhi-si-lu-wei-yun-suan-zhu-wei-t/)

解法二：位运算---诸位统计

关键点：诸位统计计算时，记得要先右移位补0的部分。

    public int singleNumber(int[] nums) {
        // int最长32位字符
        int[] bitCount = new int[32];
        for (int num : nums) {
            int n = num;
            int i = 0;
            while (n > 0) {
                bitCount[31-i] += (n & 1);
                // n无符号右移1
                n >>>= 1;
                i++;
            }
        }
        int res = 0;
        for (int count : bitCount) {
            res <<= 1;
            res += count % 3;
        }
        return res;
    }

时间5 ms击败57.37%

内存42.7 MB击败47.9%

这题百分百解法是逻辑电路模拟推导。个人觉得没必要掌握。

剑指 Offer 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

解题思路

这题暴力解的思路是：固定一边，查找另一边值，使得两个数之和为target。时间复杂度过高，考虑下优化。

本题的查找数组为递增排序，可以考虑用双指针滑动窗口。

解法一：滑动窗口---双指针

    public int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            if (nums[left] + nums[right] == target) {
                return new int[]{nums[left], nums[right]};
            } else if (nums[left] + nums[right] > target) {
                right--;
            } else {
                left++;
            }
        }
        return new int[]{};
    }

时间2 ms击败46.52%

内存60.3 MB击败33.19%

剑指 Offer 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

解题思路

经典滑窗思路，给出代码

解法一：滑动窗口---双指针

    public int[][] findContinuousSequence(int target) {
        List<int[]> ans = new ArrayList<>();
        int left = 1;
        int right = 1;
        int sum = 0;
        List<Integer> list = new ArrayList<>();
        while (left <= target/2) {
            if (sum < target) {
                sum += right;
                list.add(right);
                right++;
            } else if (sum == target) {
                ans.add(list.stream().mapToInt(Integer::intValue).toArray());
                sum += right;
                list.add(right);
                right++;
            } else {
                sum-= left;
                list.remove(0);
                left++;
            }
        }
        return ans.toArray(new int[0][]);
    }

时间11 ms击败8.41%

内存42.1 MB击败5.4%

效率有点低，优化下。

    public int[][] findContinuousSequence(int target) {
        List<int[]> ans = new ArrayList<>();
        int left = 1;
        int right = 1;
        int sum = 0;
        while (left <= target/2) {
            if (sum < target) {
                sum += right;
                right++;
            } else if (sum == target) {
                int[] cur = new int[right-left];
                for (int i = left; i < right; i++) {
                    cur[i-left] = i;
                }
                ans.add(cur);
                sum += right;
                right++;
            } else {
                sum-= left;
                left++;
            }
        }
        return ans.toArray(new int[0][]);
    }

时间2 ms击败94.30%

内存39.7 MB击败34.42%

剑指 Offer 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"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

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

解题思路

熟悉Java api的朋友直接根据空字符split字符串并反向输出即可。

解法一：split() + trim()

    public String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            if (!"".equals(words[i])) {
                sb.append(words[i]).append(" ");
            }
        }
        return sb.toString().trim();
    }

时间1 ms击败100%

内存41.3 MB击败70.32%

不使用api也写下，也是滑窗写法。

解法二：滑动窗口

    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        int left = s.length() - 1;
        while (left >= 0) {
            if (s.charAt(left) == ' ') {
                left--;
            } else {
                int right = left;
                while (right >= 0 && s.charAt(right) != ' ') {
                    right--;
                }
                sb.append(s, right+1, left+1).append(" ");
                left = right;
            }
        }
        return sb.toString().trim();
    }

时间2 ms击败76.25%

内存41.7 MB击败26.43%

剑指 Offer 58 - II. 左旋转字符串

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

示例 1：

输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

限制：

• 1 <= k < s.length <= 10000

解题思路

调Java api只需一行代码

解法一：substring()

    public String reverseLeftWords(String s, int n) {
        return s.substring(n) + s.substring(0, n);
    }

时间0 ms击败100%

内存41.5 MB击败40.37%

不使用api也写一下。

解法二：遍历拼接

    public String reverseLeftWords(String s, int n) {
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        for (int i = n; i < chars.length; i++) {
            sb.append(chars[i]);
        }
        for (int i = 0; i < n; i++) {
            sb.append(chars[i]);
        }
        return sb.toString();
    }

时间2 ms击败50.75%

内存41.7 MB击败11.95%

剑指 Offer 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 ≤ nums.length。

解题思路

维护一个优先队列即可。

写出第一版代码

    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < k; i++) {
            queue.offer(nums[i]);
        }
        int[] ans = new int[nums.length-k+1];
        ans[0] = queue.peek();
        for (int i = k; i < nums.length; i++) {
            queue.remove(nums[i-k]);
            queue.offer(nums[i]);
            ans[i-k+1] = queue.peek();
        }
        return ans;
    }

发现超时，尝试修改下。

改为使用单调队列实现，思想和[剑指Offer 30. 包含 min 函数的栈](https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/)比较相似。

关键点：维护一个单调递减队列。

解法一：单调队列

单调队列经典题，必会。

    // 维护一个单调递减双端队列
    // 关键点，单调队列存储数组下标，方便计算滑窗
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                // 若待插元素大于队列末端，删除最末元素
                deque.removeLast();
            }
            deque.offer(i);
        }
        int[] ans = new int[nums.length-k+1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.removeLast();
            }
            // 开滑
            deque.offer(i);
            if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.removeFirst();
            }
            ans[i-k+1] = nums[deque.peekFirst()];
        }
        return ans;
    }

时间30 ms击败43.12%

内存56.6 MB击败89.25%

剑指 Offer 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]

解题思路

参考题解：[字节题库 - #剑60 - 中等 - n个骰子的点数 - 1刷](https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/solutions/542243/zi-jie-ti-ku-jian-60-zhong-deng-nge-tou-lni20/)

s的所有可能的值出现的概率 = s的所有可能的值出现的次数/所有可能出现的排列组合

摘抄来源上述题解

解题前须知

投掷 n 个骰子，一共会有 6 的 n 次方 种结果，且每种结果都是等可能事件。

投掷 n 个骰子，那么就会有 n 个面朝上，这 n 个朝上的面的点数之和 s 的最大值是 6n，最小值是 n。故投掷 n 个骰子，s 一共有 6n - n + 1 个可能的值（所以题目所要我们返回的浮点数组的大小就是 n * 6 - n + 1。

s 的每一个可能值的概率等于：这个值出现的次数（可表示为 #s，即 the number of s） / 6 的 n 次方。之所以可以这么计算，是因为所有事件都是等可能事件。所以最终需要返回的浮点数组的内容就会是这个样子：[#n / pow(6.0, n), #(n + 1) / pow(6.0, n), #(n + 2) / pow(6.0, n), ..., #6n / pow(6.0, n)]。

解题思路 我们先建立二维 dp 数组，dp[n][s] 表示投掷 n 个骰子，n 个朝上的面的点数之和为 s 的事件出现的次数。

那么动态转移方程就是：dp[n][s] += dp[n - 1][s - k]，k 属于 [1, 6]。

当然，上面的动态转移方程的前提条件是要保证 s - k > 0，因为没有骰子能投掷出小于等于 0 的点数。

解法一：动态规划

    public double[] dicesProbability(int n) {
        int[][] dp = new int[n + 1][n * 6 - n + 1];
        for (int i = 1; i <= 6; i++) {
            // 初始化 dp 数组
            dp[1][i] = 1;
        }
        for(int i = 2; i <= n; i++){
            for(int j = i; j <= 6*n; j++){
                for(int k = 1; k <= 6; k++){
                    if (j-k > 0){
                        dp[i][j] += dp[i-1][j-k];
                    } else {
                        break;
                    }
                }
            }
        }
        double sum = Math.pow(6.0,n);
        double[] ans = new double[n * 6 - n + 1];
        for(int i = n; i <= 6*n; i++){
            ans[i-n] = dp[n][i]/sum;
        }
        return ans;
    }

时间0 ms击败100%

内存41.7 MB击败88.85%

剑指 Offer 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

解题思路

回溯模拟下这套逻辑。写出代码

解法一：回溯模拟

    List<Integer> list = new ArrayList<>();
    int ans = 0;
    public int lastRemaining(int n, int m) {
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        dfs(m, 0);
        return ans;
    }

    public void dfs(int m, int start) {
        if (list.size() == 1) {
            ans = list.get(0);
            return;
        }
        int index = (start + m - 1) % list.size();
        list.remove(index);
        dfs(m, index);
    }

时间1096 ms击败5.19%

内存51.7 MB击败5.11%

效率过低。。。

解法二：约瑟夫环

参考题解：[Java解决约瑟夫环问题，告诉你为什么模拟会超时！](https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solutions/177639/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/)

这么著名的约瑟夫环问题，是有数学解法的！ 因为数据是放在数组里，所以我在数组后面加上了数组的复制，以体现是环状的。我们先忽略图片里的箭头： 【第一轮后面的数字应该是[0, 1, 2 ,3 ,4]，手误打错了。。抱歉】

很明显我们每次删除的是第 mmm 个数字，我都标红了。

第一轮是 [0, 1, 2, 3, 4] ，所以是 [0, 1, 2, 3, 4] 这个数组的多个复制。这一轮 2 删除了。

第二轮开始时，从 3 开始，所以是 [3, 4, 0, 1] 这个数组的多个复制。这一轮 0 删除了。

第三轮开始时，从 1 开始，所以是 [1, 3, 4] 这个数组的多个复制。这一轮 4 删除了。

第四轮开始时，还是从 1 开始，所以是 [1, 3] 这个数组的多个复制。这一轮 1 删除了。

最后剩下的数字是 3。

图中的绿色的线指的是新的一轮的开头是怎么指定的，每次都是固定地向前移位 mmm 个位置。

然后我们从最后剩下的 3 倒着看，我们可以反向推出这个数字在之前每个轮次的位置。

最后剩下的 3 的下标是 0。

第四轮反推，补上 m 个位置，然后模上当时的数组大小 2，位置是(0 + 3) % 2 = 1。

第三轮反推，补上 m 个位置，然后模上当时的数组大小 3，位置是(1 + 3) % 3 = 1。

第二轮反推，补上 m 个位置，然后模上当时的数组大小 4，位置是(1 + 3) % 4 = 0。

第一轮反推，补上 m 个位置，然后模上当时的数组大小 5，位置是(0 + 3) % 5 = 3。

所以最终剩下的数字的下标就是3。因为数组是从0开始的，所以最终的答案就是3。

总结一下反推的过程，就是 (当前index + m) % 上一轮剩余数字的个数。

代码就很简单了。

关键点在于：从最后数字的位置进行反向推导。

    public int lastRemaining(int n, int m) {
        // 最后一个数字的位置
        int pos = 0;
        for (int i = 2; i <= n; i++) {
            pos = (pos + m) % i;
        }
        return pos;
    }

时间4 ms击败98.94%

内存38.2 MB击败79.65%

剑指 Offer 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

解题思路

仔细读题，本题要求在此区间内，股票仅可交易一次。

首先给出暴力解。

解法一：暴力---for for

    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length; i++) {
            for (int j = 0; j < i; j++) {
                max = Math.max(max, prices[i] - prices[j]);
            }
        }
        return max;
    }

时间321 ms击败5.7%

内存41.2 MB击败82.46%

解法二：更新最低买入价格

    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int max = 0;
        int minPrice = prices[0];
        for (int i = 1; i < prices.length; i++) {
            max = Math.max(max, prices[i] - minPrice);
            minPrice = Math.min(minPrice, prices[i]);
        }
        return max;
    }

时间1 ms击败52.44%

内存41.2 MB击败74.83%

剑指 Offer 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

解题思路

什么都不让用。。。只让用+、-、位运算。神奇脑筋急转弯题目。

参考题解：[面试题64. 求 1 + 2 + … + n（逻辑符短路，清晰图解）](https://leetcode.cn/problems/qiu-12n-lcof/solutions/208315/mian-shi-ti-64-qiu-1-2-nluo-ji-fu-duan-lu-qing-xi-/)

解法一：递归模拟---用&&中断递归

    public int sumNums(int n) {
        boolean flag = n > 0 && (n += sumNums(n-1)) > 0;
        return n;
    }

时间0 ms击败100%

内存38.6 MB击败11.75%

很多人会好奇为什么要 && (n += sumNums(n-1)) > 0，实际上这么写也是对的

    public int sumNums(int n) {
        boolean flag = n > 0 && (n += sumNums(n-1)) < Integer.MIN_VALUE;
        return n;
    }

只是利用了一下n > 0 &&的中断性质，&&后面只要跟递归即可，语句的对错并不影响结果。

关键点在于：

• 通过递归替代循环。
• 通过短路运算符来替代条件判断。

剑指 Offer 65. 不用加减乘除做加法

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

示例:

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

提示：

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

解题思路

第一反应：位运算，第二反应：我不会位运算...

来学习一下。

a^b 是无进制相加。

a&b是进位信息。

解法一：位运算

    public int add(int a, int b) {
        int sum = a;
        while (b != 0) {
            sum = a ^ b;
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }

时间0 ms击败100%

内存38.7 MB击败5.37%

解法二：递归

    public int add(int a, int b) {
        if (b == 0) {
            return a;
        }
        return add(a^b, (a & b) << 1);
    }

时间0 ms击败100%

内存38.3 MB击败55.19%

举个例子理解一下

a = 5 (101), b = 9 (1001)

第一遍循环

sum = 5 sum = a ^ b = 5 ^ 9 = 0101 ^ 1001 = 1100 = 12 b = a ^ b = (5 & 9) << 1 = (0101 & 1001) << 1 = (0001) << 1 = 10 = 2 a = sum = 12

第二遍循环

sum = a ^ b = 12 ^ 2 =14 b = a ^ b = (12 & 2) << 1 = (1100 & 0010) << 1 = 0

结束循环，返回sum = 14

剑指 Offer 66. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 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

解题思路

经典前缀和思想应用，必会。

分别维护两个dp数组即可，分别保存i左侧的乘积和及i右侧的乘积和。

解法一：前缀和

    public int[] constructArr(int[] a) {
        if (a.length == 0) {
            return a;
        }
        int[] dp_left = new int[a.length];
        dp_left[0] = 1;
        for (int i = 1; i < a.length; i++) {
            dp_left[i] = dp_left[i-1] * a[i-1];
        }
        int[] dp_right = new int[a.length];
        dp_right[a.length-1] = 1;
        for (int i = a.length-2; i >= 0; i--) {
            dp_right[i] = dp_right[i + 1] * a[i + 1];
        }
        for (int i = 0; i < a.length; i++) {
            a[i] = dp_left[i] * dp_right[i];
        }
        return a;
    }

时间1 ms击败100%

内存51.5 MB击败84.28%

[cuyu0]

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

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

[百度百科](https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin)中最近公共祖先的定义为：“对于有根树 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 为不同节点且均存在于给定的二叉搜索树中。

解题思路

仔细读题，发现是查找二叉搜索树的最近公共祖先，那么问题就简单了，只需要根据p、q两节点的值去找即可。

解法一：DFS

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val < q.val || root.val < p.val && root.val > q.val || root.val == p.val || root.val == q.val) {
            return root;
        } else if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return null;
        }
    }

时间5 ms击败100%

内存42.3 MB击败85.63%

或者写成这样

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }

解法二：BFS

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else if (root.val < p.val && root.val < q.val) {
                root = root.right;
            } else {
                return root;
            }
        }
        return root;
    }

时间5 ms击败100%

内存42.3 MB击败85.18%

剑指 Offer 68 - II. 二叉树的最近公共祖先★

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

[百度百科](https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin)中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: 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 为不同节点且均存在于给定的二叉树中。

解题思路

和上题不一样，这道题的二叉树是普通二叉树，意味着节点的值之间不存在任何规律。所以直接暴力去查找就好了。

关键点：根据左右子树的查找结果，判断祖先在哪部分子树上。

解法一：DFS

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root.left == p && root.right == q || root.right == p && root.left == q ) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return root;
        }
    }

时间6 ms击败100%

内存41.9 MB击败30.31%

面试题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

解题思路

这种题的难点只在于理解题意。。。

m、n表示矩阵范围，k表示对于移动范围的限制。

倒是可以暴力法先梳理一下，判断矩阵每个坐标是否在k的限制之内。给出代码

    public int movingCount(int m, int n, int k) {
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isValid(i, j, k)) {
                    count++;
                }
            }
        }
        return count;
    }

    public boolean isValid(int i, int j, int k) {
        int sum = 0;
        while (i > 0) {
            sum += i % 10;
            i = (i - i % 10)/10;
        }
        while (j > 0) {
            sum += j % 10;
            j = (j - j % 10)/10;
        }
        return sum <= k;
    }

发现未通过。原因是理解错了题意，需要机器人能够访问的节点是从坐标[0,0]开始，连续的坐标。

于是这题就变成了一道图的深度优先遍历。

稍微修改下代码

解法一：DFS

    int count = 0;
    public int movingCount(int m, int n, int k) {
        int[][] directions = new int[][]{
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
        };
        boolean[][] visited = new boolean[m][n];
        dfs(0,0, m, n, k,visited,directions);
        return count;
    }

    public void dfs(int i, int j, int m, int n, int k, boolean[][] visited, int[][] directions) {
        if (i < 0 || i >= m || j < 0 || j >=n || visited[i][j]) {
            return;
        }
        if (isValid(i, j, k)) {
            count++;
            visited[i][j] = true;
            for (int[] direction : directions) {
                dfs(i + direction[0], j + direction[1], m, n, k, visited, directions);
            }
        }
    }

    public boolean isValid(int i, int j, int k) {
        int sum = 0;
        while (i > 0) {
            sum += i % 10;
            i = (i - i % 10)/10;
        }
        while (j > 0) {
            sum += j % 10;
            j = (j - j % 10)/10;
        }
        return sum <= k;
    }

时间1 ms击败63.61%

内存38.1 MB击败95.11%

由于这题限制了k的范围，所以k不会出现三位的情况。isvalid函数可以不用，稍微精简修改下代码。

    int count = 0;
    public int movingCount(int m, int n, int k) {
        int[][] directions = new int[][]{
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
        };
        boolean[][] visited = new boolean[m][n];
        dfs(0,0, m, n, k,visited,directions);
        return count;
    }

    public void dfs(int i, int j, int m, int n, int k, boolean[][] visited, int[][] directions) {
        if (i < 0 || i >= m || j < 0 || j >=n || visited[i][j]) {
            return;
        }
        if ((i % 10 + i / 10 + j % 10 + j / 10) <= k) {
            count++;
            visited[i][j] = true;
            for (int[] direction : directions) {
                dfs(i + direction[0], j + direction[1], m, n, k, visited, directions);
            }
        }
    }

面试题45. 把数组排成最小的数★

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

示例 1:

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

示例 2:

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

提示:

• 0 < nums.length <= 100

说明:

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

解题思路

第一反应是可以自定义排序规则，将首位最小的数字放在前面。

关键点，要写对排序规则。。。想了半天没想出来怎么写。利用Java String的compareTo

Collections.sort(list, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));

解法一：内置api + 自定义排序

    public String minNumber(int[] nums) {
        List<String> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num+"");
        }
        Collections.sort(list, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
        StringBuilder sb = new StringBuilder();
        for (String num : list) {
            sb.append(num);
        }
        return sb.toString();
    }

时间5 ms击败44.26%

内存41.4 MB击败29.29%

所以这题本质上是一个自定义排序规则的题目。所有的排序算法+自定义规则，都可以实现本题。以冒泡排序为例。

解法二：冒泡排序 + 自定义排序

    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]);
        }
        bubbleSort(strs);
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str);
        }
        return sb.toString();
    }

    public void bubbleSort(String[] strs) {
        for (int i = 0; i<strs.length-1; i++) {
            for (int j = i + 1; j<strs.length; j++) {
                if ((strs[i]+strs[j]).compareTo(strs[j]+strs[i]) > 0) {
                    String temp = strs[i];
                    strs[i] = strs[j];
                    strs[j] = temp;
                }
            }
        }
    }

时间12 ms击败11.48%

内存41.7 MB击败9%

效率较低，但是也能通过。再复习一下快速排序。

解法三：快速排序 + 自定义排序

    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]);
        }
        quickSort(strs, 0, strs.length-1);
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str);
        }
        return sb.toString();
    }

    public void quickSort(String[] strs, int i, int j) {
        if (i > j) {
            return;
        }
        String pivot = strs[i];
        int left = i;
        int right = j;
        while (left < right) {
            while (left < right && (strs[right] + pivot).compareTo(pivot + strs[right]) >= 0) {
                right--;
            }
            while (left < right && (strs[left] + pivot).compareTo(pivot + strs[left]) <= 0) {
                left++;
            }
            swap(strs, left, right);
        }
        swap(strs, i, left);
        quickSort(strs, i, left-1);
        quickSort(strs, left+1, j);
    }

    public void swap(String[] nums, int i, int j) {
        String temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

时间4 ms击败96.18%

内存41.2 MB击败56.38%

面试题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

解题思路

队列push()和poll()的时间复杂度本身就是O(1)，只需要设计max()函数如何达到O(1)的复杂度。

可以用单调队列实现。这题其实很像剑指 Offer 59 - I. 滑动窗口的最大值的解法。

解法一：单调队列

    Queue<Integer> queue;
    Deque<Integer> maxQueue;
    public MaxQueue() {
        queue = new LinkedList<>();
        maxQueue = new LinkedList<>();
    }

    public int max_value() {
        return maxQueue.isEmpty() ? -1 : maxQueue.peek();
    }

    public void push_back(int value) {
        queue.offer(value);
        // 单调递减队列更新
        while (!maxQueue.isEmpty() && maxQueue.peekLast() < value) {
            maxQueue.removeLast();
        }
        maxQueue.offer(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }
        if (!maxQueue.isEmpty() && maxQueue.peek().equals(queue.peek())) {
            maxQueue.poll();
        }
        return queue.poll();
    }

时间32 ms击败8.36%

内存49.4 MB击败36.60%

效率怎么这么低。。。检查下

!maxQueue.isEmpty() &&这句可以不用。删掉

class MaxQueue {

    Queue<Integer> queue;
    Deque<Integer> maxQueue;
    public MaxQueue() {
        queue = new LinkedList<>();
        maxQueue = new LinkedList<>();
    }

    public int max_value() {
        return maxQueue.isEmpty() ? -1 : maxQueue.peek();
    }

    public void push_back(int value) {
        queue.offer(value);
        // 单调递减队列更新
        while (!maxQueue.isEmpty() && maxQueue.peekLast() < value) {
            maxQueue.removeLast();
        }
        maxQueue.offer(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }
        if (maxQueue.peek().equals(queue.peek())) {
            maxQueue.poll();
        }
        return queue.poll();
    }
}

时间26 ms击败68.63%

内存49.6 MB击败12.33%

[cuyu0]

面试题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] .

解题思路

先理解下题意。数组的范围为 [0, 13] ，0可取任意数字。

首先明确题目，抛开“扑克”这两个字，和扑克一点关系都没有。

题意：判断给出的5个数是否可以连续，其中0可以当作任意数。

排序+遍历计算0的数量，并根据0的数量，判断是否能成顺子。

解法一：排序+遍历计数

关键点，从当前往后比较，而不是从当前往前比较

    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        int diff = 0;
        for (int i = 0; i < nums.length-1; i++) {
            if (nums[i] == 0) {
                count++;
            } else {
                if (nums[i] == nums[i+1]) {
                    return false;
                }
                if (nums[i]+1 != nums[i+1]) {
                    diff += (nums[i+1] - nums[i] - 1);
                }
            }
        }
        return count >= diff;
    }

时间1 ms击败25.35%

内存38.7 MB击败95.75%

解法二：max - min < 5

参考题解：[面试题61. 扑克牌中的顺子（集合 Set / 排序，清晰图解）](https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solutions/212071/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se/)

盗个图：

    public boolean isStraight(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num == 0) {
                continue;
            }
            if (set.contains(num)) {
                return false;
            } else {
                set.add(num);
                if (max < num) {
                    max = num;
                }
                if (min > num) {
                    min = num;
                }
            }
        }
        return max - min < 5;
    }

时间0 ms击败100%

内存39.1 MB击败55.60%

面试题67. 把字符串转换成整数★

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

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

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

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

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

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

说明：

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

示例 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 (−231) 。

解题思路

很恶心的题。。。

抄个答案

解法一：模拟

    public int myAtoi(String s) {
        int sign = 1;
        int res = 0;
        int m = s.length();
        int i = 0;
        while(i < m && s.charAt(i)==' '){
            i++;
        }
        int start = i;
        for(; i < m; i++){
            char c = s.charAt(i);
            if(i==start && c=='+'){
                sign = 1;
            }else if(i==start && c=='-'){
                sign = -1;
            }else if(Character.isDigit(c)){
                int num = c-'0';
                if(res > Integer.MAX_VALUE/10 || (res == Integer.MAX_VALUE/10&&num>Integer.MAX_VALUE%10)){
                    return Integer.MAX_VALUE;
                }

                if(res < Integer.MIN_VALUE/10 || (res == Integer.MIN_VALUE/10&&-num<Integer.MIN_VALUE%10)){
                    return Integer.MIN_VALUE;
                }
                res = res*10+sign*num;
            }else{
                break;
            }
        }
        return res;
    }