【力扣刷题】_剑指offer68题

发表于 | 分类于

面试题2.实现singleton模式

tips：代码块中的注解、加粗、下划线部分为重点内容。

1. 题目

设计一个类，我们只能生成该类的一个实例。

2.单例模式

单例模式是一种常用的软件设计模式，在应用这个模式时，单例对象的类必须保证只有一个实例存在，整个系统只能使用一个对象实例。

优点：是不会频繁地创建和销毁对象，浪费系统资源。

使用场景：IO 、数据库连接、Redis 连接等。

3. 额外知识

类加载(classLoader)机制一般遵从下面的加载顺序：

  • 如果类还没有被加载：

    1. 先执行父类的静态代码块和静态变量初始化，静态代码块和静态变量的执行顺序跟代码中出现的顺序有关。
    2. 执行子类的静态代码块和静态变量初始化。
    3. 执行父类的实例变量初始化 (Java的成员变量有两种：一种是静态变量又叫类变量；一种是实例变量，也就是非成员方法内变量。成员方法内定义的变量又分为全局变量和局部变量。类变量是所有实例对象共有，其中一个实例对象将它的值改变，其他实例对象得到的就是改变后的结果；而实例变量则是每新建一个实例对象就会新建一个，某一个实例对象内将其值改变，不影响其他实例对象内的值。)
    4. 执行父类的构造函数
    5. 执行子类的实例变量初始化
    6. 执行子类的构造函数

    同时，加载类的过程是线程私有的，别的线程无法进入。

  • 如果类已经被加载：

    静态代码块和静态变量不在重复执行，再创建类对象时，只执行与实例相关的变量初始化和构造方法。

4. 方法一：饿汉模式

优点：类加载的时候创建一次实例，避免了多线程同步问题。

缺点：即使单例没被用到也会创建，浪费内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Hungry {
    //static关键字用来声明独立于对象的静态变量，无论一个类实例化多少对象，它的静态变量只有一份拷贝。
    //静态变量也被称为类变量，该变量在类被类加载器加载时就在jvm堆中分配了空间，并完成初始化赋值。
    private static Hungry instance = new Hungry();

    //同时为了避免单例的类被频繁创建对象，我们可以用private的构造函数来确保单例类无法被外部实例化。
    private Hungry(){}

    //static关键字用来声明独立于对象的静态方法，静态方法不能使用类的非静态变量。
    public static Hungry getInstance() {
        return instance;
    }
}

5. 方法二：静态内部类

只要程序中不使用内部类，JVM就不会去加载这个单例类，也不会创建单例对象，从而实现懒汉式的延迟加载。这种方式可以同时保证延迟加载和线程安全。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class StaticInternClass {
    private StaticInternClass(){}

    private static class SingletonHodler{

        //因为类的静态属性只会在第一次加载类的时候初始化，也就保证了SingletonInstance中的对象只会被实例化一次。
        private static StaticInternClass INSTANCE = new StaticInternClass();
    }

    //这种静态内部类方式在Singleton类被装载时并不会立即实例化，而是在需要实例化时，调用getInstance方法，才会装载SingletonInstance类，从而完成对象的实例化。
    public static StaticInternClass getInstance(){
        return SingletonHodler.INSTANCE;
    }
}

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

方法一：遍历数组

思路：利用集合中元素不可重复的特性

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findNum(int[] nums) {
        int ans = -1;

        //java中集合Set的常用实现类是HashSet
        Set<Integer> numsSet= new HashSet<>();
        for (int i = 0; i < nums.length; i++) {

            //Set.add()方法的返回值类型为boolean，表示输入参数是否成功添加到集合中去了，如果集合中已存在该元素则无法添加。
            if (!numsSet.add(nums[i])) {
                ans = nums[i];
                break;
            }
        }
        return ans;
    }
}

方法二：原地置换(剑指offer原答案)

这种方法太巧妙了，只能背原题，让直接自己想出来是不可能的。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution1 {
    public int findNum(int[] nums) {
        int temp;
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {

                //如果满足该判断语句则表示不同位置索引nums[i]和i两处的值相同
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }

                temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }

        return -1;
    }
}

面试题4.二维数组中的查找

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof

方法一：暴力法

时间复杂度：O(n*m)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (target == matrix[i][j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

方法二：线性查找

思路：从矩阵的右上角开始查找，如果元素比target大，则左移一位继续比较；如果元素比target小，则下移一位继续比较，循环上述步骤，知道找到target或者到达矩阵边界。（从矩阵的左下角开始查找一样可行）

时间复杂度：O(n+m)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution1 {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0) return false;
        int n = matrix.length,m = matrix[0].length;
        int row = 0,column = m - 1;
        while (row < n && column > -1) {
            if (target == matrix[row][column]) return true;
            else if (target < matrix[row][column]) column--;
            else row++;
        }
        return false;
    }
}

面试题5.替换空格

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    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();
    }
}

面试题6.从尾到头打印链表

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1：

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

方法一：栈

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> ints = new Stack<>();
        int length = 0;
        while (head != null) {
            ints.push(head.val);
            length++;
            head = head.next;
        }
        int[] ans = new int[length];
        for (int i = 0; i < length; i++) {
            ans[i] = ints.pop();
        }
        return ans;
    }
}

面试题7.重建二叉树

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

例如，给出

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

返回如下的二叉树：

​ 3

/
9 20
/
15 7

链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof

方法一：递归

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        if (n == 0) return null;
        int cut = 0;
        for (int i = 0; i < n; i++) {
            if (inorder[i] == preorder[0]) {
                cut = i;
                break;
            }
        }
        int[] leftpre = new int[cut];
        int[] leftin = new int[cut];
        int[] rightpre = new int[n - cut - 1];
        int[] rightin = new int[n - cut - 1];
        for (int i = 0; i < cut; i++) {
            leftpre[i] = preorder[i + 1];
        }
        for (int i = 0; i < cut; i++) {
            leftin[i] = inorder[i];
        }
        for (int i = 0; i < n - cut - 1; i++) {
            rightpre[i] = preorder[cut + 1 + i];
        }
        for (int i = 0; i < n - cut - 1; i++) {
            rightin[i] = inorder[cut + 1 + i];
        }

        TreeNode node = new TreeNode(preorder[0]);
        node.left = buildTree(leftpre,leftin);
        node.right = buildTree(rightpre,rightin);
        return node;
    }
}

面试题9.用两个栈实现队列

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1：

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

示例 2：

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

链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof

方法一：双栈

思路：使用左栈和右栈，左栈只负责压入数据，右栈只负责弹出数据，在每次弹出时检测右栈是否为空，为空则将左栈中数据全部移入右栈，如果左栈也为空说明该队列为空。

入队和出队时间复杂度：O(1)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class CQueue {

    private Stack<Integer> left;
    private Stack<Integer> right;

    public CQueue() {
        this.left = new Stack<>();
        this.right = new Stack<>();
    }

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

    public int deleteHead() {
        if (right.empty()) {
            if (left.empty()) return -1;
            else {
                while (!left.empty()) {
                    right.push(left.pop());
                }
            }
        }
        return right.pop();
    }
}

面试题10_1.斐波那契数列

tips：代码块中的注解、加粗、下划线部分为重点内容。

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

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

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

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return (fib(n - 1) + fib(n - 2)) % 1000000007;
    }
}

方法二：动态规划

由于使用递归方法会进行大量重复的递归计算，所以非常容易超时。

这里我们采用简化的动态规划方法，可以达到在不增加空间复杂度的情况下减小时间复杂度。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution1 {
    public int fib(int n) {
        //选择a、b作为状态变量，并初始化
        int a = 0,b = 1,temp = 0;

        //状态转移方程
        for (int i = 0; i < n; i++) {

            //当n很大的时候可能会出现数字溢出，所以我们需要用结果对1000000007求余。
            temp = (a + b) % 1000000007;
            a = b;
            b = temp;
        }

        return a;
    }
}

面试题10_2.青蛙跳台阶问题

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof

方法一：动态规划

思路：跳上n级台阶的最后一步有可能是直接从n-2级台阶直接跳上来，也有可能是从n-1级台阶跳上来，那么将这两种情况的跳法相加，即为结果。

本题采用优化的动态规划，简化了空间复杂度。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numWays(int n) {
        if (n < 2) return 1;

        //初始化
        int dp1 = 1,dp2 = 2,temp;

        for (int i = 1; i < n; i++) {
            temp = (dp1 + dp2) % 1000000007;
            dp1 = dp2;
            dp2 = temp;
        }

        return dp1;
    }
}

面试题11.旋转数组的最小数字

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1：

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

示例 2：

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

链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

方法一：二分搜索

重要：这道题的数组中可以包含相等元素，比不包含相等元素要难得多。

平均时间复杂度：O(logn)

最差时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minArray(int[] numbers) {
        int left = 0,right = numbers.length - 1,mid;

        while (right > left) {
            mid = (left + right)/2;
            if (numbers[mid] < numbers[right]) {
                right = mid;
            }else if (numbers[mid] > numbers[right]){
                
                //这里这个+1非常重要，保证了每次循环范围都会缩小。
                left = mid + 1;
            }else {
                
                //也就是numbers[mid]==numbers[right]的情况，则将右边界一个一个往左挪。
                right--;
            }
        }
        return numbers[left];
    }
}

总结

非常重要：本题中要在每次循环中将中间点数值与右边界数值进行比较判断，而不能将中间点数值与左边界数值进行比较判断，否则会麻烦很多。

一定要注意，将中间点数值与左边界数值还是右边界数值比较是有不同意义的，在做题时可以尝试比较两者区别，选择更加合适比较方式。

面试题12.矩阵中的路径

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

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

示例 1：

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

示例 2：

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

链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof

方法一：递归回溯法

用一个保存boolean类型值的矩阵保存每个格子是否已经被经过过。

空间复杂度：O(K)（k为递归层数，也就是字符串长度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean exist(char[][] board, String word) {
        int n = board.length,m = board[0].length,l = word.length();
        boolean[][] mark = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (stringExist(board,mark,l,0,i,j,word)) return true;
            }
        }

        return false;
    }

    public boolean stringExist(char[][] board,boolean[][] mark,int stringLength,int index,int row,int column,String word) {
        if (stringLength == index) return true;
        if (row > -1 && row < board.length && column > -1 && column < board[0].length && board[row][column] == word.charAt(index) && !mark[row][column]) {
            mark[row][column] = true;
            if (stringExist(board,mark,stringLength,index + 1,row + 1,column,word)) return true;
            if (stringExist(board,mark,stringLength,index + 1,row - 1,column,word)) return true;
            if (stringExist(board,mark,stringLength,index + 1,row,column + 1,word)) return true;
            if (stringExist(board,mark,stringLength,index + 1,row,column - 1,word)) return true;

            //这一步非常重要，如果一条路失败了，一定不能忘记回溯。
            mark[row][column] = false;
        }
        return false;
    }
}

总结

本题中的回溯代码很容易忘记写，一定不能忘了。深度优先遍历时，一条路走不通了换另一条路时一定要先回溯。

面试题13.机器人的运动范围

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof

方法一：动态规划

思路：机器人能到达的格子的上或左边的格子也一定能到达。

时间复杂度：O(mn)

空间复杂度：O(mn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int movingCount(int m, int n, int k) {
        int count = 0;

        //状态：机器人能否到达该格子
        boolean[][] dp = new boolean[m][n];

        //状态转移方程
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                    count++;
                    continue;
                }
                if ((this.get(i) + this.get(j) <= k) && ((((i - 1) > -1) && dp[i - 1][j]) || (((j - 1) > -1) && dp[i][j - 1]))) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }

        return count;
    }

    /**
     * 求十进制数x各位之和的方法
     */
    public int get(int x) {
        int sum = 0;
        while (x != 0) {
            sum = sum + x % 10;
            x = x / 10;
        }
        return sum;
    }
}

总结

本题中求十进制数各位之和的方法写的比较简洁，可以记一下。

面试题14_1.剪绳子

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof

方法一：高数推导

由高数计算公式推导得出：1.当所有绳段长度相等时，乘积最大。2.最优的绳段长度为3。

那么就是用总绳长除3：余数位0则正好；余数为2则最后一段长度为2；余数为1则将一段长度为3的片段拿出来与1一起组成一个长度为4的片段。

时间复杂度：O(1)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        int count = n / 3;
        int temp = n % 3;
        if (temp == 0) {
            //java中的^是位异或运算符，并不是幂运算符。
            //java中的幂运算要使用方法double Math.pow(double,double)
            return (int)Math.pow(3,count);
        }else if (temp == 2) {
            return (int)Math.pow(3,count)*2;
        }else {
            return (int)Math.pow(3,count - 1)*4;
        }
    }
}

方法二：动态规划

比较少见的动态规划，每次计算一个状态值时，把前面的每一个状态值都用到了。

这种动态规划用法也一定要掌握。

思路：首先我们把一段长度为i绳子分成两段，一段长度为j，另一端长度为i-j：

那么会有四种情况：

  1. j和i-j都不能再拆了：dp[i]=j*(i-j);
  2. j能拆，i-j不能拆：dp[i]=dp[j]*(i-j);
  3. j不能拆，i-j能拆：dp[i]=j*dp[i-j];
  4. j和i-j都能拆：dp[i]=dp[j]*dp[i-j];

我们取上面4种情况的最大值即可，我们把它整理一下，得到递推公式如下：

dp[i] = max(dp[i], (max(j, dp[j])) * (max(i - j, dp[i - j])));

时间复杂度：O(n^2)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution1 {
    public int cuttingRope(int n) {
        if (n <= 3) return n - 1;

        //状态：一段长度为n的绳子能得到的最大乘积
        int[] dp = new int[n + 1];

        //初始化：
        dp[2] = 1;
        dp[3] = 2;

        //状态转移方程
        for (int i = 4; i <= n; i++) {

            //分成最小的一段就是2，一般不考虑长度为1的分段。
            for (int j = 2; j < i - 1; j++) {
                dp[i] = Math.max(dp[i],Math.max(j,dp[j])*Math.max(i - j,dp[i - j]));
            }
        }

        return dp[n];
    }
}

面试题14_2.剪绳子2

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof

方法一：高数推导

本题相比于面试题14_1.剪绳子其实就是增加了一个取模的条件，所以大致思路不变，只需改变计算细节，本质上变成了一道考察Interger、Long、Double数据类型取值范围的题目。

本题中要求每次乘3之后都要取模，所以不能直接用Math.pow方法直接一下求出double类型结果。但是int类型的取值范围为-2147483648~+2147483647，计算结果有可能直接在一次乘3之后直接溢出了，所以此处我们设置结果数据类型为long或者double，一次一次乘3的计算，每次乘3后都取模。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        int count = n / 3;
        int temp = n % 3;
        double ans = 1;
        int p = 1000000007;

        //本题中要求每次乘3之后都要取模，所以不能直接用Math.pow方法直接一下求出double类型结果。
        //但是int类型的取值范围为-2147483648~+2147483647，计算结果有可能直接在一次乘3之后直接溢出了，
        //所以此处我们设置结果数据类型为long或者double，一次一次乘3的计算，每次乘3后都取模。
        if (temp == 0) {
            for (int i = 0; i < count; i++) {
                ans = ans * 3 % p;
            }
            return (int)ans;
        }else if (temp == 2) {
            for (int i = 0; i < count; i++) {
                ans = ans * 3 % p;
            }
            ans = ans * 2 % p;
            return (int)ans;
        }else {
            for (int i = 0; i < count - 1; i++) {
                ans = ans * 3 % p;
            }
            ans = ans * 2 % p;
            ans = ans * 2 % p;
            return (int)ans;
        }
    }
}

面试题15.二进制中1的个数

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1：

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

示例 2：

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

示例 3：

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

链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof

方法一：位运算

位与运算准则：

  • n&1=1，则n二进制最后一位为1；
  • n&1=0，则n二进制最后一位为0。

思路：将n与1进行为与运算，然后将n无符号右移一位。循环以上步骤，直到n为0。

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            if ((n & 1) == 1) count++;
            n = n >>> 1;
        }
        return count;
    }
}

java位运算之左移、右移与无符号右移

  • <<：左移运算符：左操作数按位左移右操作数指定的位数。移动得到的右边空位自动充零，注意包括符号位，也就是说左移运算符有可能改变一个数的正负。
  • >>：右移运算符：左操作数按位右移右操作数指定的位数。移动得到的左边空位自动充零，但是表示符号的最高位除外，正数右移高位补0，负数右移高位补1。
  • >>>：无符号右移运算符：左操作数按位右移右操作数指定的位数。移动得到的左边空位自动充零，无论是正数还是负数，最高位通通补0。

面试题16.数值的整数次方

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

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

链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof

方法一：递归+二分法

把递归简化一下：当n为正偶数时，myPow(double x, int n)==myPow(double x*x, int n/2)。

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        
        if (n > 0) {
            if (n % 2 == 0) {
                return myPow(x * x,n / 2);
            }
            return x * myPow(x,n - 1);
        }
        
        return 1.0 / (myPow(x,-n - 1) * x);
    }
}

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1:

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

链接：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof

方法一：递归

大数越界问题：无论是short、int、long…任意数字数据类型，数字的取值范围都是有限的，超出取值范围的数字无法正常存储。

解决方法：要从根本上解决大数越界问题，大数的表示应使用字符串String类型。

思路：先确定高位，再确定低位，从0到9，这样才能保证最后的结果字符串中数字是按升序排列。

时间复杂度：O(10^n)

空间复杂度：O(10^n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution1 {
    public String printNumbers(int n) {
        StringBuilder ans = new StringBuilder();
        char[] answer = new char[n];
        char[] loop = new char[]{'0','1','2','3','4','5','6','7','8','9'};

        dfs(answer,ans,0,n,loop);

        //将ans最后的逗号删掉
        ans.deleteCharAt(ans.length() - 1);
        return ans.toString();
    }

    public void dfs(char[] answer,StringBuilder ans,int index,int n,char[] loop) {
        //递归终止条件
        if (index == n) {
            ans.append(new String(answer));
            ans.append(',');
            return;
        }

        for (char num : loop) {
            answer[index] = num;
            dfs(answer,ans,index + 1,n,loop);
        }
    }
}

总结

本题中的很多类型转换可以参考博文java数字的进制转换&数据类型转化。

面试题18.删除链表的节点

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

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

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

链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof

方法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode god = new ListNode(0);
        god.next = head;
        if (head == null) return null;
        if (head.val == val) return head.next;

        while (head != null && head.next != null) {
            if (head.next.val == val) head.next = head.next.next;
            head = head.next;
        }

        return god.next;
    }
}

面试题19.正则表达式匹配

tips：代码块中的注解、加粗、下划线部分为重点内容。

请实现一个函数用来匹配包含’. ‘和’*‘的正则表达式。模式中的字符’.’表示任意一个字符，而’*‘表示它前面的字符可以出现任意次（含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 = “misis*p.”
输出: false

链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof

方法一：递归

因为*符号要和它前面的一个字母进行组合来进行匹配，所以我们从后往前来进行递归遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(),n = p.length();
        if (m == 0 && n == 0 ) return true;
        if (n == 0) return false;
        if (p.charAt(n - 1) == '*') {
            //p字符串以*字符打头的情况
            if (n == 1) {
                return m == 0;
            }

            if (m != 0 && (p.charAt(n - 2) == s.charAt(m - 1) || p.charAt(n - 2) == '.')) {

                //这一步是该题递归的关键：第一种情况表示*组合不匹配该字符；第二种情况表示*组合匹配一个该字符，但*组合可以继续匹配。
                //一定要理解这两种情况就囊括了所有的情况，因为无论是匹配多少个连续相同的该字符，都是重复递归该句实现的。
                //比如*组合匹配一个字符，就是先第二种情况再第一种情况；匹配两个字符，就是先第二种情况再第二种情况最后第一种情况，依此类推。
                return isMatch(s.substring(0, m), p.substring(0, n - 2)) || isMatch(s.substring(0, m - 1), p.substring(0, n));
            }

            //*符号前一个符号与s中该符号无法匹配的情况
            return isMatch(s.substring(0, m), p.substring(0, n - 2));
        }
        if (m == 0) return false;
        if (p.charAt(n - 1) == '.' || s.charAt(m - 1) == p.charAt(n - 1)) return isMatch(s.substring(0,m - 1),p.substring(0,n - 1));
        return false;
    }
}

方法二：动态规划

见10.正则表达式匹配(非常重要)此处不再复写，两种方法进行比较：整体思路是一样的，递归方法时间复杂度更大，空间复杂度更小，面试时更推荐使用动态规划。

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例：

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

链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof

方法一：双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] exchange(int[] nums) {
        int left = 0,right = nums.length - 1;
        while (left < right) {
            if (nums[left] % 2 == 0) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                right--;
            }else {
                left++;
            }
        }
        return nums;
    }
}

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例：

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

链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof

方法一：栈

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        for (int i = 0; i < k - 1; i++) {
            stack.pop();
        }
        return stack.peek();
    }
}

方法二：双指针

很多数组和链表的题都可以用双指针啊，最主要是要计算处两个指针之间的数学关系，能使用双指针就尽量不要使用栈等其他数据结构。

前指针先走k步，然后同步前进，前指针走完链表时，后指针刚好到倒数第k个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution1 {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head,slow = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

面试题24.反转链表

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例:

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

链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode temp = head;
        if (temp == null) return null;
        if (temp.next == null) return head;
        while (temp.next.next != null) {
            temp = temp.next;
        }
        ListNode newHead = temp.next;
        temp.next = null;
        newHead.next = reverseList(head);
        return newHead;
    }
}

方法二：双指针

双指针方法也就是迭代的方法，就是一个接一个地反转节点的指向，相比于递归方法，时间复杂度O(n)不变，空间复杂度从O(n)变成了O(1)，所以还是双指针方法更好。此处不再复写。

面试题25.合并两个排序的链表

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例1：

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

链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        if (l1.val <= l2.val) {
            ListNode head = l1;
            l1 = l1.next;
            head.next = mergeTwoLists(l1,l2);
            return head;
        }else {
            ListNode head = l2;
            l2 = l2.next;
            head.next = mergeTwoLists(l1,l2);
            return head;
        }
    }
}

面试题26.树的子结构

tips：代码块中的注解、加粗、下划线部分为重点内容。

输入两棵二叉树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

链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof

方法一：前序遍历+递归

这实现方法太巧妙了，要硬记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {

    //用于前序遍历的方法，递归地遍历A中每一个节点是否与B根节点的值相同
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A != null && B != null) return isEquel(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
        return false;
    }

    //在A中找到与B根节点相等的节点之后，判断B是否可以完全对应上去
    public boolean isEquel(TreeNode A, TreeNode B) {
        //递归终止条件
        if (B == null) return true;

        if (A == null) return false;
        if (A.val == B.val) return isEquel(A.left,B.left) && isEquel(A.right,B.right);
        return false;
    }
}

面试题27.二叉树的镜像

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

例如输入：

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]

链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof

方法一：递归

1
2
3
4
5
6
7
8
9
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        return root;
    }
}

面试题28.对称的二叉树

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

链接：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isEquel(root.left,root.right);
    }

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

面试题29.顺时针打印矩阵

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

链接：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof

方法一：按层模拟

思路：把矩阵看成若干层，最先打印最外层，然后打印次外层…

定义矩阵中的第k层是由距离最近边界为k的顶点所组成的。

时间复杂度：O(m*n)

空间复杂度：O(1) //空间复杂度是指除了返回值以外，额外使用的内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) return new int[0];
        int n = matrix[0].length;
        int[] ans = new int[m * n];
        int count = 0;
        int left = 0,right = n - 1,top = 0,bottum = m - 1;

        //此处这个循环条件是本题的关键，这个循环条件一定要记住。
        while (left <= right && top <= bottum) {
            for (int i = left;i <= right;i++) {
                ans[count] = matrix[top][i];
                count++;
            }
            for (int i = top + 1; i <= bottum; i++) {
                ans[count] = matrix[i][right];
                count++;
            }
            //必须要在该层能围成一个圈的时候，才能接着遍历下边和左边，否则根本就没有下边和左边，会导致上边和右边遍历两次。
            if (left < right && top < bottum) {
                for (int i = right - 1;i >= left;i--) {
                    ans[count] = matrix[bottum][i];
                    count++;
                }
                for (int i = bottum - 1; i > top; i--) {
                    ans[count] = matrix[i][left];
                    count++;
                }
            }
            left++;
            right--;
            top++;
            bottum--;
        }
        return ans;
    }
}

面试题30.包含min函数的栈

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof

方法一：双栈

思路：本题的关键在于，每删除一个最小元素时，所记录的最小元素能退回到原来所记录的最小元素，也就是说需要一个辅助栈，其长度与主栈一直相同，记录主栈在每个时刻的最小元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class MinStack {

    Stack<Integer> mainStack;
    Stack<Integer> helpStack;

    /** initialize your data structure here. */
    public MinStack() {
        this.mainStack = new Stack<>();
        this.helpStack = new Stack<>();
    }

    public void push(int x) {
        this.mainStack.push(x);
        if (this.helpStack.isEmpty()) {
            this.helpStack.push(x);
            return;
        }
        this.helpStack.push(this.helpStack.peek() > x ? x : this.helpStack.peek());
    }

    public void pop() {
        this.mainStack.pop();
        this.helpStack.pop();
    }

    public int top() {
        return this.mainStack.peek();
    }

    public int min() {
        return this.helpStack.peek();
    }
}

面试题31.栈的压入弹出序列

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof

方法一：辅助栈

这道题也属于一个巧思，需要硬记。

思路：就是创建一个辅助栈来真正模拟该栈，将入栈队列依次压入栈中，每压入一个元素，检验出栈队列是否需要将栈顶元素出栈。若执行完上述操作之后，辅助栈正好为空，说明此出栈队列可以对应上入栈队列。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int count = 0;
        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[count]) {
                stack.pop();
                count++;
            }
        }
        return stack.isEmpty();
    }
}

面试题32_1.从上到下打印二叉树

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

​ 3

/
9 20
/
15 7

返回：

[3,9,20,15,7]

链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof

方法一：队列

嘿嘿，小爷早就总结了二叉树的各种非递归遍历方法，思路见博文二叉树的非递归遍历方法。

Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] levelOrder(TreeNode root) {
        List<Integer> answer = new ArrayList<>();

        //java中的队列一般使用链表来实现。
        Queue<TreeNode> queue = new LinkedList<>();

        if (root == null) return new int[0];
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            answer.add(temp.val);
            if (temp.left != null) queue.offer(temp.left);
            if (temp.right != null) queue.offer(temp.right);
        }
        int[] ans = new int[answer.size()];
        for (int i = 0; i < answer.size(); i++) {
            ans[i] = answer.get(i);
        }
        return ans;
    }
}

面试题32_2.从上到下打印二叉树2

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

例如:

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

3

/
9 20
/
15 7

返回其层次遍历结果：

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

链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof

方法一：队列

嘿嘿，小爷早就总结了二叉树的各种非递归遍历方法，思路见博文二叉树的非递归遍历方法。

思路：可以发现，每当遍历完一层的二叉树节点时，这时队列中的元素正好是下一层中的所有节点。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> subAns = new ArrayList<>();
            int rowSize = queue.size();
            for (int i = 0; i < rowSize; i++) {
                TreeNode temp = queue.poll();
                subAns.add(temp.val);
                if (temp.left != null) queue.offer(temp.left);
                if (temp.right != null) queue.offer(temp.right);
            }
            ans.add(subAns);
        }
        return ans;
    }
}

面试题32_3.从上到下打印二叉树3

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

例如:

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

3

/
9 20
/
15 7

返回其层次遍历结果：

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

链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof

方法一：队列+双端链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        Queue<TreeNode> queue = new LinkedList<>();
        boolean flag = false;
        queue.offer(root);
        while (!queue.isEmpty()) {

            //当方法声明返回值类型为List时，返回List、ArrayList和LinkedList类型的数据都可以，不会报错。
            LinkedList<Integer> subAns = new LinkedList<>();

            int rowSize = queue.size();
            for (int i = 0; i < rowSize; i++) {
                root = queue.poll();

                //addFirst()方法就是在链表头部添加元素。
                if (flag) subAns.addFirst(root.val);

                //addLast()方法就是在链表尾部添加元素，与add()方法作用相同。
                else subAns.addLast(root.val);
                if (root.left != null) queue.offer(root.left);
                if (root.right != null) queue.offer(root.right);
            }
            ans.add(subAns);
            flag = !flag;
        }
        return ans;
    }
}

方法二：双端队列+链表

同理也可以利用双端队列的属性，代码不再复写。

总结

  • java中的LinkedList数据结构具有双向链表的属性，所以可以用它具有addFirst()和addLast()方法分别可以向数组两端添加元素，具有removeFirst()和removeLast()分别向数组两端删除元素。

    其中，addFirst()方法就是在链表头部添加元素。addLast()方法就是在链表尾部添加元素，与add()方法作用相同。

    由LinkedList实现的队列Queue自然也具有双端队列的属性，也具有上述的四个方法。

  • 当方法声明返回值类型为List时，返回List、ArrayList和LinkedList类型的数据都可以，不会报错。

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

​ 5
/ \

2 6
/
1 3

示例 1：

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

示例 2：

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

链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof

方法一：递归

思路：一个二叉搜索树的后序遍历结果的格式一定是{小于根节点的节点，大于根节点的节点，根节点}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        int length = postorder.length;
        if (length < 3) return true;
        int count = 0;
        while (postorder[length - 1] > postorder[count]) {
            count++;
        }
        for (int i = count; i < length - 1; i++) {
            if (postorder[i] < postorder[length - 1]) return false;
        }

        //小于根节点的节点所组成的数组
        int[] left = new int[count];
        for (int i = 0; i < count; i++) {
            left[i] = postorder[i];
        }

        //大于根节点的节点所组成的数组
        int[] right = new int[length - 1 - count];
        for (int i = 0; i < length - 1 - count; i++) {
            right[i] = postorder[i + count];
        }

        return verifyPostorder(left) && verifyPostorder(right);
    }
}

方法二：官方答案

注意官方答案与我自己写的代码的主要区别，明显我自己写的代码空间复杂度更大且可读性更差。因为每次递归我都在原输入数组的基础之上截取一部分连续元素作为下一层递归方法的输入数组，其实这样没有必要。

以后遇到这种情况都学习该官方答案中的写法：创建一个新的递归方法，该方法的输入参数为数组、截取起始点和截取终止点，每层递归都使用同一个数组作为输入，只不过截取部分不一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution1 {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while(postorder[p] > postorder[j]) p++;
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例:

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

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

返回:

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

链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof

方法一：递归回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> answers = new ArrayList<>();
        if (root == null) return answers;
        List<Integer> temp = new ArrayList<>();
        path(root,sum,answers,temp);
        return answers;
    }

    public void path(TreeNode root,int sum,List<List<Integer>> answers,List<Integer> temp) {
        if (root == null ) return;
        
        //注意一定要到达叶子节点时才算做一条路径
        if (root.val == sum && root.left == null && root.right ==null) {
            temp.add(root.val);

            //注意这里一定要新建一个链表加到最终返回链表中，如果直接把临时链表temp加到最终返回链表中，
            //则最终返回链表中的元素指向的其实就是一直在改变的temp。
            List<Integer> answer = new ArrayList<>(temp);

            answers.add(answer);

            //回溯
            temp.remove(temp.size() - 1);
        }else {
            
            //注意节点有可能是负值，所以每条路径都要查询到最深处才能确定这条路径的节点值之和等不等于sum
            temp.add(root.val);
            path(root.left,sum - root.val,answers,temp);
            path(root.right,sum - root.val,answers,temp);
            temp.remove(temp.size() - 1);
        }
    }
}

面试题35.复杂链表的复制

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

方法一：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public Node copyRandomList(Node head) {

        //使用hashMap记录每个节点与复制节点作为一个键值对，
        //方便第二次遍历时为复制链表的节点添加random属性时直接找到复制链表中的对应节点。
        HashMap<Node,Node> hashMap = new HashMap<>();
        hashMap.put(null,null);

        //原链表哑节点
        Node temp = new Node(0);
        temp.next = head;

        //复制链表哑节点
        Node copyTemp = new Node(0);
        Node current = copyTemp;

        //第一次遍历，按照next属性创建好初步的复制链表
        while (head != null) {
            Node node = new Node(head.val);
            hashMap.put(head,node);

            current.next = node;
            current = current.next;
            head = head.next;
        }

        //第二次遍历，完善复制链表中每个节点的random属性
        head = temp.next;
        current = copyTemp.next;
        while (head != null) {
            current.random = hashMap.get(head.random);
            head = head.next;
            current = current.next;
        }
        return copyTemp.next;
    }
}

方法二：拼接与拆分

这种方法相比于方法一减小了空间复杂度，只使用了常数级内存空间，具体实现代码不再复写。

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

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

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

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

链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof

方法一：递归中序遍历

非递归的中序遍历和后序遍历代码写起来本来就比较麻烦，就算是最简单的前序遍历的非递归代码写起来也比递归代码要麻烦的多。所以非递归一时比较难想，而且要结合别的操作的情况下，还是用递归方法来对二叉树进行前中后序遍历比较好。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {

    //使用递归方法时，多用且善用全局变量，很多时候不能用局部变量代替全局变量，比如本题中这两个全局变量。
    //pre为前驱节点，head为哑节点。
    Node pre;
    Node head = new Node();

    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        dfs(root);
        pre.right = head.right;
        head.right.left = pre;
        return head.right;
    }

    //中序遍历方法，全局变量pre用于使不同层次递归方法中被遍历的节点之间进行交流，非常重要。
    public void dfs(Node root) {
        if (root == null) return;

        /**
         * 遍历左子树
         */
        //重要：pre会在本次访问之前先在递归方法中被改变，
        //所以在本次访问中使用到的pre是已经经过了很多次递归方法修改之后返回来的pre。
        dfs(root.left);

        /**
         * 访问本节点
         */
        //如果pre已经赋上值了，说明本次访问的节点具有前驱节点；
        //如果没有赋值，则说明本次访问的节点为头结点。
        if (pre != null) pre.right = root;
        else head.right = root;
        root.left = pre;
        pre = root;

        /**
         * 遍历右子树
         */
        dfs(root.right);
    }
}

面试题37.序列化二叉树

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例:

你可以将以下二叉树：
​ 1

/
2 3
/
4 5

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

链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof

方法一：层序遍历

总体思路：通常使用的前序、中序、后序、层序遍历记录的二叉树的信息不完整，即唯一的输出序列可能对应着多种二叉树可能性。题目要求的序列化和反序列化是可逆操作。因此，序列化的字符串应携带完整的二叉树信息，使其所表示的二叉树是唯一确定的。

序列化思路：为完整表示二叉树，考虑将叶节点下的null也记录。在此基础上，对于列表中任意某节点node，其左子节点node.left和右子节点node.right在序列中的位置都是唯一确定的。也就是说只要把二叉树中度为0和1的节点都补上值为null的辅助空子节点，得到的层序遍历结果就可以与一棵唯一的二叉树对应。

反序列化思路：查看具体实现代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Codec {

    //二叉树序列化为字符串
    public String serialize(TreeNode root) {
        if (root == null) return "[]";
        StringBuilder ans = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (root != null) {
                ans.append(root.val);
                queue.offer(root.left);
                queue.offer(root.right);
            } else ans.append("null");
            ans.append(",");
        }
        ans.deleteCharAt(ans.length() - 1);
        ans.append("]");
        return ans.toString();
    }

    //字符串反序列化为二叉树
    public TreeNode deserialize(String data) {
        if (data.equals("[]")) return null;

        //重要：String.split("*")方法可以将字符串以*字符参数为分隔符，分割成一个字符串数组。
        String[] vals = data.substring(1,data.length() - 1).split(",");

        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        TreeNode head = root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty()) {
            //每次将队列queue中的一个节点取出，这时数组中对应的下两个值vals[i]和vals[i+1]就正好是该节点的左右子节点的值。
            root = queue.poll();
            if (!vals[i].equals("null")) {
                root.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(root.left);
            }
            i++;
            if (!vals[i].equals("null")) {
                root.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(root.right);
            }
            i++;
        }
        return head;
    }
}

总结

二叉树层序遍历就是最典型的广度优先搜索(BFS)。

面试题38.字符串的排列

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

示例:

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

链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof

方法一：递归回溯+剪枝

本题的关键时在递归回溯的基础之上去除重复。

思路：要解决重复问题，我们只要设定一个规则，保证在填第i个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中从左往右第一个未被填过的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public String[] permutation(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();

        //将字符进行排序，使得相同字符连续放置，这样在判断数组中是否具有相同元素时，只需要与相邻字符比较即可。
        Arrays.sort(chars);

        //该数组用来标记chars数组中那个字符已经被使用过了，则在后面的递归中不能再使用该字符。
        boolean[] mark = new boolean[n];

        List<String> ans = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(chars,mark,0,sb,ans);
        String[] answers = new String[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            answers[i] = ans.get(i);
        }
        return answers;
    }

    public void dfs(char[] chars,boolean[] mark,int index,StringBuilder sb,List<String> ans) {
        if (index == chars.length) {
            ans.add(sb.toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {

            //没有被使用并且(和前一个字符不同或者前一个相同字符已经使用了)的字符，才会被考虑添加到字符串上。
            if (!mark[i]) {
                if (i > 0 && !mark[i - 1] && chars[i] == chars[i - 1]) continue;
                mark[i] = true;
                sb.append(chars[i]);
                dfs(chars,mark,index + 1,sb,ans);
                sb.deleteCharAt(sb.length() - 1);
                mark[i] = false;
            }
        }
    }
}

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

示例 1:

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

链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof

方法一：中位数

先排序，再找中位数，数组中位数一定是出现次数超过一半的那个数。

1
2
3
4
5
6
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

方法二：摩尔投票法

这是巧思，得硬记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution1 {
    public int majorityElement(int[] nums) {
        int x = 0,votes = 0;
        for (int num : nums) {

            //每个元素有一次投票的机会，只能投一个元素，相同的投赞成，不同的投反对，
            //一旦一个元素票数到0就换被投票的人，最后得到的一定是出现次数超过一半的元素。
            if (votes == 0) x = num;
            if (num == x) votes++;
            else votes--;
        }
        return x;
    }
}

面试题40.最小的k个数

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof

方法一：排序

时间复杂度：O(nlogn)

空间复杂度：O(logn)(此处主要是Array.sort()方法所需要的额外内存空间)

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        int[] ans = new int[k]
        for (int i = 0; i < k; i++) {
            ans[i] = arr[i];
        }
        return ans;
    }
}

方法二：堆排序

堆就是专门设计出来解决topk问题的，也就是专门设计出来寻找一个具有可比较元素的数组的前k大的元素或者前k小的元素。本题中堆排序优于快速排序。

java中主要使用工具类中的PriorityQueue来作为二叉堆的底层实现，主要有offer、poll、peek三个方法。

思路：先将数组中前k个元素放入二叉大根堆中，然后遍历剩下的元素，若元素小于堆顶元素则删除堆顶元素再将该元素添加到二叉大根堆中。

时间复杂度：O(nlogk)

空间复杂度：O(logk)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution1 {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] ans = new int[k];
        if (k == 0) return ans;

        //java中使用输入了比较器参数的优先级队列作为二叉堆的底层实现。
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {

                //注意此处比较器方法的复写决定了该队列实现的是大根堆还是小根堆，
                //第二个参数减第一个参数表示逆序排序，也就是大的值放在上面，小的值放在下面，表示该队列实现的是大根堆。
                return o2 - o1;
            }
        });

        for (int i = 0; i < k; i++) {
            queue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            if (arr[i] < queue.peek()) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }

        for (int i = k - 1; i > -1; i--) {
            ans[i] = queue.poll();
        }

        return ans;
    }
}

方法三：快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution2 {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        } else if (arr.length <= k) {
            return arr;
        }

        // 原地不断划分数组
        partitionArray(arr, 0, arr.length - 1, k);

        // 数组的前 k 个数此时就是最小的 k 个数，将其存入结果
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    void partitionArray(int[] arr, int lo, int hi, int k) {
        // 做一次 partition 操作
        int m = partition(arr, lo, hi);
        // 此时数组前 m 个数，就是最小的 m 个数
        if (k == m) {
            // 正好找到最小的 k(m) 个数
            return;
        } else if (k < m) {
            // 最小的 k 个数一定在前 m 个数中，递归划分
            partitionArray(arr, lo, m-1, k);
        } else {
            // 在右侧数组中寻找最小的 k-m 个数
            partitionArray(arr, m+1, hi, k);
        }
    }

    // partition 函数和快速排序中相同，具体可参考快速排序相关的资料
    // 代码参考 Sedgewick 的《算法4》
    int partition(int[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int v = a[lo];
        while (true) {
            while (a[++i] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (a[--j] > v) {
                if (j == lo) {
                    break;
                }
            }

            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, lo, j);

        // a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
        return j;
    }

    void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

总结

堆排序相对来说是大多数情况下的最优选。

面试题41.数据流中的中位数

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

例如，

[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]

链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof

方法一：二叉堆/优先队列

思路：创建两个二叉堆，第一个存放数据流中较小的一半数据，第二个存放数据流中较大的一半数据。

时间复杂度：

  • 查找中位数 O(1)： 获取堆顶元素使用 O(1) 时间；
  • 添加数字 O(log N)： 堆(优先队列)的插入和弹出操作使用 O(logN) 时间。

空间复杂度 O(N) ： 其中 N 为数据流中的元素数量，小顶堆 A 和大顶堆 B 最多同时保存 N 个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class MedianFinder {

    PriorityQueue<Integer> small;
    PriorityQueue<Integer> large;
    int sum;
    double ans;

    //构造函数
    //我的设想是：当数据总数为偶数时，两堆中存放数据量相同；当数据总数为奇数时，small堆中存放数据比large堆中多一个。
    public MedianFinder() {
        //小根堆
        this.small = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //大根堆
        this.large = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        this.sum = 0;
    }

    //添加数据时，如果数据总数为偶数，则先将数据放入large中，再将large的栈顶元素弹出放入small中；
    //如果数据总数为奇数，则先将数据放入small中，在将small的栈顶元素弹出放入large中。
    //这样是为了确保新添加进来的数据和数据流中的每个数据都进行了比较。
    public void addNum(int num) {
        if (sum % 2 == 0) {
            large.offer(num);
            small.offer(large.poll());
        }else {
            small.offer(num);
            large.offer(small.poll());
        }
        sum++;
    }

    public double findMedian() {
        if (sum == 0) return ans;
        if (sum % 2 == 0) return (double)(small.peek() + large.peek())/2;
        else return (double)small.peek();
    }
}

面试题42.连续子数组的最大和

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

示例1:

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

链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof

方法一：动态规划

与题目【力扣刷题】_53.最大子序和相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;


        //状态与初始化：表示以第i个数字为尾端的子数组的最大子数组和。
        int sum = nums[0];

        int maxSum = sum;

        //状态转移方程
        for (int i = 1; i < n; i++) {
            sum = Math.max(nums[i],sum + nums[i]);
            maxSum = Math.max(sum,maxSum);
        }

        return maxSum;
    }
}

面试题43.前n个整数中1出现的次数

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

示例 1：

输入：n = 12
输出：5

示例 2：

输入：n = 13
输出：6

链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof

方法一：迭代

巧思，需要硬记。

思路：将1~n中个位、十位、百位…中1出现的次数相加，即为1出现的总次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int countDigitOne(int n) {
        //hig记录高位值，curr记录当前位值，low记录低位值，count用来得到三个部分，ans表示该方法返回的答案。
        int count = 1,ans = 0;
        int high = n / 10;
        int curr = n % 10;
        int low = 0;
        while (high != 0 || curr != 0) {

            //当要计算某一位上1出现的次数时，将n分成三部分：高位、当前位、低位。
            //计算当前位上1出现的次数主要考虑高位-1和高位固定的情况：
            //高位-1的情况下，当前位和低位可以为任意值；
            //高位固定的情况下，当前位和低位连起来只能为更小的值。

            if (curr == 0) ans = ans + high * count;
            else if (curr == 1) ans = ans + high * count + low + 1;
            else ans = ans + (high + 1) * count;
            low = low + curr * count;
            curr = high % 10;
            high = high / 10;
            count = count * 10;
        }
        return ans;
    }
}

面试题44.数字序列中某一位的数字

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

链接：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof

方法一：找规律

巧思题，要硬记。

思路：观察总结发现该序列中数字09占据了序列的9位，数字1099占据了序列的90*2位，数字100~999占据了序列的900*3位…

  • 我们首先要判断第n位所在数字处于上述的哪一段中；
  • 然后判断出第n位所在数字是该段中的第几个数字，即可确定该数字的数值；
  • 然后确定第n位是该数字上的第几位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int findNthDigit(int n) {
        int count = 1;
        long digit = 9;
        long temp = digit * count;
        while (n > temp) {
            n = (int) (n - temp);
            count++;
            digit = digit * 10;
            temp = digit * count;
        }

        //序列中第n位所在数字所处段的前面有多少个数字。
        temp = temp / 9 / count;

        //序列中第n位所在数字
        long num = (n - 1) / count + temp;

        //第n位在该数字中的位置索引
        int index = (n - 1) % count;

        return Long.toString(num).charAt(index) - '0';
    }
}

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1:

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

示例 2:

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

链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof

方法一：快速排序

这道题本质上是一个排序问题，排序规则为：取出任意两个元素a和b，如果ab小于ba则应该将a放在b前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public String minNumber(int[] nums) {
        int n = nums.length;
        String[] strings = new String[n];
        for (int i = 0; i < n; i++) {
            strings[i] = String.valueOf(nums[i]);
        }
        quickSort(strings,0,n - 1);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(strings[i]);
        }
        return sb.toString();
    }

    //快速排序方法，其思路是以strings[left]为轴点元素，使用双指针分别从两端开始找，每次找到左指针大于轴点、右指针小于轴点时，
    //交换左右指针元素，知道两指针相遇，这时两指针指向的点会是最右端的小于或等于轴点的元素，
    //此时这段数组的布局：轴点|不大于轴点的元素|不小于轴点的元素。然后我们交换轴点元素和指针元素，再对两段子数组递归快速排序方法。
    void quickSort(String[] strings,int left,int right) {
        //递归终止条件：数组中元素小于两个。
        if (left >= right) return;

        int i = left,j = right;
        String temp = strings[i];
        while (i < j) {
            while ((strings[j] + strings[left]).compareTo(strings[left] + strings[j]) >= 0 && i < j) j--;
            while ((strings[i] + strings[left]).compareTo(strings[left] + strings[i]) <= 0 && i < j) i++;
            temp = strings[i];
            strings[i] = strings[j];
            strings[j] = temp;
        }
        strings[i] = strings[left];
        strings[left] = temp;
        quickSort(strings,left,i - 1);
        quickSort(strings,i + 1,right);
    }
}

方法二：使用JDK工具类排序

比较器Comparator的使用见博文【随手小记】_比较器Comparable和Comparator。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution1 {
    public String minNumber(int[] nums) {
        int n = nums.length;
        String[] strings = new String[n];
        for (int i = 0; i < n; i++) {
            strings[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strings, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(strings[i]);
        }
        return sb.toString();
    }
}

面试题46.把数字翻译成字符串

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1:

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

链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof

方法一：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int n = s.length();

        //状态与初始化：前i位的不同翻译的种数
        int dp1 = 1;
        if (n == 1) return dp1;
        int dp2 = 1;

        //要注意两位数中的00~09并不能翻译成字符串
        if (Integer.parseInt(s.substring(0,2)) <= 25 && Integer.parseInt(s.substring(0,2)) >= 10) dp2 = 2;

        int sum = dp2;
        //状态转移方程
        for (int i = 3; i <= n; i++) {
            if (Integer.parseInt(s.substring(i - 2,i)) <= 25 && Integer.parseInt(s.substring(i - 2,i)) >= 10) sum = dp1 + dp2;
            else sum = dp2;
            dp1 = dp2;
            dp2 = sum;
        }
        return sum;
    }
}

面试题47.礼物的最大价值

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1:

输入:

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

链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof

方法一：动态规划

这是一个路径问题，是一个很典型的动态规划问题，一般看到路径问题首先就要想到动态规划。

优化思路：反正原矩阵中的元素只需要在计算该格状态时使用一次，所以直接在原矩阵的格子中记录状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        //初始化
        for (int i = 1; i < m; i++) {
            grid[i][0] = grid[i - 1][0] + grid[i][0];
        }
        for (int i = 1;i < n;i++) {
            grid[0][i] = grid[0][i - 1] + grid[0][i];
        }

        //状态转移方程
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] = Math.max(grid[i - 1][j],grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[m - 1][n - 1];
    }
}

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

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

示例 1:

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

示例 2:

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

示例 3:

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

链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof

方法一：滑动窗口

巧思题，要硬记。

用左右指针组成一个滑动窗口，窗口中无重复字符则右指针右移，窗口中有重复字符则左指针右移，记录窗口的历史最大长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        Set<Character> set = new HashSet<>();
        int left = 0;
        for (int i = 0; i < n; i++) {
            char temp = s.charAt(i);
            while (set.contains(temp)) {
                set.remove(s.charAt(left));
                left++;
            }
            set.add(temp);
            ans = Math.max(ans,set.size());
        }
        return ans;
    }
}

面试题49.丑数

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例:

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

链接：https://leetcode-cn.com/problems/chou-shu-lcof

方法一：动态规划

巧思题，要硬记。这样用动态规划，这谁想得到啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int nthUglyNumber(int n) {
        int a = 0,b = 0,c = 0;

        //状态：dp[i]表示第i+1个丑数的值
        int[] dp = new int[n];

        //初始化
        dp[0] = 1;

        //状态转移方程
        for (int i = 1; i < n; i++) {

            //这个状态转移方程的过程非常精彩，整个过程就是每次把乘2、3、5的结果进行比较，
            //最小的放入队列中，另外两个待定，已经放入数组的再乘刚才那个值。
            //同时又通过索引能保证每个数都乘过2、3、5，都进行过比较，很妙，你让我自己想我绝对想不出来。
            int n2 = dp[a] * 2,n3 = dp[b] * 3,n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2,n3),n5);
            if (dp[i] == n2) a++;
            if (dp[i] == n3) b++;
            if (dp[i] == n5) c++;
        }

        return dp[n - 1];
    }
}

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例:

s = “abaccdeff”
返回 “b”

s = “”
返回 “ “

链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof

方法一：HashMap

巧思题，要硬记。

思路：遍历两遍，第一遍用来检查每个字符是否重复出现；第二遍用来拿出第一个不重复的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public char firstUniqChar(String s) {
        HashMap<Character,Integer> map = new HashMap<>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char temp = s.charAt(i);
            if (map.containsKey(temp)) {

                //重要：哈希表是去重的，存入已经存在的key时，会覆盖原键值对。
                map.put(temp,-1);
            }else map.put(temp,1);
        }

        //重要：哈希表中的键值对是无序的，所以无法直接遍历哈希表中的键值对，必须通过字符串来辅助遍历哈希表。
        for (int i = 0; i < n; i++) {
            if (map.get(s.charAt(i)) == 1) return s.charAt(i);
        }

        return ' ';
    }
}

总结

  • 哈希表是去重的，存入已经存在的key时，会覆盖原键值对。
  • 哈希表中的键值对是无序的，所以无法直接遍历哈希表中的键值对，必须通过其他数据来辅助遍历哈希表。

面试题51.数组中的逆序对

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1:

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

链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof

方法一：归并排序

巧思题，要硬记。这谁想得到啊！

该题的本质实际上是一个排序问题，六种比较排序中平均时间复杂度最小的就是归并和堆排序，而不借助工具类的就是归并排序了。

所以我们在归并排序的基础之上进行修改，计算逆序对数量。

时间复杂度：O(nlogn)（和归并排序相同）

空间复杂度：O(n)（和归并排序相同）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        if (n < 2) return 0;

        //归并排序需要一个与原数组等大的数组来辅助排序过程中的合并。
        int[] help = new int[n];

        return sort(nums,0,n - 1,help);
    }

    //归并排序方法，返回值为被排序的这段数组中的逆序对的个数。
    private int sort(int[] nums,int left,int right,int[] help) {
        if (left >= right) return 0;

        int mid = (left + right) / 2;

        //a为排序数组的前半段中逆序对个数，b为后半段中逆序对个数。
        int a = sort(nums,left,mid,help);
        int b = sort(nums,mid + 1,right,help);
        //count为前半段元素与后半段元素共同参与组成的逆序对的个数，也是本层递归排序方法中要扭转的逆序对个数。
        int count = 0;

        int m = left,n = mid + 1;

        //将已经排好序的left~mid和mid+1~right这两段数组合并，先用辅助数组保存原来的数值序列，然后谁小谁先加到原数组上去。
        //m索引表示left~mid段中的元素，n索引表示mid+1~right段中的元素
        for (int i = left; i <= right; i++) {
            help[i] = nums[i];
        }
        for (int i = left; i <= right; i++) {
            if (m > mid) {//left~mid段中的元素已经全部按顺序添加到原数组上去了的情况
                nums[i] = help[n];
                n++;
            }else if (n > right) {//mid+1~right段中的元素已经全部按顺序添加到原数组上去了的情况
                nums[i] = help[m];
                m++;
            }else if (help[m] <= help[n]) {
                nums[i] = help[m];
                m++;
            }else {
                nums[i] = help[n];
                n++;
                //只有在把后半段元素放到前半段元素之前的情况时，才会又逆序对被逆转。
                count = count + mid + 1 - m;
            }
        }
        return count + a + b;
    }
}

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

编写一个程序，找到两个单链表相交的起始节点。

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

链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

方法一：双指针

巧思题。

思路：两个指针分别从headA和headB出发，同速前进，任何一个指针走到链表尾部则跳转指向另一个链表头部，最后两指针会在第一个公共节点相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode a = headA,b = headB;
        int count = 0;
        while (a != b) {
            if (a.next == null) {
                count++;
                if (count == 2) return null;
                a = headB;
            }
            else a = a.next;
            if (b.next == null) b = headA;
            else b = b.next;
        }
        return a;
    }
}

面试题53_1.在排序数组中查找数字

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1:

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

示例 2:

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

链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof

方法一：二分查找

思路：其实这道题是相当于二分查找两个元素，起始点和终止点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return 0;
        int left = 0,right = n - 1;

        //找起始点
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
        }

        //数组中没有target值得情况
        if (target != nums[left]) return 0;

        int begin = left;

        left = 0;
        right = n - 1;
        //找终止点
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] > target) right = mid - 1;
            else left = mid;
        }
        return left - begin + 1;
    }
}

面试题53_2.前n个数中缺失的数字

tips：代码块中的注解、加粗、下划线部分为重点内容。

一个长度为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

链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof

方法一：二分查找

排序数组相关的查找问题，首先就是想到二分查找及其各种变式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;

        //缺失数字为第一个数字的特殊情况
        if (nums[0] != 0) return 0;

        //缺失数字为最后一个数字的特殊情况
        if (nums[n - 1] == n - 1) return n;

        int left = 0,right = n - 1;
        while (left < right - 1) {
            int mid = (left + right) / 2;
            if (nums[mid] > mid) right = mid;
            else left = mid;
        }
        return left + 1;
    }
}

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

给定一棵二叉搜索树，请找出其中第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

链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof

方法一：中序遍历

二叉堆是每个节点都比子节点大或者小的逻辑二叉树，实际优先队列；

二叉搜索数是每个节点的左子树都比该节点小，右子树都比该节点大的实际二叉树。

思路：先右后左的中序遍历所得第k个节点即为所求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

    int count;
    int ans;

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

    void inorderTraversal(TreeNode root,int k) {
        //已经找到第k大节点，递归中序遍历终止。
        if (k == count) return;

        if (root == null) return;
        inorderTraversal(root.right,k);

        if (k == count) return;
        count++;
        if (k == count) ans = root.val;
        inorderTraversal(root.left,k);
    }
}

总结

单词积累

  • preorderTraversal：前序遍历
  • inorderTraversal：中序遍历
  • postorderTraversal：后序遍历

面试题55_1.二叉树的深度

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

例如：

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

​ 3

/
9 20
/
15 7

返回它的最大深度 3 。

链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof

方法一：递归回溯法

前中后序遍历就是典型的DFS深度优先搜索，层序遍历就是典型的BFS广度优先搜索。

我简直要爱死递归题中的全局变量了，妈妈再也不用担心递归方法的输入参数太多太麻烦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {

    int depth,ans;

    public int maxDepth(TreeNode root) {
        traversal(root);
        return ans;
    }

    private void traversal(TreeNode root) {
        if (root == null) {
            ans = Math.max(ans,depth);
            return;
        }
        depth++;
        traversal(root.left);
        traversal(root.right);
        depth--;
    }
}

面试题55_2.平衡二叉树

tips：代码块中的注解、加粗、下划线部分为重点内容。

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过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 。

链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof

方法一：递归

如果刚做了面试题55_1来做这道题会觉得很简单，如果直接做该题可能需要一些时间来思考。

思路：使用递归，在每层递归方法中先判断每个节点的左右子树是不是平衡二叉树，

然后计算左右子树的深度差是否不大于1，其中计算树的深度又是另外一个递归方法。

时间复杂度：O(nlogn)：

这个时间复杂度的计算对于递归题复杂度计算非常有参考意义，要计算的是isBalanced()方法的复杂度，该方法中：

  • isBalanced()方法：递归最复杂的情况是每颗子树都平衡，则每层两个递归方法都要进入，总共向下logn层；
  • maxDepth()方法：递归最复杂的情况是每个节点只有一个子节点，每层只进入一个递归方法，总共向下n层。

这两个递归方法属于嵌套关系，所以最差时间复杂度即为O(nlogn)。

空间复杂度：O(n)：

不同递归方法嵌套时，空间复杂度取最差的递归方法的空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int gap = maxDepth(root.left,0) - maxDepth(root.right,0);
        return isBalanced(root.left) && isBalanced(root.right) && gap <= 1 && gap >= -1;
    }

    //计算一棵树的深度，depth参数表示该节点的父节点的深度。
    private int maxDepth(TreeNode root,int depth) {
        if (root == null) return depth;
        return Math.max(maxDepth(root.left,depth + 1),maxDepth(root.right,depth + 1));
    }
}

面试题56_1.数组中数字出现的次数

tips：代码块中的注解、加粗、下划线部分为重点内容。

一个整型数组 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]

链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof

方法一：位运算

本题是【力扣刷题】_136.只出现一次的数字的升级，也算是巧思题，要硬记。

思路：记这两个只出现了一次的数字为 a 和 b，那么所有数字异或的结果就等于 a 和 b 异或的结果，我们记为 x。如果我们把 x 写成二进制的形式 xk xk - 1 … x2 x1 x0，其中 xi不是0就是1。
那么如果我们把 a 和 b 写成二进制的形式，xi = 1就表示ai与bi不等；xi = 0就表示ai与bi相等。
假如我们任选一个不为 0 的 xi，按照第 i 位给原来的序列分组，如果该位为 0 就分到第一组，否则就分到第二组，分别将两组中的数组全部异或所得到的两个异或值即为两个只出现一次的数。
时间复杂度：O(n)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] singleNumbers(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = ans ^ nums[i];
        }

        //寻找a和b的异或和中从右往左第一个为1的位
        int temp = 1;
        while ((temp & ans) == 0) {

            //该位不为1则将temp中的1左移一位
            temp = temp << 1;
        }

        int a = 0,b = 0;
        for (int i = 0; i < n; i++) {
            if ((temp & nums[i]) == 0) {//该元素的该位为0
                a = a ^ nums[i];
            }else {//该元素的该位为1
                b = b ^ nums[i];
            }
        }

        return new int[]{a,b};
    }
}

面试题56_2.数组中数字出现的次数2

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1：

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

示例 2：

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

链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof

方法一：位运算

思路：考虑数字的二进制形式，对于出现三次的数字，各二进制位出现的次数都是 3 的倍数。因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。

总结：照这个思路来看，这个思路可以解决所有某个数字只出现一次，其他数字出现多次，要求寻找只出现一次的数字的问题。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution1 {
    public int singleNumber(int[] nums) {

        //创建一个容量为32的数组，用来记录数组nums所有数字各个对应二进制位中1出现的次数。
        int[] count = new int[32];

        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 32; j++) {
                count[j] = count[j] + (1 & nums[i]);
                nums[i] = nums[i] >>> 1;
            }
        }

        int ans = 0;
        for (int i = 31; i >= 0; i--) {
            ans <<= 1;
            ans |= (count[i] % 3);
        }
        return ans;
    }
}

面试题57.和为s的两个数字

tips：代码块中的注解、加粗、下划线部分为重点内容。

输入一个递增排序的数组和一个数字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]

链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof

方法一：双指针

思路：计算双指针的和，比target大则右指针左移；比target小则左指针右移。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        int left = 0,right = n - 1;
        while (left < right) {
            if (nums[left] + nums[right] == target) return new int[]{nums[left],nums[right]};
            if (nums[left] + nums[right] < target) left++;
            else right--;
        }
        return null;
    }
}

总结

提醒一下，判断条件最好不要用相加后的结果，应该用target - nums[i] 跟 nums[j]比较，这样保证不会溢出。同样的例子还有二分查找，(left + right) / 2 可以用left + (rigth - left) / 2 代替。

面试题57_2.和为s的连续正数序列

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

示例 1：

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

示例 2：

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

链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof

方法一：滑动窗口(双指针)

思路：使用连续整数和的计算公式：首项加末项乘以项数除以二。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int[][] findContinuousSequence(int target) {
        int left = 1,right = 2;
        List<int[]> ans = new ArrayList<>();
        while (left < right) {
            int sum = ((left + right) * (right - left + 1)) / 2;
            if (sum == target) {
                int[] answer = new int[right - left + 1];
                for (int i = 0; i < right - left + 1; i++) {
                    answer[i] = left + i;
                }
                ans.add(answer);

                //本题为求出所有可行的解，所以得到一种答案以后，任然要使窗口滑动。
                left++;

            }else if (sum < target) right++;
            else left++;
        }
        int size = ans.size();

        //重要：矩阵的每一行中的列数可以不同，所以在初始化矩阵时，可以先只初始化行数目。
        int[][] res = new int[size][];

        for (int i = 0; i < size; i++) {
            res[i] = ans.get(i);
        }
        return res;
    }
}

面试题58_1.翻转单词顺序

tips：代码块中的注解、加粗、下划线部分为重点内容。

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”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”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof

方法一：双指针

贼简单一道题，就用最直接想到的方法，从后往前一个个找到单词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String reverseWords(String s) {
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        int begin = n - 1,end = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) != ' ' && (i == n - 1 || s.charAt(i + 1) == ' ')) end = i + 1;
            if (s.charAt(i) != ' ' && (i == 0 || s.charAt(i - 1) == ' ')) {
                begin = i;
                String temp = s.substring(begin,end);
                sb.append(temp);
                sb.append(' ');
            }
        }
        if (sb.length() != 0) sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
}

面试题58_2.左旋转字符串

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1：

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

示例 2：

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

链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof

方法一：字符串切片

1
2
3
4
5
6
7
class Solution {
    public String reverseLeftWords(String s, int n) {
        String begin = s.substring(0,n);
        String end = s.substring(n,s.length());
        return end + begin;
    }
}

面试题59_1.滑动窗口的最大值

tips：代码块中的注解、加粗、下划线部分为重点内容。

给定一个数组 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

链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof

方法一：辅助队列

思想上和【剑指刷题】_面试题30.包含min函数的栈是一样的，借助一个辅助数据结构来保存滑动窗口在每个状态下的最大值。

辅助队列中只保存滑动窗口中从左到右依次最大的值。每次滑动窗口删除一个值时，先验证该值是不是辅助队列最左端的值，是则删除；滑动窗口添加元素时，检验新元素是否比辅助队列右端的值大，是则先将比新元素小的值都删除，然后加上新元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0 || k == 0) return new int[]{};
        Deque<Integer> queue = new LinkedList<>();
        int[] ans = new int[n - k + 1];
        for (int i = 0; i < k; i++) {
            while (!queue.isEmpty() && queue.peekLast() < nums[i]) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);
        }
        ans[0] = queue.peekFirst();

        for (int i = k; i < n; i++) {
            if (queue.peekFirst() == nums[i - k]) queue.removeFirst();
            while (!queue.isEmpty() && queue.peekLast() < nums[i]) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);
            ans[i - k + 1] = queue.peekFirst();
        }
        return ans;
    }
}

面试题59_2.队列的最大值

tips：代码块中的注解、加粗、下划线部分为重点内容。

请定义一个队列并实现函数 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]

链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof

方法一：辅助队列

思路与面试题59_1相同，只不过滑动窗口变成了队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MaxQueue {

    Queue<Integer> queue;
    Deque<Integer> helpQueue;

    public MaxQueue() {
        this.queue = new LinkedList<>();
        this.helpQueue = new LinkedList<>();
    }

    public int max_value() {
        if (queue.isEmpty()) return -1;
        return helpQueue.peekFirst();
    }

    public void push_back(int value) {
        queue.offer(value);
        while (!helpQueue.isEmpty() && helpQueue.peekLast() < value) {
            helpQueue.removeLast();
        }
        helpQueue.addLast(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) return -1;
        int ans = queue.poll();
        if (helpQueue.peekFirst() == ans) helpQueue.removeFirst();
        return ans;
    }
}

面试题60.n个骰子的点数

tips：代码块中的注解、加粗、下划线部分为重点内容。

把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]

链接：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof

方法一：动态规划

骰子数量为n时，可能的骰子点树分布情况有6^n种，点数和的可能值则为n~6n，返回数组的大小即为6n-n+1。

思路：注意此处动态规划的关键是，我们不是用概率值来作为状态，而是用出现种数来作为状态值。

状态转移方程：dp[n][j]= (6/∑/i=1) dp[n−1][j−i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public double[] dicesProbability(int n) {
        double[] ans = new double[5 * n + 1];

        //状态：dp[i][j]表示用n个骰子掷出点数和为j时，有多少种不同的骰子点数分布情况，要考虑每个骰子的编号不同。
        int[][] dp = new int[n + 1][];

        //初始化
        dp[1] = new int[7];
        for (int i = 1; i <= 6; i++) {
            dp[1][i] = 1;
        }

        //状态转移方程
        for (int i = 2; i < n + 1; i++) {
            dp[i] = new int[6 * i + 1];
            for (int j = i; j <= 6 * n; j++) {
                for (int k = 1; k <= 6; k++) {

                    //这里要限定好i-1个骰子能掷出的点数和的范围
                    if (j - k >= i - 1 && j - k <= 6 * i - 6) dp[i][j] = dp[i][j] + dp[i - 1][j - k];
                }
            }

        }

        //求出总种数6^n
        double sum = 1;
        for (int i = 0; i < n; i++) {
            sum *= 6;
        }

        for (int i = 0; i < 5 * n + 1; i++) {
            ans[i] = dp[n][i + n] / sum;
        }

        return ans;
    }
}

面试题61.扑克牌中的顺子

tips：代码块中的注解、加粗、下划线部分为重点内容。

从扑克牌中随机抽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

链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof

方法一：排序+遍历

巧思题，要硬记。

思路，不要从正面找，从反面找不是顺子的情况，那么反面主要有两类：有重复数字、最大值-最小值>=5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);

        //joker用于记录大小王的个数
        int joker = 0;

        //找出大小王个数，并判断有无重复数字
        for (int i = 0; i < 5; i++) {
            if (nums[i] == 0) {
                joker = i + 1;
                continue;
            }
            if (i + 1 < 5 && nums[i] == nums[i + 1]) return false;
        }

        if (joker == 5) return true;

        //无重复数字的情况下，最大值减最小值必须小于5才是顺子。
        return nums[4] - nums[joker] < 5;
    }
}

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

方法一：递归

好家伙这不是典型的约瑟夫环问题吗？巧思题，要硬记。

n个数字从0位置开始每m个数字删除一个数字：这个过程，在删除了第一个数字(m-1)%n之后，就相当于n-1个数字从(m-1)%n位置开始每m个数字删除一个数字。

那么n-1个数字从(m-1)%n位置开始每m个数字删除一个数字，n-1个数字从0位置开始每m个数字删除一个数字，这两个过程的关系其实就是起点相差(m-1)%n,步长相同，那么最后留下的这个数字的位置索引也就是相差(m-1)%n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int lastRemaining(int n, int m) {

        //递归终止条件
        if (n == 1) return 0;

        int x = lastRemaining(n - 1,m);

        //index为最后留下的数字在删除了m%n位置的数字之后的n-1个数字中的位置索引。
        int index = ((m - 1) % n + x) % (n - 1);
        if (index < (m - 1) % n) return index;
        else return index + 1;
    }
}

面试题63.股票的最大利润

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

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

链接：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof

方法一：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        int ans = 0;

        //状态与初始化：dp[i]表示第i天卖出所能收获的最大利润
        int dp = 0;

        //状态转移方程
        for (int i = 1; i < n; i++) {
            dp = Math.max(dp + prices[i] - prices[i - 1],0);
            ans = Math.max(ans,dp);
        }

        return ans;
    }
}

面试题64.求前n个正整数之和

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

链接：https://leetcode-cn.com/problems/qiu-12n-lcof

方法一：递归

1
2
3
4
5
6
class Solution {
    public int sumNums(int n) {
        if (n == 1) return 1;
        return sumNums(n - 1) + n;
    }
}

方法二：位运算

这个方法又叫俄罗斯农民乘法，一种不使用*，而使用位运算的乘法。

思路：考虑 A 和 B 两数相乘的时候我们如何利用加法和位运算来模拟，其实就是将 B 二进制展开，如果 B 的二进制表示下第 i 位为 1，那么这一位对最后结果的贡献就是 A*(1<<i) ，即 A<<i。我们遍历 B 二进制展开下的每一位，将所有贡献累加起来就是最后的答案。

因为题目数据范围 n 为 [1,10000]，所以 n 二进制展开最多不会超过 14 位，我们手动展开 14 层代替循环即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution1 {
    public int sumNums(int n) {
        int ans = 0, A = n, B = n + 1;
        boolean flag;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        flag = ((B & 1) > 0) && (ans += A) > 0;
        A <<= 1;
        B >>= 1;

        return ans >> 1;
    }
}

面试题65.不用加减乘除做加法

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

示例:

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

链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof

方法一：位运算

巧思题，要硬记。

在计算机系统中，数值一律用补码来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。也就是说计算机已经帮我们做好了负数的补码操作，我们在进行位运算时不用考虑什么正负数、最高位，直接每一位平等对待就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int add(int a, int b) {
        while (b != 0) {

            //可以自己列表查看四种情况，0&0=0、0&1=0、1&0=0、1&1=1，
            //可以看出两个数的对应位进行与运算的结果其实就是它们相加后是否进位的结果，
            //所以我们将该结果左移一位其实就是相加后的进位值。
            int c = (a & b) << 1;

            //可以自己列表查看四种情况，0^0=0、0^1=1、1^0=1、1^1=0，
            //可以看出两个数的对应位进行异或运算的结果其实就是它们相加后，不考虑进位时，本位的结果。
            a = a ^ b;

            //将进位结果赋值给b，在下一次循环中将进位值与不进位结果相加。
            b = c;
        }
        return a;
    }
}

面试题66.构建乘积数组

tips：代码块中的注解、加粗、下划线部分为重点内容。

给定一个数组 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]

链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof

方法一：动态规划

巧思题，要硬记。

思路：结果数组中每个元素=左边所有元素的乘积*右边所有元素的乘积，第一次遍历求出每个元素对应的左边所有元素乘积，第二次遍历再乘上每个元素对应右边所有元素乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] constructArr(int[] a) {
        int n = a.length;
        int[] ans = new int[n];
        if (n == 0) return ans;

        //第一次遍历
        ans[0] = 1;
        for (int i = 1; i < n; i++) {
            ans[i] = ans[i - 1] * a[i - 1];
        }

        //第二次遍历
        int right = 1;
        for (int i = n - 2; i >= 0; i--) {
            right = right * a[i + 1];
            ans[i] = ans[i] * right;
        }

        return ans;
    }
}

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

tips：代码块中的注解、加粗、下划线部分为重点内容。

写一个函数 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) 。

链接：https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof

方法一：大数字符串转换成整数

int类型数值范围为 [−231, 231 − 1]。

本题的关键难点是将超过int边界甚至是long边界的大数转换为int类型数值，采用将每一位从左往右一个一个加上的方式，这样也有利于设定到达int边界条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int strToInt(String str) {
        int n = str.length();
        if (n == 0) return 0;

        //找到第一个不为' '的字符的位置
        int begin = 0;
        while (str.charAt(begin) == ' ') {
            begin++;
            if (begin == n) return 0;
        }

        int flag = 1;
        if (str.charAt(begin) == '+') {
            begin++;
        }else if (str.charAt(begin) == '-') {
            flag = -1;
            begin ++;
        }

        int ans = 0;
        for (int i = begin; i < n; i++) {
            if (str.charAt(i) < '0' || str.charAt(i) > '9') break;
            
            //ans接下来将要越界的两种情况。
            if (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && str.charAt(i) > '7')) {
                return flag == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            ans = ans * 10 + (str.charAt(i) - '0');
        }

        return flag * ans;
    }
}

面试题68_1.二叉搜索树的最近公共祖先

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

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

示例 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, 因为根据定义最近公共祖先节点可以为节点本身。

链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof

方法一：递归

沿着根节点往下走，直到给定的两个节点，一个是该根节点的子节点、一个不是，则该根节点的父节点即为最近公共祖先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;

        while (true) {
            if (isSon(root.left,p) && isSon(root.left,q)) root = root.left;
            else if (isSon(root.right,p) && isSon(root.right,q)) root = root.right;
            else break;
        }
        return root;
    }

    //判断节点node是不是root节点的子孙
    private boolean isSon(TreeNode root,TreeNode node) {
        if (root == null) return false;
        if (root == node) return true;
        return isSon(root.left,node) || isSon(root.right,node);
    }
}

方法二：递归

我自己写的方法一并没有用到二叉搜索树的特性，方法二中用到了，可以极大降低空间复杂度和时间复杂度。

二叉搜索树的特性是左子树全部小于根节点，右子树全部大于根节点。

1
2
3
4
5
6
7
class Solution1 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right,p,q);
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left,p,q);
        return root;
    }
}

面试题68_2.二叉树的最近公共祖先

tips：代码块中的注解、加粗、下划线部分为重点内容。

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

百度百科中最近公共祖先的定义为：“对于有根树 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。因为根据定义最近公共祖先节点可以为节点本身。

链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;

        while (true) {
            if (isSon(root.left,p) && isSon(root.left,q)) root = root.left;
            else if (isSon(root.right,p) && isSon(root.right,q)) root = root.right;
            else break;
        }
        return root;
    }

    //判断节点node是不是root节点的子孙
    private boolean isSon(TreeNode root,TreeNode node) {
        if (root == null) return false;
        if (root == node) return true;
        return isSon(root.left,node) || isSon(root.right,node);
    }
}