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

找出数组中重复的数字。

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

示例 1：

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

限制：

1
2 <= n <= 100000

解法一：利用哈希表

解法二：原地交换

原地交换注意，i什么时候增加，一定是在nums[i] == i之后才会往后走。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length){
            if(nums[i] == i){
                i++;
                continue;
            }
            if(nums[i] == nums[nums[i]] )return nums[i];
            swap(nums , nums[i] , i );
        }
        return -1;
    }

    public void swap(int[] nums , int x , int y){
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}

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

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

示例:

现有矩阵 matrix 如下：

1
2
3
4
5
6
7
[
  [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。

限制：

1
2
0 <= n <= 1000
0 <= m <= 1000

解法一：暴力求解

解法二：线性查找法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int row = 0, column = columns - 1;
        while (row < rows && column >= 0) {
            int num = matrix[row][column];
            if (num == target) {
                return true;
            } else if (num > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }
}

剑指 Offer 05. 替换空格

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

示例 1：

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

限制：

1
0 <= s 的长度 <= 10000

方法一：Java内置函数

1
return s.replace(" ","%20");

方法二：遍历替换

1
2
3
4
5
6
7
8
9
10
class Solution {
    public String replaceSpace(String s) {
        StringBuffer buffer = new StringBuffer();
        for(int i = 0 ; i < s.length() ; i++){
            if(s.charAt(i) == ' ')buffer.append("%20");
            else buffer.append(s.charAt(i)); 
        }
        return buffer.toString();
    }
}

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

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

示例 1：

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

限制：

1
0 <= 链表长度 <= 10000

方法一：借助辅助栈 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while(head != null){
            stack.push(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        int i = 0;
        while(!stack.isEmpty()){
            res[i++] = stack.pop();
        }
        return res;
    }
}

方法二：两次遍历

主要是不知道链表长度，其实我们可以先遍历一次链表，找到长度，给数组倒序赋值。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        int count = 0;
        ListNode node = head;
        while(node != null){
            node = node.next;
            count++;
        }
        int[] res = new int[count];
        node = head;
        for(int i = 0 ; i < count ; i++){
            res[count - i - 1] = head.val;
            head = head.next;
        }
        return res;
    }
}

剑指 Offer 07. 重建二叉树

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

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

示例 1:

img

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

示例 2:

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

限制：

1
0 <= 节点个数 <= 5000

方法一：递归

该方法思路利用前序遍历 和 中序遍历的特性

1
2
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

一层一层往下找。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private Map<Integer , Integer> indexMap;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        indexMap = new HashMap<>();
        int len = preorder.length;
        for(int i = 0 ; i < len ; i++){
            indexMap.put(inorder[i] , i);
        }

        return recur(preorder, inorder, 0,  len-1, 0, len-1);

    }

    public TreeNode recur(int[] preorder, int[] inorder , int pl , int pr , int il , int ir){
        if(pl > pr || il > ir)return null;
        int k = indexMap.get(preorder[pl]) - il;

        TreeNode root = new TreeNode(preorder[pl]);
        root.left = recur(preorder, inorder, pl+1,  pl+k, il, il+k-1);
        root.right = recur(preorder, inorder, pl+k+1,  pr, il+k+1, ir);
        return root;
    
    }
}

方法二：迭代

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路：

两个栈，栈1入栈，栈2作为队列末尾删除，如果栈2空了，让栈1再给栈2点元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class CQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        stack1.add(value);
    }
    
    public int deleteHead() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.isEmpty() ? -1 : stack2.pop();
    }
}

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

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

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

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

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

示例 1：

1
2
输入：n = 2
输出：1

示例 2：

1
2
输入：n = 5
输出：5

提示：

  • 0 <= n <= 100

方法一：动态规划

解题思路

简单的动态规划，递归方程也给了,这里直接给到省略空间的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int fib(int n) {
        int MOD = 1000000007;
        if(n < 2)return n;
        int pre = 0 , cur = 1;
        for(int i = 2 ; i <= n ; i++){
            int temp = (pre + cur)%MOD;
            pre = cur;
            cur = temp;
        }
        return cur;
    }
}

方法二：矩阵快速幂

image-20220810195627400

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
class Solution {
    static final int MOD = 1000000007;
    public int fib(int n) {
        
        if(n < 2)return n;

        int[][] m = {{1,1},{1,0}};
        int[][] res = pow(m , n-1);
        return res[0][0];
    }


    public int[][] pow(int[][] m , int n){
        int[][] ret = {{1,0},{0,1}};

        while(n > 0){
            if( (n & 1) == 1){
                ret = multiply( ret , m);
            }
            n >>= 1;
            m = multiply(m , m);
        }
        return ret;
    }

    public int[][] multiply(int[][] a , int[][] b){

        int[][] c = new int[2][2];
        for(int i = 0 ; i < 2 ; i++){
            for(int j = 0 ; j < 2 ; j++){
                c[i][j] = (int) (( (long)a[i][0]*b[0][j] + (long)a[i][1]*b[1][j])%MOD );
            }
        }
        return c;
    }
}

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

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

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

示例 1：

1
2
输入：n = 2
输出：2

示例 2：

1
2
输入：n = 7
输出：21

示例 3：

1
2
输入：n = 0
输出：1

提示：

  • 0 <= n <= 100

方法一：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    static final int MOD = 1000000007;
    public int numWays(int n) {
        int pre = 1 , cur = 1;
        for(int i = 2 ; i <= n ; i++){
            int temp = (pre + cur)%MOD;
            pre = cur;
            cur = temp;
        }
        return cur;
    }
}

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

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

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

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

示例 1：

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

示例 2：

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

提示：

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

方法一：二分解法

注意，有点坑的是，他说 n 大于1 ，有可能是，旋转过头， 比如 1 2 3 ，旋转三次 还是 1 2 3，这个时候他的旋转点就是1，所以不能单纯判断mid大于nums[0]

我们看num[right]分为大于mid , 小于mid ，

大于mid：比如 1 2 3 ， 31 2 34 ， 所以旋转点在左边，就需要往左找， 比如找到1 ，还是小于右边，这个时候能right = mid - 1 吗？ 显然不能 所以 right = mid

小于mid ： 2 4 1 ,这种情况，旋转点一定在右边，就可以直接往右找， 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minArray(int[] numbers) {
        int left = 0 , right = numbers.length - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(numbers[mid] < numbers[right])right = mid;
            else if(numbers[mid] > numbers[right])left = mid + 1;
            else right--;
        }
        return numbers[left];
    }
}

剑指 Offer 12. 矩阵中的路径

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

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

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

img

示例 1：

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

1
2
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和word仅由大小写英文字母组成
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 exist(char[][] board, String word) {
        char[] wordarry = word.toCharArray();
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
               if( cur(board,wordarry,i,j,0))return true;
            }
        }
        return false;
	}

    boolean cur(char[][] board,char[] wordarry,int i,int j,int k){
        if(i<0||i>=board.length||j<0||j>=board[0].length||board[i][j]!=wordarry[k])return false;
        if(k == wordarry.length - 1)return true;
        
        board[i][j] = '\0';
        //注意不能直接k++，后边要把该位置还原
        boolean res = cur(board,wordarry,i+1,j,k+1)||cur(board,wordarry,i,j+1,k+1)||cur(board,wordarry,i-1,j,k+1)||cur(board,wordarry,i,j-1,k+1);
        board[i][j] = wordarry[k];
        return res;       
    }
}

剑指 Offer 14- I. 剪绳子

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

示例 1：

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

示例 2:

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

提示：

  • 2 <= n <= 58

方法一：贪心

怎样乘积最大，3越多越好，有余数的时候，就要考虑一下，余数是1，就去掉一个3换成4 ， 余数是2 就直接×2

1
2
3
4
5
6
7
8
9
10

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if(b == 0) return (int)Math.pow(3, a);
        if(b == 1) return (int)Math.pow(3, a - 1) * 4;
        return (int)Math.pow(3, a) * 2;
    }
}

方法二：动态规划

dp的含义：

dp[i]代表以i截至，最大乘积

dp的推导：

第一种： dp[i]可分成两段，以下标j遍历，从j分两段相乘。

第二种： dp[i] 可能由很多段，以下标j遍历，dp[j]代表前j前边相乘的最大值，然后乘以后边一段

取两种最大值

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 cuttingRope(int n) {
        /*
        dp五部曲:
        1.状态定义:dp[i]为长度为i的绳子剪成m段最大乘积为dp[i]
        2.状态转移:dp[i]有两种途径可以转移得到
            2.1 由前一个dp[j]*(i-j)得到,即前面剪了>=2段,后面再剪一段,此时的乘积个数>=3个
            2.2 前面单独成一段,后面剩下的单独成一段,乘积为j*(i-j),乘积个数为2
            两种情况中取大的值作为dp[i]的值,同时应该遍历所有j,j∈[1,i-1],取最大值
        3.初始化:初始化dp[1]=1即可
        4.遍历顺序:显然为正序遍历
        5.返回坐标:返回dp[n]
        */
        // 定义dp数组
        int[] dp = new int[n + 1];
        // 初始化
        dp[1] = 1;  // 指长度为1的单独乘积为1
        // 遍历[2,n]的每个状态
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j <= i - 1; j++) {
                // 求出两种转移情况(乘积个数为2和2以上)的最大值
                int tmp = Math.max(dp[j] * (i - j), j * (i - j));
                dp[i] = Math.max(tmp, dp[i]);
            }
        }
        return dp[n];
    }
}

剑指 Offer 14- II. 剪绳子 II

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

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

示例 1：

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

示例 2:

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

提示：

  • 2 <= n <= 1000

为什么不能用动态规划

尝试在动态规划的基础上取余，就算把数据类型都换成long也是无解的，对每次的dp[i]取余确实可以避免溢出的问题，但是由于过程中修改了值，会导致最终结果和预期不同。比如
这一步：
dp[i] = Math.max(dp[i] ，x * y );
x * y = 1000000005 ，若dp[i] 本该等于 1000000008 ，但是经过上次取余后变成了1，本来的结果应该是1000000008 ，现在却变成了1000000005，所以在动态规划过程中是不能取余的，那么就只能使用BigInter存储中间结果了

方法一：贪心 + 循环取余

利用快速幂

利用 剑指 Offer 14- I. 剪绳子 的结论，3 越多越好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    static final int MOD = 1000000007;
    public int cuttingRope(int n) {
        if(n <= 3)return n-1;

        int a = n/3 - 1 , b = n%3;
        long res = 1 , x = 3;
        
        while(a > 0){
            if( (a & 1) == 1)res = res * x % MOD;
            a >>= 1;
            x = x * x % MOD ;
        }
        if(b == 0)return (int)(res * 3 % MOD);
        if(b == 1)return (int)(res * 4 % MOD);
        return (int)(res * 6 % MOD);
    }
}

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

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

提示：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

这里考察的负数在计算机中存储方式

比如：

1
2
3
System.out.println(5>>3);//结果是0  
System.out.println(-5>>3);//结果是-1  
System.out.println(-5>>>3);//结果是536870911

5换算成二进制： 0000 0000 0000 0000 0000 0000 0000 0101

5右移3位后结果为0，0的二进制为： 0000 0000 0000 0000 0000 0000 0000 0000 // (用0进行补位)

-5换算成二进制： 1111 1111 1111 1111 1111 1111 1111 1011

-5右移3位后结果为-1，-1的二进制为： 1111 1111 1111 1111 1111 1111 1111 1111 // (用1进行补位)

-5无符号右移3位后的结果 536870911 换算成二进制：0001 1111 1111 1111 1111 1111 1111 1111 // (用0进行补位)

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 >>>= 1;
        }
        return count;
    }
}

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • -104 <= xn <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public double myPow(double x, int n) {
        long absN = n >= 0 ? n : -n ;
        double res = 1;
        while(absN != 0){
            if( (absN & 1) == 1) res = res * x;
            absN >>>= 1;
            x = x * x;
        }
        if(n > 0)return res;
        return 1.0/res;      
    }
}

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

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

示例 1:

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

说明：

  • 用返回一个整数列表来代替打印
  • n 为正整数
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[] printNumbers(int n) {
        if( n == 0)return new int[0];
        int count = (int)Math.pow(10,n);
        int[] res = new int[count-1];
        for(int i = 0 ; i < count-1 ; i++){
            res[i] = i+1;
        } 
        return res;
    }
}

大数打印解法：

实际上，本题的主要考点是大数越界情况下的打印。需要解决以下三个问题：

  1. 表示大数的变量类型：
    无论是 short / int / long … 任意变量类型，数字的取值范围都是有限的。因此，大数的表示应用字符串 String 类型。
  2. 生成数字的字符串集：
    使用 int 类型时，每轮可通过 +1+1 生成下个数字，而此方法无法应用至 String 类型。并且， String 类型的数字的进位操作效率较低，例如 “9999” 至 “10000” 需要从个位到千位循环判断，进位 4 次。

观察可知，生成的列表实际上是 nn 位 00 - 99 的 全排列 ，因此可避开进位操作，通过递归生成数字的 String 列表。

  1. 递归生成全排列：
    基于分治算法的思想，先固定高位，向低位递归，当个位已被固定时，添加数字的字符串。例如当 n=2 时（数字范围 1−99 ），固定十位为 0 - 9， 按顺序依次开启递归，固定个位 0 - 9 ，终止递归并添加数字字符串。

但是这个程序没有删除前导0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    static final char[] loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public String printNumbers(int n) {
        StringBuffer buffer = new StringBuffer();
        int[] num = new int[10];
        dfs(num , buffer , n , 0);
        buffer.deleteCharAt(buffer.length() - 1);
        return buffer.toString(); 

    }
    public void dfs(char[] num , StringBuffer buffer , int n , int index ) {
        if(index == n){
            int start = num.length-1;
            while(start>=0 && num[start--] != '0')break;
            buffer.append(String.valueOf(num).substring(num.length - start + 1); + ",");
            return;
        }
        for(char i : loop){
            num[index] = i;
            dfs(num , buffer , n , index+1);
        }
    }
}

去除前导0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    static final char[] loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public String printNumbers(int n) {
        StringBuffer buffer = new StringBuffer();
        int[] num = new int[10];
        dfs(num , buffer , n , 0);
        buffer.deleteCharAt(buffer.length() - 1);
        return buffer.toString(); 

    }
    public void dfs(char[] num , StringBuffer buffer , int n , int index ) {
        if(index == n){
            int start = 0;
            while(start < n-1 && num[start] == '0')start++;
            buffer.append(  String.valueOf(num).substring( start )  +  "," );
            return;
        }
        for(char i : loop){
            num[index] = i;
            dfs(num , buffer , n , index+1);
        }
    }
}

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

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

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

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

示例 1:

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

示例 2:

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

方法一：单指针直接查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode node = head;
        if(node.val == val)return node.next;
        while(node.next != null && node.next.val != val){
            node = node.next;
        }
        node.next = node.next.next;
        return head;
    }
}

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

1
2
3
4
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

动态规划解法：

这个题比较难，关键在于动态规划的递推转换。

我们用 f[i][j]表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配。在进行状态转移时，我们考虑 p 的第 j 个字符的匹配情况：

如果 p 的第 j个字符是一个小写字母，那么我们必须在 s 中匹配一个相同的小写字母，即

image-20220725150214841

如果 p的第 j个字符是 *，那么就表示我们可以对 p 的第 j-1 个字符匹配任意自然数次。在匹配 0 次的情况下，我们有

image-20220725150257196

也就是我们「浪费」了一个字符 + 星号的组合，没有匹配任何 s 中的字符。

在匹配 1,2,3,⋯ 次的情况下，类似地我们有

image-20220725150326368

如果我们通过这种方法进行转移，那么我们就需要枚举这个组合到底匹配了 s 中的几个字符，会增导致时间复杂度增加，并且代码编写起来十分麻烦。我们不妨换个角度考虑这个问题：字母 + 星号的组合在匹配的过程中，本质上只会有两种情况：

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

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

如果按照这个角度进行思考，我们可以写出很精巧的状态转移方程：

image-20220725150426447

这回到了动态规划五部曲：

确定了dp含义和推导顺序，接下来就是如何初始化，如何遍历。

方便起见，我们从1开始，所以字符串前边加入空格。

遍历顺序，从前往后，层层遍历，

初始化，f[0][0] = true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        s = " " + s;
        p = " " + p;
        
        for(int i = 0 ; i <= m ; i++){
            for(int j = 1 ; j <= n ; j++){
                if(j < n && p.charAt(j+1) == '*')continue;
                if(p.charAt(j) != '*'){
                    dp[i][j] = i > 0 && dp[i-1][j-1] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                }else{
                    dp[i][j] = (j >=2 && dp[i][j-2]) || (i >=1 && dp[i-1][j] && (s.charAt(i) == p.charAt(j-1) || p.charAt(j-1) == '.'));
                }
            }
        }
        return dp[m][n];
    }
}

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

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

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

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

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

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

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

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

部分数值列举如下：

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

部分非数值列举如下：

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

Picture1.png

状态机

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 boolean isNumber(String s) {
        Map[] states = {
            new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
            new HashMap<>() {{ put('d', 2); put('.', 4); }},                           // 1.
            new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
            new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
            new HashMap<>() {{ put('d', 3); }},                                        // 4.
            new HashMap<>() {{ put('s', 6); put('d', 7); }},                           // 5.
            new HashMap<>() {{ put('d', 7); }},                                        // 6.
            new HashMap<>() {{ put('d', 7); put(' ', 8); }},                           // 7.
            new HashMap<>() {{ put(' ', 8); }}                                         // 8.
        };
        int p = 0;
        char t;
        for(char c : s.toCharArray()) {
            if(c >= '0' && c <= '9') t = 'd';
            else if(c == '+' || c == '-') t = 's';
            else if(c == 'e' || c == 'E') t = 'e';
            else if(c == '.' || c == ' ') t = c;
            else t = '?';
            if(!states[p].containsKey(t)) return false;
            p = (int)states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}

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

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

示例：

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

提示：

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

方法一：双指针判断

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

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

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

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

示例：

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

返回链表 4->5.

方法一：两次遍历

方法二：快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head , slow = head;
        while(k-- > 0)fast = fast.next;
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

剑指 Offer 24. 反转链表

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

示例:

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

限制：

1
0 <= 节点个数 <= 5000

方法一：顺序反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null , cur = head;
        while(cur != null){
            ListNode tempNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tempNext;
        }
        return pre;
    }
}

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

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

示例1：

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

限制：

1
0 <= 链表长度 <= 1000
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        ListNode node = res;
        while(l1 != null && l2 != null){
            if(l1.val > l2.val){
                node.next = l2;
                l2 = l2.next;
            }else{
                node.next = l1;
                l1 = l1.next;
            } 
            node = node.next;
        }
        if(l1 != null)node.next = l1;
        if(l2 != null)node.next = l2;
        return res.next;
    }
}

剑指 Offer 26. 树的子结构

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

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

例如:
给定的树 A:

3 / \ 4 5 / \ 1 2
给定的树 B：

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

示例 1：

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

示例 2：

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

限制：

1
0 <= 节点个数 <= 10000

方法一：递归

B是A的子树，就是有可能A的某一个子节点开始，是B的子树，所以我们需要递归找所有的A子树，看一看每一个子树，是不是B。

递归确定子树的根节点后，就要开始递归判断 以该子节点的A ，是否能够包含B，直到找完A所有的子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return  A != null && B != null && ( recur(A , B) || isSubStructure(A.left , B) || isSubStructure(A.right , B) );
    }
    public boolean recur(TreeNode A, TreeNode B){
        if(B == null )return true;
        if(A == null || A.val != B.val )return false;
        return recur(A.left , B.left ) && recur(A.right , B.right);
    }
}

剑指 Offer 27. 二叉树的镜像

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

例如输入：

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

1
4  /  \ 7   2 / \  / \9  6 3  1

示例 1：

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

限制：

1
0 <= 节点个数 <= 1000

方法一：递归

注意，递归过程不要把值改了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null)return null;

        //这里拿了临时存储，不然left改变之后递归进去了就
        TreeNode leftNode = mirrorTree(root.right);
        TreeNode rightNode = mirrorTree(root.left);

        root.left = leftNode;
        root.right = rightNode;
        return root;
    }
}

方法二：辅助栈

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null)return null;
        Stack<TreeNode> stack = new Stack<>();

        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.left != null)stack.push(node.left);
            if(node.right != null)stack.push(node.right);
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
        return root;
    }
}

剑指 Offer 28. 对称的二叉树

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

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

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

1
1  / \ 2  2  \  \  3   3

示例 1：

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

示例 2：

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

限制：

1
0 <= 节点个数 <= 1000

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null)return true;
        return recur(root.left , root.right);
    }


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

方法二：迭代

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(root);

        while(!queue.isEmpty()){
            TreeNode p = queue.poll();
            TreeNode q = queue.poll();

            if(p == null && q == null)continue;


            if(p == null || q == null || p.val != q.val)return false;

            queue.add(p.left);
            queue.add(q.right);

            queue.add(p.right);
            queue.add(q.left);
        }

        return true;
    }
}

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

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

示例:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示：

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

方法一：辅助栈

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
class MinStack {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
        if(stack2.isEmpty() || x <= stack2.peek())stack2.push(x);
    }
    //注意Integer超过127不能==比较。要用equals
    public void pop() {
        if(stack1.peek().equals(stack2.peek()))stack2.pop();
        stack1.pop();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        return stack2.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

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

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

示例 1：

1
2
3
4
5
输入：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：

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

提示：

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

方法一：模拟解法

利用栈，往栈中压入元素，遇到出栈数组相等的数，出栈，下标增加。直到遍历完入栈数组，看最后栈是否出完。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();

        int i = 0;
        for(int x : pushed){
            stack.push(x);
            while(!stack.isEmpty() && stack.peek() == popped[i]){
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

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

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

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

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回：

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

提示：

  1. 节点总数 <= 1000
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null)return new int[0];
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();

        queue.add(root);

        while(!queue.isEmpty()){
            int len = queue.size();
            for(int i = 0 ; i < len ; i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null)queue.add(node.left);
                if(node.right != null)queue.add(node.right);
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

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

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

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

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回其层次遍历结果：

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]

提示：

  1. 节点总数 <= 1000
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null)return res;
        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);

        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i = 0 ; i < len ; i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null)queue.add(node.left);
                if(node.right != null)queue.add(node.right);
            }
            res.add(list);
        }
        return res;
    }
}

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

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

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

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回其层次遍历结果：

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

方法一：BFS

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null)return res;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int len = queue.size();
            for(int i = 0 ; i < len ; i++){
                if( (res.size() & 1) == 0){
                    TreeNode node = queue.removeFirst();
                    list.add(node.val);
                    if(node.left != null)queue.addLast(node.left);
                    if(node.right != null)queue.addLast(node.right);
                }else{
                    TreeNode node = queue.removeLast();
                    list.add(node.val);
                    if(node.right != null)queue.addFirst(node.right);
                    if(node.left != null)queue.addFirst(node.left);
                }  
            }
            res.add(list);
        }
        return res;
    }
}

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

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

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

1
2
3
4
5
    5
   / \
  2   6
 / \
1   3

示例 1：

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

示例 2：

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

提示：

  1. 数组长度 <= 1000

方法一：递归

后续遍历，就是左右根，就按照数字来分割，首先，最右边肯定是根，第一个大于根的数开始就是右节点了，左边就是左节点，按照这个规则递归。

要求，左边都要小于节点吗，右边都要大于根节点，遍历玩必须个数够根节点的左右总数，不然就不是二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder , 0 , postorder.length - 1);
    }

    public boolean recur(int[] arr , int left, int right){
        if(left >= right)return true;
        int i = left;
        while(arr[i] < arr[right])i++;
        int mid = i;
        while(arr[i] > arr[right])i++;
        return i == right && recur(arr , left , mid - 1) && recur(arr , mid , right - 1);
    }
}

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

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

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

示例 1：

img

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

示例 2：

img

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

示例 3：

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

提示：

  • 树中节点总数在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000
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>> pathSum(TreeNode root, int target) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        dfs(res , path , root , target , 0);
        return res;
    }

    public void dfs(List<List<Integer>> res , LinkedList<Integer> path ,TreeNode root , int target , int sum){
        if(root == null)return;
        sum += root.val;
        path.add(root.val);
        if(target == sum && root.left == null && root.right == null){
            res.add(new ArrayList<Integer>(path));
        }
        dfs(res , path , root.left , target , sum);
        dfs(res , path , root.right , target , sum);
        path.removeLast();
    }
}

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

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

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

示例 1：

img

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

示例 2：

img

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

示例 3：

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

提示：

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

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

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

示例 1：

img

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

示例 2：

img

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

示例 3：

img

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

示例 4：

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

提示：

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

方法一：拼接+拆分

两次遍历，第二次把random修改同时拆分，但是会破坏原链表，会报错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public Node copyRandomList(Node head) {
        Node node = head;
        while(node != null){
            Node TempNodeNext = node.next;
            Node newNode = new Node(node.val);
            node.next = newNode;
            newNode.next = TempNodeNext;
            node = TempNodeNext;
        }
        node = head;
        Node res = node.next;
        while(node!=null){
            Node tempNodeNext = node.next.next;
            node.next.random = node.random == null ? null : node.random.next;
            node.next.next = tempNodeNext == null ? null : tempNodeNext.next;
            node = tempNodeNext;
        }
        return res;
    }
}

只好进行三次遍历

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
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null)return null;
        Node node = head;
        while(node != null){
            Node TempNodeNext = node.next;
            Node newNode = new Node(node.val);
            node.next = newNode;
            newNode.next = TempNodeNext;
            node = TempNodeNext;
        }
        node = head;
        while(node != null){
            node.next.random = node.random == null ? null : node.random.next;
            node = node.next.next;
        }
        node = head;
        Node res = node.next;
        while(node!=null){
            Node tempNodeNext = node.next.next;
            node.next.next = tempNodeNext == null ? null : tempNodeNext.next;
            node.next = tempNodeNext;
            node = tempNodeNext;
        }
        return res;
    }
}

方法二：回溯+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    HashMap<Node, Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        if(head == null)return head;

        if(!map.containsKey(head)){
            Node newNode = new Node(head.val);
            map.put(head , newNode);
            newNode.next = copyRandomList(head.next);
            newNode.random = copyRandomList(head.random);
        }
        return map.get(head);
    }
}

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

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

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

img

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

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

img

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

方法一：dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    Node pre , head;
    public Node treeToDoublyList(Node root) {
        if(root == null)return null;
        recur(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    public void recur(Node cur){
        if(cur == null)return;
        recur(cur.left);
        if(pre != null)pre.right = cur;
        else head = cur;    
        cur.left = pre;
        pre = cur;
        recur(cur.right);
    }
}

剑指 Offer 37. 序列化二叉树

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

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

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

示例：

img

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

方法一：层序遍历

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 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)return null;
        StringBuffer buffer = new StringBuffer();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node == null){
                buffer.append("null,");
            }else{
                buffer.append(node.val+",");
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        buffer.setLength(buffer.length() - 1);
        return buffer.toString();
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null)return null;
        String[] dataArray = data.split(",");
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode res = new TreeNode(Integer.valueOf(dataArray[0]));
        deque.add(res);
        int i = 1;
        while(i < dataArray.length){
            TreeNode node = deque.poll();
            
            if(!dataArray[i].equals("null")){
                node.left = new TreeNode(Integer.valueOf(dataArray[i]));
                deque.add(node.left);
            }

            if(++i >= dataArray.length)break;

            if(!dataArray[i].equals("null")){
                node.right = new TreeNode(Integer.valueOf(dataArray[i]));
                deque.add(node.right);
            }
            i++;
        }
        return res;
    }
}

剑指 Offer 38. 字符串的排列

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

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

示例:

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

限制：

1
1 <= s 的长度 <= 8

解题方法一：回溯

我们也是假设全排列，通过visit来看是否访问过，通过递归遍历全部，加入到list中，但是要进行去重

一是最终结果去重，

二是遍历中去重，

我们将其排一下序，比如 a a b c

我们 让两个 a a 区别一下，分别是 a1 a2 ，假定一个排列， … a1…….a2 ….，省略号代表中间有别的元素， 另外一种 … a2 ……..a1….，这里其他元素都一模一样，所以这里就出现了重复的排列，先用a1 然后用 a2， 其实都是一样的序列。

我们这里进行排序，保证我每次只用第一个a1进行排序，后边在出现a1不排列不就行了。 注意不排列不是不用，而是假如我们选用排好序的a1进行排列，那么碰到a2也会进行正常的排列，可以理解成先用了a1，然后用了a2。 后边开始测试a2开头了，我们当然要把这个情况去掉，应为a1开头是一样的呀。

所以看到a2了，我们看前边那个元素是否用过，没用那肯定是以a2开头的这次测试了，就不进行这个排列了，直接下一次。 

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 String[] permutation(String s) {
        int len = s.length();
        boolean[] visit = new boolean[len];
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        StringBuffer buffer = new StringBuffer();
        List<String> res = new ArrayList<>();
        recur(res , buffer , arr , visit , 0 , len);
        String[] recArr = new String[res.size()];

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

    public void recur(List<String> res , StringBuffer buffer , char[] arr , boolean[] visit , int bufferLen , int len){
        if(bufferLen == len){
            res.add(buffer.toString());
            return;
        }

        for(int i = 0 ; i < len ; i++){
            if(visit[i] || (i > 0 && !visit[i-1] && arr[i] == arr[i-1]) )continue;
            visit[i] = true;
            buffer.append(arr[i]);
            recur(res , buffer , arr , visit , bufferLen+1 , len);
            buffer.deleteCharAt​(bufferLen);
            visit[i] = false;
        }
    }
}

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

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

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

示例 1:

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

限制：

1
1 <= 数组长度 <= 50000

方法一：哈希表，存每个，并统计个数

方法二：排序返回中位数

方法三：随机化，随机挑选验证

方法四：投票算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int majorityElement(int[] nums) {
        int count = 1 , res = nums[0];
        for(int i = 1 ; i < nums.length ; i++){
            if(res == nums[i])count++;
            else if(count > 0)count--;
            else {
                res = nums[i];
                count = 1;
            }
        }
        return res;
    }
}

剑指 Offer 40. 最小的k个数

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

示例 1：

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

示例 2：

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

限制：

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000

方法一：排序

方法二：堆

方法三：快速排序

快速排序的时候，我们不需要排序全部的，只要前K个数就行了，我们看分割的数，如果恰好等于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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        quickSort(arr, 0 , arr.length - 1 , k-1);
        int[] res = new int[k];
        for(int i = 0 ; i < k ; i++){
            res[i] = arr[i];
        }
        return res;
    }

    public void quickSort(int[] arr , int left , int right , int k){
        if(left < right){
            int partitionIndex = randomPartition(arr , left , right);
            if(partitionIndex == k)return;
            if(partitionIndex < k)quickSort(arr , partitionIndex + 1 , right , k);
            else quickSort(arr , left , partitionIndex -1 , k);
        }
    }

    public int randomPartition(int[] arr , int left , int right){
        int random = new Random().nextInt(right - left + 1) + left;
        swap(arr , left , random);
        return partition(arr , left , right );
    }
    public int partition(int[] arr , int left , int right ){
        int pivot = left;
        int index = left + 1;
        for(int i = index ; i <= right ; i++){
            if(arr[pivot] > arr[i]){
                swap(arr , index , i);
                index++;
            }
        }
        swap(arr , index-1 , left);
        return index - 1;
    }

    public void swap(int[] arr , int x , int y){
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}

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

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

例如，

[2,3,4] 的中位数是 3

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

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例 1：

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

示例 2：

1
2
3
4
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

限制：

  • 最多会对 addNum、findMedian 进行 50000 次调用。

方法一：优先队列

维护一个大根堆放一半中小的元素，小根堆放一半中大的元素。取两个队列的头部，加入元素的时候看num大小往两边差，然后看两个大小差，超过2就要调换

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
class MedianFinder {
    PriorityQueue<Integer> queueMax;
    PriorityQueue<Integer> queueMin;
    /** initialize your data structure here. */
    public MedianFinder() {
        queueMax = new PriorityQueue<Integer>( (o1 , o2) -> o1 - o2);
        queueMin = new PriorityQueue<Integer>( (o1 , o2) -> o2 - o1);
    }
    
    public void addNum(int num) {
        if(queueMax.isEmpty() || num > queueMax.peek()){
            queueMax.add(num);
            if(queueMax.size() > queueMin.size() + 1){
                queueMin.add(queueMax.poll());
            }
        }else{
            queueMin.add(num);
            if(queueMax.size() < queueMin.size()){
                queueMax.add(queueMin.poll());
            }
        }
    }

    public double findMedian() {
        if(queueMax.size() > queueMin.size()){
            return queueMax.peek();
        }else return (queueMin.peek() + queueMax.peek())/2.0 ;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

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

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

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

示例1:

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

提示：

  • 1 <= arr.length <= 10^5
  • -100 <= arr[i] <= 100

方法一：动态规划

或者贪心的思想，每次看前边这个累加值是否对现在有贡献，有就加上，没有就放弃，直接用当前的值

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        int cur = 0 , pre = 0 , res = Integer.MIN_VALUE;

        for(int i = 0 ; i < nums.length ; i++){
            cur = pre > 0 ? pre + nums[i] : nums[i];
            pre = cur;
            res = Math.max(res , cur);
        }
        return res;
    }
}

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

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

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

示例 1：

1
2
输入：n = 12
输出：5

示例 2：

1
2
输入：n = 13
输出：6

限制：

  • 1 <= n < 2^31

方法一：找规律

可以将1~n的 个位、十位、百位、、、1出现的次数相加，即为1出现的总次数

某位中 11 出现次数的计算方法：
根据当前位 curcur 值的不同，分为以下三种情况：

  1. 当 cur=0 时： 此位 1 的出现次数只由高位 high 决定，计算公式为：

image-20220819160256483

  1. 当 cur = 1 时：此位 11 的出现次数由高位 high 和低位 low决定，计算公式为：

image-20220819160416716

  1. 当 cur = 2, 3, ..9时：此位 11 的出现次数只由高位 high 决定，计算公式为

image-20220819160452504

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int countDigitOne(int n) {
        int digit = 1 , cur = n % 10 , high = n/10 , low = 0 , res = 0;

        while(high != 0 || cur != 0){
            if(cur == 0)res+= high * digit;
            else if(cur == 1)res += high * digit + low + 1;
            else res += (high + 1) * digit;
            low += cur*digit;
            cur = high%10;
            high = high/10;
            digit *= 10;
        }
        return res;   
    }
}

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

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

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

示例 1：

1
2
输入：n = 3
输出：3

示例 2：

1
2
输入：n = 11
输出：0

限制：

  • 0 <= n < 2^31

方法一：

image-20220819153319305

1.确定n所属于的start，

2.确定n落到了那个数字上。

3.确定是在这个数字的哪一个位上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findNthDigit(int n) {
        int digit = 1;
        long start = 1 ,  count = 9;

        while(n > count){
            n -= count;
            start *= 10;
            digit += 1;
            count = digit * start * 9;
        }
        long num = start + (n - 1)/digit;
        return Long.toString(num).charAt((n - 1)%digit) - '0';
    }
}

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

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

示例 1:

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

示例 2:

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

提示:

  • 0 < nums.length <= 100

说明:

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

其实本质就是自定义排序规则

方法一：内置排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public String minNumber(int[] nums) {
        //如果，x+y > y+x ，说明，x>y;否则，x<y;按照这个规则排序
        String[] num = new String[nums.length];
        for(int i = 0 ; i < nums.length ; i++){
            num[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(num , (o1 , o2) -> (o1+o2).compareTo(o2+o1));
        StringBuilder res = new StringBuilder();
        for(String s : num){
            res.append(s);
        }
        return res.toString();
    }
}

方法二：快速排序

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 String minNumber(int[] nums) {
        int len = nums.length;
        String[] arr = new String[len];
        for(int i = 0 ; i < len ; i++){
            arr[i] = String.valueOf(nums[i]);
        }
        quickSort(arr , 0 , len - 1);
        StringBuffer res = new StringBuffer();
        for(String s : arr){
            res.append(s);
        }
        return res.toString();
    }

    public String[] quickSort(String[] arr , int left , int right){
        if(left < right){
            int partitionIndex = randomPartition(arr , left , right);
            quickSort(arr , left , partitionIndex - 1);
            quickSort(arr , partitionIndex + 1 , right);
        }
        return arr;
    }

    public int randomPartition(String[] arr , int left , int right){
        int random = new Random().nextInt(right - left + 1) + left;
        swap(arr , left , random);
        return partition(arr , left , right);
    }

    public int partition(String[] arr , int left , int right){
        int pivot = left;
        int index = left + 1;
        for(int i = index ; i <= right ; i++){
            //x + y > y + x   x > y
            if( (arr[pivot] + arr[i]).compareTo(arr[i] + arr[pivot]) > 0){
                swap(arr , index , i);
                index++;
            }
        }
        swap(arr , index - 1 , pivot);
        return index - 1;
    }

    public void swap(String[] arr , int x , int y){
        String temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}

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

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

示例 1:

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

提示：

  • 0 <= num < 231

方法一：动态规划

dp代表方案数，考虑最后的情况

  • 最后两个字符可以组成一个，就有了两种方案，一个是组合，一个是不组合 dp[n] = dp[n-1]+dp[n-2]
  • 最后两个不能组成一个，就只能是前边dp[n-1] 了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int count = 0;
    public int translateNum(int num) {
        String src = String.valueOf(num);
        int pre1 = 1 , pre2 = 1 , cur = 0;

        for(int i = 2 ; i <= src.length() ; i++){
            String temp = src.substring(i-2,i);
            cur = temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0 ? pre1 + pre2 : pre1;
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}

剑指 Offer 47. 礼物的最大价值

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

示例 1:

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

提示：

  • 0 < grid.length <= 200
  • 0 < grid[0].length <= 200

方法一：动态规划

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

        for(int i = 1 ; i < rows; i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j = 1 ; j < columns; j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        for(int i = 1 ; i < rows; i++){
            for(int j = 1 ; j < columns; j++){
                dp[i][j] = Math.max(dp[i-1][j] , dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[rows-1][columns-1];
    }
}

缩短空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxValue(int[][] grid) {
        int rows = grid.length , columns = grid[0].length;
        int[][] dp = new int[rows][columns];

        for(int i = 1 ; i < rows; i++){
            grid[i][0] += grid[i-1][0];
        }
        for(int j = 1 ; j < columns; j++){
            grid[0][j] += grid[0][j-1];
        }
        for(int i = 1 ; i < rows; i++){
            for(int j = 1 ; j < columns; j++){
                grid[i][j] += Math.max(grid[i-1][j] , grid[i][j-1]);
            }
        }
        return grid[rows-1][columns-1];
    }
}

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

  • s.length <= 40000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0 , right = 0 , res = 0;

        while(right < s.length()){
            while(right < s.length() && !set.contains(s.charAt(right))){
                set.add(s.charAt(right));
                right++;
            }
            res = Math.max(res , right - left);
            set.remove(s.charAt(left));
            left++;
        }
        return res;
    }
}

剑指 Offer 49. 丑数

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

示例:

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

说明:

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

方法一：最小堆

我们从下到大去创建最小数，比如1，2，3，4，5，从最小堆里取出每个数，分别乘以丑数，然后放入set去重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> pq = new PriorityQueue<>();
        Set<Long> set = new HashSet<>();
        int[] factors = {2,3,5};
        pq.add(1L);
        set.add(1L);
        int res = 0;
        for(int i = 0 ; i < n ; i++){
            long x = pq.poll();
            res = (int)x;
            for(int factor : factors){
                Long next = x * factor;
                if(set.add(next))pq.add(next);
            }
        }
        return res;
    }
}

方法二：动态规划

首先一定要知道，后面的丑数一定由前面的丑数乘以2，或者乘以3，或者乘以5得来。例如，8,9,10,12一定是1, 2, 3, 4, 5, 6乘以2,3,5三个质数中的某一个得到。

这样的话我们的解题思路就是：从第一个丑数开始，一个个数丑数，并确保数出来的丑数是递增的，直到数到第n个丑数，得到答案。那么问题就是如何递增地数丑数？

观察上面的例子，假如我们用1, 2, 3, 4, 5, 6去形成后面的丑数，我们可以将1, 2, 3, 4, 5, 6分别乘以2, 3, 5，这样得到一共6*3=18个新丑数。也就是说1, 2, 3, 4, 5, 6中的每一个丑数都有一次机会与2相乘，一次机会与3相乘，一次机会与5相乘（一共有18次机会形成18个新丑数），来得到更大的一个丑数。

这样就可以用三个指针，

pointer2, 指向1, 2, 3, 4, 5, 6中，还没使用乘2机会的丑数的位置。该指针的前一位已经使用完了乘以2的机会。
pointer3, 指向1, 2, 3, 4, 5, 6中，还没使用乘3机会的丑数的位置。该指针的前一位已经使用完了乘以3的机会。
pointer5, 指向1, 2, 3, 4, 5, 6中，还没使用乘5机会的丑数的位置。该指针的前一位已经使用完了乘以5的机会。
下一次寻找丑数时，则对这三个位置分别尝试使用一次乘2机会，乘3机会，乘5机会，看看哪个最小，最小的那个就是下一个丑数。最后，那个得到下一个丑数的指针位置加一，因为它对应的那次乘法使用完了。

这里需要注意下去重的问题，如果某次寻找丑数，找到了下一个丑数10，则pointer2和pointer5都需要加一，因为5乘2等于10， 5乘2也等于10，这样可以确保10只被数一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n+1];
        int p2 = 1 , p3 = 1 , p5 = 1;
        dp[1] = 1;
        for(int i = 2 ; i <= n ; i++){
            int nums1 = dp[p2] * 2 , nums2 = dp[p3]*3 , nums3 = dp[p5]*5;
            dp[i] = Math.min(nums1 , Math.min(nums2 , nums3));
            if(dp[i] == nums1)p2++;
            if(dp[i] == nums2)p3++;
            if(dp[i] == nums3)p5++;
        }
        return dp[n];
    }
}

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

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

示例 1:

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

示例 2:

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

限制：

1
0 <= s 的长度 <= 50000

方法一：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public char firstUniqChar(String s) {
        Map<Character , Integer> map = new HashMap<>();
        for(char ch : s.toCharArray()){
            map.put(ch , map.getOrDefault(ch,0) + 1);
        }
        for(char ch : s.toCharArray()){
            if(map.get(ch) == 1)return ch;
        }
        return ' ';
    }
}

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

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

示例 1:

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

限制：

1
0 <= 数组长度 <= 50000

方法一：归并排序

归并排序的思想，就是先分治，分区间，然后合并，两两合并。

利用归并的特性， 比如 3 7 2 6 ， 在合并的时候，3 > 2 ，所以要把2放在前边，因此，mid左边所有的都比当前的值大，所以，我们统计到逆序对的个数。

当到了 2 ， 3， 6 ， 在6的时候又发现前边有大数了，就可以把左边index的下标找到，用mid-index+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
class Solution {
    private int count;
    public int reversePairs(int[] nums) {
        merge(nums, 0 , nums.length-1);
        return count;
    }

    public void merge(int[] arr , int left , int right){
        int mid = left + ((right - left) >> 1);
        if(left < right){
            merge(arr , left , mid);
            merge(arr , mid + 1 ,right);
            mergeSort(arr , left , mid , right);
        }
    }

    public void mergeSort(int[] arr , int left ,int mid , int right){
        int[] temp = new int[right - left + 1];
        int index = 0;
        int x = left , y = mid + 1;
        while(x <= mid && y <= right){
            if(arr[x] <= arr[y])temp[index++] = arr[x++];
            else {
                temp[index++] = arr[y++];
                count += mid - x + 1;
            }

        }
        while(x <= mid)temp[index++] = arr[x++];
        while(y <= right)temp[index++] = arr[y++];
        for(int k = 0 ; k < temp.length ; k++){
            arr[k + left] = temp[k];
        }
    }
}

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

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

如下面的两个链表：

img

在节点 c1 开始相交。

示例 1：

img

1
2
3
输入：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：

img

1
2
3
输入：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：

img

1
2
3
4
输入：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。

注意：

方法一：哈希表

方法二：双指针

利用 A ： a + c + b B : b + c + a ，让两个都走，abc，就可以会合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode nodeA = headA , nodeB = headB;
        while(nodeA != nodeB){
            nodeA = nodeA == null ? headB : nodeA.next;
            nodeB = nodeB == null ? headA : nodeB.next;
        }
        return nodeA; 
    }
}

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

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

示例 1:

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

示例 2:

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

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109
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 search(int[] nums, int target) {
        int left = 0 ,right = nums.length-1;

        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(target <= nums[mid])right = mid - 1;
            else left = mid + 1;
        }

        int index = right;

        left = 0 ; right = nums.length-1;

        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(target < nums[mid])right = mid-1;
            else left = mid + 1;
        }
        return left - index - 1;
    }
}

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

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

示例 1:

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

示例 2:

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

限制：

1
1 <= 数组长度 <= 10000

方法一：遍历一遍

方法二：二分

二分要注意边界，这道题可能出现， 0 ，1 ，2 ，3 这样就是确少4，这个没法找出来，所以要往右靠，只要相等就往右边找，不能num[i] < i 小于就往左边找,因为我们返回的是right，所以right始终到不了4。可能会疑问，为什么不反回left ，因为left是跳出条件，比如，mid-1,找到了缺失位置，此时right = 缺失元素，left，要大于这个值跳出，所以找不到右边界。

1
2
if(nums[mid] < mid)right = mid - 1;
else left = mid + 1;
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int missingNumber(int[] nums) {
        int left = 0 , right = nums.length - 1;

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

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

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

示例 1:

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

示例 2:

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

限制：

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

方法一：递归

中序遍历的倒序， 右 根 左

注意 找到 K 大的数就要返回，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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.res = 0;
        this.k = k;
        recur(root);
        return res;
    }
    public void recur(TreeNode root) {
        if(root == null)return;
        recur(root.right);
        if(k == 0)return;
        if(--k == 0)res = root.val;
        recur(root.left);
    }
}

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

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

例如：

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

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

方法一：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)return 0;
        return Math.max(maxDepth(root.left) , maxDepth(root.right)) + 1;
    }
}

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

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

示例 1：

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

示例 2：

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

限制：

  • 2 <= nums.length <= 10000

方法一：分组异或

只有一个数的我们知道，全员异或就能找到，对于两个数，全员异或之后就相当于这两个数异或，就可以按照异或性质，相异为1，将这两个数分开，然后全组按照这一位分开，进行异或，找到这两个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] singleNumbers(int[] nums) {
        
        int ret = 0;
        for(int n : nums){
            ret ^= n;
        }

        int index = 1;
        while( (index & ret) == 0)index <<= 1;

        int a = 0 , b = 0;
        for(int n : nums){
            if( (n & index) == 0)a ^= n;
            else b ^= n;
        }
        return new int[]{a,b};
    }
}

剑指 Offer 57. 和为s的两个数字

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

示例 1：

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

示例 2：

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

限制：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

方法一：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        
        for(int i = 0 ; i < nums.length ; i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{nums[map.get(target - nums[i])] , nums[i]};
            }
            map.put(nums[i], i);
        }
        return new int[2];
    }
}

方法二：双指针

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

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

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

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

示例 1：

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

示例 2：

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

限制：

  • 1 <= target <= 10^5

方法一：滑动窗口

要用滑动窗口解这道题，我们要回答两个问题：

  • 第一个问题，窗口何时扩大，何时缩小？
  • 第二个问题，滑动窗口能找到全部的解吗？

对于第一个问题，回答非常简单：

当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动
当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动
当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [i, j)[i,j)，那么我们已经找到了一个 ii 开头的序列，也是唯一一个 ii 开头的序列，接下来需要找 i+1i+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
class Solution {
    public int[][] findContinuousSequence(int target) {
        int left = 1 , right = 1;
        int sum = 0;
        List<int[]> list = new ArrayList<>();
        while(left <= target/2){
            if(sum == target){
                int[] arr = new int[right - left];
                for(int i = 0 ; i < right - left ; i++){
                    arr[i] = left + i;
                }
                list.add(arr);
                sum -= left;
                left++;
            }
            if(sum < target){
                sum += right;
                right++; 
            }
            if(sum > target){
                sum -= left;
                left++;
            }
        }
        return list.toArray( new int[list.size()][]  );
    }
}

方法二：超级暴力

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[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();

        for(int i = 1 ; i <= target/2 ; i++){
            int sum = 0;
            for(int j = i ; ;j++){
                sum += j;
                if(sum > target)break;
                if(sum == target){
                    int[] arr = new int[j - i + 1];
                    for(int k = 0 ; k < j - i + 1 ; k++){
                        arr[k] = k + i;
                    }
                    list.add(arr);
                }
            }
        }
        return list.toArray( new int[list.size()][]  );
    }
}

剑指 Offer 58 - I. 翻转单词顺序

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

示例 1：

1
2
输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

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

示例 3：

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

说明：

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

方法一：双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        int i = s.length() - 1 , j = i;
        StringBuffer str = new StringBuffer();

        while(i >= 0){
            while(i >= 0 && s.charAt(i) != ' ')i--;
            str.append(s.substring(i+1 , j+1) + " ");
            while(i >= 0 &&s.charAt(i) == ' ')i--;
            j = i;
        }
        return str.toString().trim();
    }
}

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

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

示例 1：

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

示例 2：

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

限制：

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

方法一：取余

从n开始，和len取余数， n 到 len 就是开始的位置，len 到 len+n ，就是 0到n，正好前边移到后边

1
2
3
4
5
6
7
8
9
10
class Solution {
    public String reverseLeftWords(String s, int n) {
        int len = s.length();
        StringBuffer res = new StringBuffer();
        for(int i = n ; i < len + n ; i++){
            res.append(s.charAt(i % len)); 
        }
        return res.toString();
    }
}

方法二：拼接截断

类似方法一

将 两个 s 拼起来， 比如 s = “ a b c d e “ k = 2; ss = “ a b c d e a b c d e” ,从n到len+n，截断就行

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

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

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

提示：

你可以假设 k 总是有效的，在输入数组 不为空 的情况下，1 ≤ k ≤ nums.length。

方法一：最大堆

维护最大K个数的堆 ， 每次滑动的时候，就往堆中放，当时这种每删除和加入一个元素就要重新堆排序。所以我们优化一下，把下标也放进去，不随着添加一个一个往外移除元素，只有发现最大值的小标超过滑动窗口边界的时候，就往外吐元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>( (o1,o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o2[0] - o1[0]);
        for(int i = 0 ; i < k ; i++){
            pq.offer( new int[]{nums[i] , i} );
        }
        int[] res = new int[len - k + 1];
        res[0] = pq.peek()[0];
        for(int i = k; i < len ; i++){
            pq.offer(new int[]{nums[i] , i});
            while(pq.peek()[1] <= i-k)pq.poll();
            
            res[i-k+1] = pq.peek()[0];
        }
        return res;
    }
}

方法二：单调队列

但是方法一还可以优化，

  • 我们维护 i j ， 且 i<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
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[len-k+1];

        for(int i = 0 ; i < k ; i++){
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offer(i);
        }
        res[0] = nums[deque.peekFirst()];
        for(int i = k ; i < len ; i++){
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
            while(i - k >= deque.peekFirst()){
                deque.pollFirst();
            }
            res[i - k + 1] = nums[deque.peekFirst()];
        }
        return res;
    }
}

剑指 Offer 59 - II. 队列的最大值

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

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

示例 1：

1
2
3
4
输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

1
2
3
4
输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

限制：

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

方法一：双端队列

有个小问题，注意直接拿队列peek比较实际是包装类在比较

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 MaxQueue {
    Deque<Integer> dequeMax;
    Deque<Integer> deque;   
    public MaxQueue() {
        dequeMax = new LinkedList<>();
        deque = new LinkedList<>();
    }
    
    public int max_value() {
        return dequeMax.isEmpty() ? -1 : dequeMax.peekFirst();
    }
    
    public void push_back(int value) {
        deque.offer(value);
        while(!dequeMax.isEmpty() && value > dequeMax.peekLast()){
            dequeMax.pollLast();
        }
        dequeMax.offerLast(value);
    }
    
    public int pop_front() {
        if(deque.isEmpty())return -1;
        int res = deque.pollFirst();
        if(res == dequeMax.peekFirst()){
            return dequeMax.pollFirst();
        }
        return res;
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */

剑指 Offer 60. n个骰子的点数

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

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

示例 1:

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

示例 2:

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

限制：

1
1 <= n <= 11

方法一：动态规划

我们知道，扔一个筛子的和就是1到6 ，两个的话就是2到12 …… 所以 n 个筛子就是 n 到 n*5+1 。

仍一个筛子的时候，概率都是1/6，2个的话，2-12， 我们分别拿上次扔的结果，再扔一次，也就是说，算一下上次每一个dp[i]的概率乘以这次扔的概率，然后我们遍历dp，比如上次1，2，3，4，5，6. 这次遍历就在1的基础上，遍历1-1，1-2，1-3，1-4，1-5，1-6，等等往后，只需要返回各个数的概率，我们直接往对应下标放就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public double[] dicesProbability(int n) {
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6.0);

        for(int i = 2 ; i <= n ; i++){
            double[] temp = new double[i*5+1];
            for(int j = 0 ; j < dp.length ; j++){
                for(int k = 0 ; k < 6 ; k++){
                    temp[k+j] += dp[j]*(1.0/6.0);
                }
            }
            dp = temp; 
        }
        return dp;
    }
}

剑指 Offer 61. 扑克牌中的顺子

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

示例 1:

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

示例 2:

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

限制：

数组长度为 5

数组的数取值为 [0, 13] .

方法一：哈希表，去重，统计最大值最小值

方法二：排序后，判断重复和最大最小

根据题意，此 55 张牌是顺子的 充分条件 如下：

除大小王外，所有牌 无重复 ；设此 55 张牌中最大的牌为 max ，最小的牌为 min （大小王除外），则需满足：

  • max - min < 5
  • max−min<5
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);

        int king = 0;
        for(int i = 0 ; i < 4 ; i++){   
            if(nums[i] == 0)king++;
            else if(nums[i] == nums[i+1])return false;
        }
        return nums[4] - nums[king] <= 4;
    }
}

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

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

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

示例 1：

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

示例 2：

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

限制：

  • 1 <= n <= 10^5
  • 1 <= m <= 10^6

方法一：递归

我们令f(n,m) = y

f(n-1,m)是表示在长度为n-1的序列中，以0为起点（这个是前提），一直删除，最后剩下的节点所在的下标。假设现在序列长度为n，此时删除一个元素（也是以0为起点），长度就变成了n-1，但删除一个元素之后，此时的起点下标是m%n。而通过f(n-1,m)我们得知了以0为起点时一直删除，剩下最后一个元素的下标。但现在是以m%n为起点，因此结果应该加上一个长度为m%n的偏移量，因此有f(n,m) = (f(n-1,m)+m%n)%n =( f(n-1, m)+m)%n。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int lastRemaining(int n, int m) {
        return f(n,m);
    }
    public int f(int n , int m){
        if(n == 1)return 0;
        int x = f(n - 1 , m);
        return (x+m)%n;
    } 
}

方法二：迭代

1
2
3
4
5
6
7
8
9
class Solution {
    public int lastRemaining(int n, int m) {
        int i = 1 , res = 0 ;
        while( i++ < n){
            res = (res + m ) % i;
        }
        return res;
    }
}

剑指 Offer 63. 股票的最大利润

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

示例 1:

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

示例 2:

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

限制：

1
0 <= 数组长度 <= 10^5
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE , res = 0;
        for(int price : prices){
            minPrice = Math.min(minPrice , price);
            res = Math.max(res , price - minPrice);
        }
        return res;
    }
}

剑指 Offer 64. 求1+2+…+n

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

示例 1：

1
2
输入: n = 3
输出: 6

示例 2：

1
2
输入: n = 9
输出: 45

限制：

  • 1 <= n <= 10000

方法一：利用&&的执行进行递归

1
2
3
4
5
6
7
8
class Solution {
    public int sumNums(int n) {
        boolean flag = true;
        int res = 0;
        flag = n > 0 &&   (n += sumNums(n-1) )  > 0;
        return n;
    }
}

方法二：快速乘

「俄罗斯农民乘法」

考虑 A 和 B 两数相乘的时候我们如何利用加法和位运算来模拟，其实就是将 B 二进制展开，如果 B 的二进制表示下第 i 位为 1，那么这一位对最后结果的贡献就是 A*(1<<i)，即 A<<i，我们遍历 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
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 Solution {
    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;
    }
}

剑指 Offer 66. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

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

提示：

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

方法一：前缀，后缀乘积

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[] constructArr(int[] a) {
        int len = a.length;
        if(len == 0)return new int[0];
        int[] L = new int[len];
        int[] R = new int[len];

        L[0] = 1;
        for(int i = 1; i < len ; i++){
            L[i] = L[i-1]*a[i-1];
        }

        R[len-1] = 1;
        for(int i = len-2; i >= 0 ; i--){
            R[i] = R[i+1]*a[i+1];
        }

        int[] res = new int[len];
        for(int i = 0 ; i < len ; i++){
            res[i] = L[i] * R[i];
        }
        return res;
    }
}

省略空间算法

我们可以把返回数组当作L的前缀乘积，然后用一个备份R来存储后缀积，直接做相乘返回res。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] constructArr(int[] a) {
        int len = a.length;
        if(len == 0)return new int[0];
        int[] res = new int[len];
        res[0] = 1;
        for(int i = 1; i < len ; i++){
            res[i] = res[i-1]*a[i-1];
        }

        int R= 1;
        for(int i = len-1; i >= 0 ; i--){
            res[i] = res[i] * R;
            R = R*a[i];
        }
        return res;
    }
}

剑指 Offer 67. 把字符串转换成整数

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

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

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

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

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

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

说明：

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

示例 1:

1
2
输入: "42"
输出: 42

示例 2:

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

示例 3:

1
2
3
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

示例 4:

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

示例 5:

1
2
3
4
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

根据题意，有以下四种字符需要考虑：

  1. 首部空格： 删除之即可；

  2. 符号位： 三种情况，即 ‘’+’’ , ‘’−’’ , ‘’无符号” ；新建一个变量保存符号位，返回前判断正负即可。

  3. 非数字字符： 遇到首个非数字的字符时，应立即返回。

  4. 数字字符：

    • 字符转数字： “此数字的 ASCII 码” 与 “ 0 的 ASCII 码” 相减即可；

    • 数字拼接： 若从左向右遍历数字，设当前位字符为 c ，当前位数字为 x ，数字结果为 res ，则数字拼接公式为：

      • res = 10×res+x
      • x = asci(c) - asci('0')
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 strToInt(String str) {
        int i = 0 , flag = 1 , res = 0 , bound = Integer.MAX_VALUE/10;
        int len = str.length();
        //去空格
        if(len == 0) return 0;
        while(str.charAt(i) == ' ')if(++i == str.length())return 0;
        //判正负
        if(str.charAt(i) == '-')flag = -1;
        if(str.charAt(i) == '-' || str.charAt(i) == '+')i++;

        for(int j = i ; j < str.length() ; j++){
            if(str.charAt(j) > '9' || str.charAt(j) < '0')break;
            if(res > bound || (res == bound && str.charAt(j) > '7')){
                return flag == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            res = res * 10 + (str.charAt(j) - '0');
        }
        return res*flag;
    }
}

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

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

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

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

img

示例 1:

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

示例 2:

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

说明:

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

方法一：迭代

因为是二叉搜索树，所以只要pq都小于root，就可以往左边找，反之往右边找，如果不是这两种情况，那就是一个在左边一个在右边，或着root等于p或者q就可以返回该节点了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null){
            if(root != null && root.val > p.val && root.val > q.val){
                root = root.left;
            }   
            else if(root != null && root.val < p.val && root.val < q.val){
                root = root.right;
            }
            else break;
        }
        return root;
    }
}

方法二：递归

递归往下走，如果小于，往左边递归，大于，右边递归，其他就返回值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    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;
    }
}

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

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

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

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

img

示例 1:

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

示例 2:

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

说明:

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

方法一：递归

我们把问题分割，是子树有两种情况，一种是P、Q是公共节点，一种是在root的两侧，

所以我们查找，只要是查到一个节点，就可以向上边返回true，代表随便再有一个节点就OK了

所以递归潘是否含有PQ,然后遇到含有，就判断是否是上边两中含有，是就返回。

递归要返回的是只要是含有节点，或者当前节点就是，就返回true

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode res;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        recur(root , p , q);
        return res;
    }
    public boolean recur(TreeNode root, TreeNode p, TreeNode q){
        if(root == null)return false;
        boolean lSon = recur(root.left , p , q);
        boolean rSon = recur(root.right , p , q);
        if( lSon && rSon || (root.val == p.val || root.val == q.val) && (lSon || rSon)){
            res = root;
        }
        return lSon || rSon || p.val == root.val || q.val == root.val;
    }
}

方法二：递归存储父节点，然后从p,开始向上找父节点，并记录路径，set集合判断重合父节点。