力扣学习录02--剑指Offer刷题记录（上）

Huang Zhiwei
  2023-04-23 19:20:11 2023-04-23 19:20 创建   2023-09-02 23:04:27 2023-09-02 23:04 更新    

剑指Offer刷题记录，共75题，陆续更新中

剑指 Offer（第 2 版） - 力扣（LeetCode）

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

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

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

方法：使用哈希集合的方法，如果出现重复就直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 1. @ClassDescription: 数组中重复的数字
 * 简单的用集合做即可
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 21:33
 */
public class Offer03 {
    public static void main(String[] args) {
        int[] input = {2, 3, 1, 0, 2, 5, 3};
        System.out.println(findRepeatNumber(input));
    }
    public static int findRepeatNumber(int[] nums) {
        HashSet<Integer> hashset = new HashSet<>();
        for(int x:nums){
            if(hashset.contains(x)) return x;
            else{
                hashset.add(x);
            }
        }
        return 0;
    }
}

剑指 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
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
/**
 * 1. @ClassDescription: 二维数组的查找
 * https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
 * 对每一行使用二分查找，降低查询耗时。
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月07日 21:31
 */
public class Offer04 {
    /**
    * @MethodDescription:
    * @param args:
    * @Return: void
    * @author: Huang Zhiwei
    * @date: 2023/4/7
    */
    public static void main(String[] args) {
        int[][] 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}};
        System.out.println(findNumberIn2DArray(matrix, 23));
    }

    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        for(int i = 0;i<matrix.length;i++){
            if(binarySearch(matrix[i],target)){
                return true;
            }
        }
        return false;
    }
    public static boolean binarySearch(int[] input,int target){
        int low = 0;
        int high = input.length-1;
        while(low <= high){
            int mid = (high-low)/2+low;
            if(input[mid] == target){
                return true;
            }else if(input[mid] >target){
                high = mid-1;
            }else {
                low =  mid+1;
            }
        }
        return false;
    }
}

剑指 Offer 05. 替换空格

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

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

方法：直接调用库函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 1. @ClassDescription: 替换空格
 * 直接调用库函数
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 19:18
 */
public class Offer05 {
    public static void main(String[] args) {
        String input = "We are happy.";
        System.out.println(replaceSpace(input));
    }
    public static String replaceSpace(String s) {
        return s.replace(" ","%20");
    }
}

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

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

1
2
输入：head = [1,3,2]
输出：[2,3,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
/**
 * 1. @ClassDescription: 从尾到头打印链表
 * 用栈，先压栈再出栈
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 19:21
 */
public class Offer06 {
    public static void main(String[] args) {

    }

    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        int[] val = new int[stack.size()];
        int i = 0;
        while(!stack.isEmpty()){
            val[i++] = stack.pop().val;
        }
        return val;
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

剑指 Offer 07. 重建二叉树

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

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

1
2
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
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
/**
 * 1. @ClassDescription: 重建二叉树
 * 前序遍历的第一个元素肯定就是根节点，由于不含重复数字，所以可以在中序遍历中找到这个根节点，它的左右两个数字就是左右孩子
 * 按照以上思路，可以用递归
 * 前序数组的第一个作为根节点直接创建；找到这个数在中序数组的位置；开始分割数组，前半部分都是左子树，后半部分都是右子树；
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 19:37
 */
public class Offer07 {
    public static void main(String[] args) {
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        System.out.println(buildTree(preorder, inorder));
        System.out.println("finished");
    }
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0) return null;
        if(preorder.length == 1){
            return new TreeNode(preorder[0]);
        }
//        if(inorder.length == 1 ){
//            return new TreeNode(inorder[0]);
//        }
        //前序遍历的第一个元素肯定就是根节点
        TreeNode ROOT = new TreeNode(preorder[0]);
        //从中序遍历返回的下标可以得出，左边有index个，从0到index位置（左子树）
        //右边就是index+1到最后（右子树）
        int index = search(inorder,preorder[0]);
        //注意前序的第一个就是根节点，要去除
        TreeNode left = buildTree(Arrays.copyOfRange(preorder,1,index+1),Arrays.copyOfRange(inorder,0,index));
        TreeNode right = buildTree(Arrays.copyOfRange(preorder,index+1,preorder.length),Arrays.copyOfRange(inorder,index+1,inorder.length));
        ROOT.left = left;
        ROOT.right = right;
        return ROOT;
    }
    public static int search(int[] input,int target){
        for(int i = 0;i<input.length;i++){
            if(input[i] == target){
                return i;
            }
        }
        return 0;
    }
    public static int binarySearch(int[] input,int target){
        int low = 0;
        int high = input.length-1;
        while(low <= high){
            int mid = (high-low)/2+low;
            if(input[mid] == target){
                return mid;
            }else if(input[mid] >target){
                high = mid-1;
            }else {
                low =  mid+1;
            }
        }
        return 0;
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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

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

1
2
3
4
输入：
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
[[],[3],[],[],[]]
输出：[null,null,3,-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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 1. @ClassDescription: 用两个栈实现队列，完成在队列尾部插入整数和在队列头部删除整数的功能
 * stack2负责出栈也就是出队列，stack1作为工具队列，当需要加入数据时就完整地倒腾一边栈
 * 看了题解可以用ArrayDeque替代stack，它也是栈，而且效率更高。
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 20:37
 */
public class Offer09 {
    public static void main(String[] args) {
        CQueue obj = new CQueue();
        obj.appendTail(100);
        int param_2 = obj.deleteHead();
        System.out.println(param_2);
    }
    static class CQueue {
        Stack<Integer> stack1 = new Stack<>();
        //stack2 负责出栈/出队列
        Stack<Integer> stack2 = new Stack<>();
        public CQueue() {

        }

        public void appendTail(int value) {
            stack1.clear();
            while(!stack2.isEmpty()){
                stack1.add(stack2.pop());
            }
            stack1.add(value);
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }

        public int deleteHead() {
            if (stack2.isEmpty()){
                return -1;
            }else {
                return stack2.pop();
            }

        }
    }
}

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

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

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 1. @ClassDescription: 斐波那契数列
 * 不可以用递归来做，这很耗资源
 * 用动态规划来做
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 21:09
 */
public class Offer10_1 {
    public static void main(String[] args) {
        System.out.println(fib(100));
    }
    public static int fib(int n) {
        if(n<=1){return n;}

        int[] ans = new int[n+1];
        ans[1] = 1;
        int i = 2;
        while(i<=n){
            ans[i] = (ans[i-1]+ans[i-2]) % 1000000007;
            i+=1;
        }
        return ans[n];
    }
}

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

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 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
/**
 * 1. @ClassDescription: 青蛙跳台阶问题
 * 首先想到的一定是递归，但是这个和斐波那契数列非常相似，递归会导致超时
 * 所以用动态规划
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 21:15
 */
public class Offer10_2 {
    public static void main(String[] args) {
        System.out.println(numWays(100));
    }
    public static int numWays(int n) {
        if(n==0){return 1;}
        if(n<=3){return n;}

        int[] ans = new int[n+1];
        ans[0] = 1;
        ans[1] = 1;
        int i = 2;
        while(i<n+1){
            ans[i] = (ans[i-1]+ans[i-2]) % 1000000007;
            i+=1;
        }
        return ans[n];
    }
}

剑指 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 1. @ClassDescription: 旋转数组的最小数字
 * 旋转数组，可以一次把多个大的数字放到前面来。
 * 遍历数组，如果后向比前项小，说明这就是最小的数；如果遍历一边还找不到，数组就是正常升序排列的，返回数组头。
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 21:22
 */
public class Offer11 {
    public static void main(String[] args) {

    }
    public int minArray(int[] numbers) {
        if(numbers.length == 1) return numbers[0];
        for(int i = 0;i<=numbers.length-2;i++){
            if(numbers[i+1] - numbers[i] < 0 ){
                return numbers[i+1];
            }
        }
        return numbers[0];
    }
}

剑指 Offer 12. 矩阵中的路径

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

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

image-20230423195934952

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
/**
 * 1. @ClassDescription: 矩阵中的路径
 * 用深度优先搜索+剪枝处理，其中需要注意的点在不能走回头路，所以要将当前位置置为不可见字符
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 21:31
 */
public class Offer12 {
    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word = "ABCCED";
        System.out.println(exist(board, word));
    }
    public static boolean exist(char[][] board, String word) {
        char[] wordArray = word.toCharArray();
        for(int i = 0;i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                if(dfs(board,wordArray,i,j,0)) return true;
            }
        }
        return false;
    }
    public static boolean dfs(char[][] board,char[] wordArray,int i,int j,int k){
        if(i>= board.length || j>= board[0].length || i<0 || j<0 || board[i][j] != wordArray[k]) return false;
        if(k == wordArray.length-1) return true;
        //由于不能走回头路，所以要将当前位置置为不可见字符。
        board[i][j] = '\0';
        boolean res = dfs(board,wordArray,i-1,j,k+1) || dfs(board,wordArray,i+1,j,k+1)
                ||dfs(board,wordArray,i,j-1,k+1)||dfs(board,wordArray,i,j+1,k+1);
        //当下面几层的递归结束后还要把这个位置的字符放回去。
        board[i][j] = wordArray[k];
        return res;
    }
}

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

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

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

构造一个辅助函数用于获取位数和，用一个二维的可见数组表示是否可见，在递推过程中判断可达的情况，vis[ij]的可达情况取决于vis[i-1,j]和vis[i,j-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
class Solution {
    public int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        boolean[][] vis = new boolean[m][n];
        int ans = 1;
        vis[0][0] = true;
        for(int i = 0;i<m;i++){
            for(int j= 0;j<n;j++){
                //判断那种情况是不行的，一种是ij=0，因为已经作为计数记过了，一种是加起来大于阈值了
                if((i==0 && j==0) || get(i)+get(j) >k){
                    continue;
                }
                //为二维的可达数组赋值,先判断可达
                if(i-1 >=0){
                    vis[i][j] |= vis[i-1][j];
                }
                if(j-1 >=0){
                    vis[i][j] |= vis[i][j-1];
                }
                if(vis[i][j]){
                    ans ++;
                }
            }
        }
        return ans;
    }
    private static int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        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
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
/**
 * 1. @ClassDescription: 剪绳子1
 * 基于数学先验的方法，那就是有3拆3，拆不出了再考虑别的情况
 * 2->1 3->2 4->4 5->6 6->9 7开始就可以用递归了
 *
 * 动态规划的思想：是个简单的动态规划
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 21:50
 */
public class Offer14_1 {
    public static void main(String[] args) {
        System.out.println(cuttingRope(58));
    }
    public static int cuttingRope(int n) {
        switch (n){
            case 2:return 1;
            case 3:return 2;
            case 4:return 4;
            case 5:return 6;
            case 6:return 9;
            default:return cuttingRope(n-3)*3;
        }
    }
    public int cuttingRope2(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                //后一项的max计算的是dp*j 和 j*(i-j),前一项max计算当前最大和后面算出的最大哪个大
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        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
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
/**
 * 1. @ClassDescription: 剪绳子
 * 和上一题不一样，它的递归会导致数值不同，考虑一种情况：100%8 *3 = 12 ；100*3 %8 = 4
 * 所以使用数学推导
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 21:59
 */
public class Offer14_2 {
    public static void main(String[] args) {
        System.out.println(cuttingRope(100));
    }
    public static int cuttingRope(int n) {
        if(n <= 3) return n-1;
        int p = 1000000007;
        int b = n%3 ;
        long rem = 1, x = 3;
        //这里要留出一个3的空间，用于判断剩下的情况。
        for(int a = n / 3 - 1; a > 0; a /= 2){
            if(a % 2 == 1) rem = (rem * x) % p;
            x = (x * x) % p;
        }
        //剩下b=0，加上前面的3，就是*3
        if(b == 0) return (int)(rem * 3 % p);
        //剩下b=1，加上前面的3，就是*4
        if(b == 1) return (int)(rem * 4 % p);
        //剩下b=2，加上前面的3，就是*6
        return (int)(rem * 6 % p);
    }
}

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

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

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

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
/**
 * 1. @ClassDescription: 二进制中1的个数
 * 暴力法就是挨个<<,计算当前位是不是1；
 * 优化的方法是 n&(n-1),如果n的末位是1，那就是将末位变0；如果末位是0，就会借位再计算。特别巧妙的方法。
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 22:14
 */
public class Offer15 {
    public static void main(String[] args) {
        System.out.println(hammingWeight1(114514));
    }
    public static int hammingWeight(int n) {
        int count = 0;
        for(int i = 0;i<32;i++){
            int k = 1<<i;
            if((n & 1<<i) !=0){
                count++;
            }
        }
        return count;
    }
    public static int hammingWeight1(int n) {
        int ret = 0;
        while (n != 0) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
}

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

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

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
/**
 * 1. @ClassDescription: 数值的整数次方
 * 方法是用一个map将高次存起来，通过二分法减少计算量。然后再通过循环，让高次逐渐变成低次。
 * 极大的坑点在于-2147483648超出了int的界限，需要用Long
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 22:26
 */
public class Offer16 {
    public static void main(String[] args) {
        System.out.println(myPow(2.00000,
                -2147483648));
    }
    public static double myPow(double x, int n) {
        return  myPowhelper(x,n);
    }
    public static double myPowhelper(double x, long n){
        if(n == 0 || x ==  1.0) return 1.0;
        if(n == 1) return x;
        if(n<0) {
            return myPowhelper(1/x,-n);
        }
        double ans = 1.0;

        HashMap<Long,Double> map = new HashMap<>();
        map.put(1L,x);
        Long n1 =1L;
        while (n1<=n/2){
            map.put(n1*2L,map.get(n1)*map.get(n1));
            n1*=2;
        }
        while (n>0){
            if((n / n1) == 0){
                n1/=2L;
                continue;
            }
            ans *= map.get(n1);
            n -= n1;
            n1 /= 2L;
        }
        return ans;
    }
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 1. @ClassDescription: 打印从1到最大的n位数
 * 计算10的n次方，直接
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月10日 23:22
 */
public class Offer17 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(printNumbers(2)));
    }
    public static int[] printNumbers(int n) {
        int max = (int)Math.pow(10,n);
        int[] result = new int[max-1];
        int i = 1;
        while (i<max){
            result[i-1] = i;
            i++;
        }
        return result;
    }
}

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

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

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
/**
 * 1. @ClassDescription: 删除链表的节点
 * 删除第i个节点的问题使用双指针法，让一个节点先走n步，再让头节点跟上。当快指针走到末尾的时候，慢指针即是要返回的节点。
 * 本题更简单，只需要比较值就可以了。
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月11日 12:46
 */
public class Offer18 {
    public static void main(String[] args) {

    }
    public static ListNode deleteNode(ListNode head, int val) {
        ListNode dummy = head;
        if(dummy.val== val) return head.next;
        while (dummy.next != null){
            if(dummy.next.val == val){
                dummy.next = dummy.next.next;
                return head;
            }
            dummy = dummy.next;
        }
        return head;
    }
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}

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

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

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
/**
 * 1. @ClassDescription: 正则表达式匹配，使用动态规划
 * 本体极难，用python这样的语言写会容易很多，本体的解法是将python的解法翻译过来的
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月11日 12:53
 */
public class Offer19 {
    public static void main(String[] args) {
        System.out.println(isMatch("aab", "c*a*b"));
    }
    public static boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        //初始化dp数组
        for(int i = 1;i<p.length()+1;i++){
            if(p.charAt(i-1) == '*'){
                dp[0][i] = dp[0][i-2];
            }
        }
        for(int i = 1;i<s.length()+1;i++){
            for(int j = 1;j<p.length()+1;j++){
                if(s.charAt(i-1) == p.charAt(j-1)||p.charAt(j - 1) == '.'){
                    dp[i][j] = dp[i-1][j-1];
                } else if (p.charAt(j - 1) == '*') {
                    if(s.charAt(i-1) != p.charAt(j-2)&& p.charAt(j-2) != '.'){
                        dp[i][j] = dp[i][j-2];
                    }else {
                        dp[i][j] = dp[i-1][j] | dp[i][j-2];
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}
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:
    def isMatch(self, s: str, p: str) -> bool:
        m,n = len(s),len(p)
        dp = [[False]* (n+1) for _ in range(m+1)]
        dp[0][0] = True
        # 设置dp第一行，防止前两个字符出现形如 a* 的情况
        for j in range(1,n+1):
            if p[j-1] == '*':
                dp[0][j] = dp[0][j-2]
        # 更新矩阵
        for i in range(1,m+1):
            for j in range(1,n+1):
                # 字符匹配的情况
                if s[i-1] == p[j-1] or p[j-1] == ".":
                    dp[i][j] = dp[i-1][j-1]
                # 出现*的情况
                elif p[j-1] == "*":
                    # 前一个字符妹有匹配上，且p的前一个字符不是通配符
                    if s[i-1] != p[j-2] and p[j-2] != '.' :
                        dp[i][j] = dp[i][j-2]
                    else:
                        dp[i][j] = dp[i-1][j] | dp[i][j-2]
        return dp[m][n]
# work = Solution()
# print(work.isMatch('www','ww*'))

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

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

本题属于搞脑子的那种，严谨的做法太费力了，一下是一种取巧的做法，摘自leetcode题解。

trim函数去除首尾空格，用Double.parseDouble库函数帮助判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isNumber(String s) {
        if(s == null || s.length() == 0){
            return false;
        }

        //面向测试用例编程，先去除首尾空格
        s = s.trim();
        try{
            double a = Double.parseDouble(s);
        }catch (Exception e){
            return false;
        }

        char c = s.charAt(s.length()-1);
        //特，末尾有f，d,D这些不算，但是3.算数字（面向测试用例编程）
        return (c >= '0' && c <= '9') || c == '.';
    }
}

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

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

1
2
3
输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。
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
/**
 * 1. @ClassDescription: 调整数组顺序使奇数位于偶数前面
 * 和快速排序的思想类似，先动后面的数字，找到奇数，再动前面的数字，找到偶数，然后互换。注意超出边界的问题即可。
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月23日 20:22
 */
public class Offer21 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4};
        System.out.println(Arrays.toString(exchange(nums)));
    }
    public static int[] exchange(int[] nums) {
        if(nums.length <= 1){
            return nums;
        }
        int left = -1;
        int right = nums.length;
        boolean leftisji = true;
        boolean rightisou = true;
        //先动后面的
        while (left<right && right >0 && left <nums.length-1){
            if(rightisou){
                right--;
                rightisou = (nums[right] %2 ==0); //偶数true，直接下一个，奇数false
                continue;
            }
            if(leftisji){
                left++;
                leftisji = (nums[left] %2 ==1); //偶数true，奇数false
                continue;
            }
            int temp = nums[right];
            nums[right] = nums[left];
            nums[left] = temp;
            rightisou = true;
            leftisji = true;
        }
        return nums;
    }
}

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 1. @ClassDescription: 链表中倒数第k个节点
 * 双指针法
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月23日 20:25
 */
public class Offer22 {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //用前后节点的方法
        ListNode dummy = head;
        while(k > 0){
            dummy = dummy.next;
            k --;
        }
        while(dummy != null){
            head = head.next;
            dummy = dummy.next;
        }
        return head;
    }
}

剑指 Offer 24. 反转链表

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

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
/**
 * 1. @ClassDescription: 反转链表
 * 在遍历链表时，将当前节点的 next
 * next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月26日 13:40
 */
public class Offer24 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
    }
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

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

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

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
/**
 * 1. @ClassDescription: 合并升序链表
 * 需要考虑的就几个特殊情况，即L1\L2为空，其他情况就比大小
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月26日 13:54
 */
public class Offer25 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){return l2;}
        if(l2 == null){return l1;}
        ListNode head = null;
        if(l1.val < l2.val){
            head = new ListNode(l1.val);
            l1 = l1.next;
        }else{
            head = new ListNode(l2.val);
            l2 = l2.next;
        }
        ListNode ans = head;
        while(true){
            if(l1 == null){
                head.next = l2;
                break;
            }
            if(l2 == null){
                head.next = l1;
                break;
            }
            if(l1.val < l2.val){
                head.next = l1;
                l1 = l1.next;
                head = head.next;
            }else{
                head.next = l2;
                l2 = l2.next;
                head = head.next;
            }
        }
        return ans;
    }
}

剑指 Offer 26. 树的子结构

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

B是A的子结构， 即 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
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
/**
 * 1. @ClassDescription: 树的子结构
 * 用先序遍历的方法获取每个节点，然后依次比较；比较的过程调用递归；但是时间复杂度和空间复杂度都较大；
 * 官方给出的题解就非常简洁，直接用递归isSubStructure方法。
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月26日 16:57
 */
public class Offer26 {
    public static void main(String[] args) {
        TreeNode A = new TreeNode(3);
        A.left = new TreeNode(4);
        A.right = new TreeNode(5);
        A.left.left = new TreeNode(1);
        A.left.right = new TreeNode(2);
        TreeNode B = new TreeNode(4);
        B.left = new TreeNode(1);
        System.out.println(isSubStructure(A, B));
    }
    public static boolean isSubStructure(TreeNode A, TreeNode B) {
        if(B == null || A == null){
            return false;
        }
        List<TreeNode> pre = preorderTraversal(A);
        for(TreeNode x:pre){
            if(judge(x,B)){
                return true;
            }
        }
        return false;
    }
    public static List<TreeNode> preorderTraversal(TreeNode A){
        List<TreeNode> ans = new ArrayList<>();
        ans.add(A);
        if(A.left != null){
            ans.addAll(preorderTraversal(A.left));
        }
        if(A.right != null){
            ans.addAll(preorderTraversal(A.right));
        }
        return ans;
    }
    public static boolean judge(TreeNode A,TreeNode B){
        if(B == null){
            return true;
        }
        if(A == null){
            return false;
        }
        if(A.val == B.val){
            return (judge(A.left,B.left)&&judge(A.right,B.right));
        }else{
            return false;
        }
    }
    public boolean isSubStructure2(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    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. 二叉树的镜像

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 1. @ClassDescription: 二叉树的镜像
 * 简单的递归，递归过程可以保证完全遍历这颗树，只需要设置终止条件 root==null 即可。
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月26日 18:09
 */
public class Offer27 {
    public TreeNode mirrorTree(TreeNode root) {
        if(root ==null) return null;
        TreeNode mirror = new TreeNode(root.val);
        mirror.left = mirrorTree(root.right);
        mirror.right = mirrorTree(root.left);
        return mirror;
    }
}

剑指 Offer 28. 对称的二叉树

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 1. @ClassDescription: 对称的二叉树
 * 构造一个判断辅助函数，这个函数用递归的方式实现对称判断，需要注意到就是终止条件
 * 当两条分支同时变为空时，那就是镜像，返回true
 * 当只有一条支路为空，那就返回false
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月26日 18:12
 */
public class Offer28 {
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }
    public static boolean check(TreeNode a,TreeNode b){
        if(a == null && b ==  null){
            return true;
        }
        if(a == null || b == null){
            return false;
        }
        return a.val == b.val && check(a.left,b.right) &&check(a.right,b.left);
    }
}

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

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

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
/**
 * 1. @ClassDescription: 顺时针打印矩阵
 * 纯正的模拟法，就是比较麻烦，通过四个方向标志表示可以向哪个方向移动
 * 2. @author: Huang Zhiwei
 * 3. @date: 2023年04月27日 19:25
 */
public class Offer29 {
    public int[] spiralOrder(int[][] matrix) {
        int i = 0;
        int j = 0;
        if(matrix.length == 0 )return new int[]{};
        int index = matrix.length*matrix[0].length;
        int totalLength = matrix.length*matrix[0].length;
        boolean upflag = false;
        boolean downflag = false;
        boolean leftflag = false;
        boolean rightflag = true;
        // 左右边界和上下边界 0,2 0,2
        int rightend = matrix[0].length-1;
        int leftstart = 0;
        int downend = matrix.length-1;
        int upstart = 0;
        int[] ans = new int[totalLength];
        // 转向时需要修改边界
        // 判断到头了就转向
        while(index > 0){
            ans[totalLength-index] = matrix[i][j];
            index -= 1;
            //四个方向
            if(rightflag && j<rightend){j += 1;}
            else if(leftflag && j>leftstart){j -= 1;}
            else if(downflag && i<downend){i += 1;}
            else if(upflag && i > upstart){i -= 1;}
            //转向
            else if( rightflag && j == rightend){
                rightflag = false;
                downflag = true;
                i += 1;
                upstart += 1;}
            else if( leftflag && j==leftstart){
                leftflag = false;
                upflag = true;
                i -= 1;
                downend -= 1;}
            else if(downflag && i==downend) {
                downflag = false;
                leftflag = true;
                j -= 1;
                rightend -= 1;}
            else if(upflag && i == upstart){
                upflag = false;
                rightflag = true;
                j += 1;
                leftstart += 1;}
        }
        return ans;
    }

}
  • 标题: 力扣学习录02--剑指Offer刷题记录（上）
  • 作者: Huang Zhiwei
  • 创建于: 2023-04-23 19:20:11
  • 更新于: 2023-09-02 23:04:27
  • 链接: https://huangzhw0221.github.io/2023/04/23/Leetcode02/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
 评论
此页目录
力扣学习录02--剑指Offer刷题记录（上）
  1. 剑指 Offer 03. 数组中重复的数字
  2. 剑指 Offer 04. 二维数组中的查找
  3. 剑指 Offer 05. 替换空格
  4. 剑指 Offer 06. 从尾到头打印链表
  5. 剑指 Offer 07. 重建二叉树
  6. 剑指 Offer 09. 用两个栈实现队列
  7. 剑指 Offer 10- I. 斐波那契数列
  8. 剑指 Offer 10- II. 青蛙跳台阶问题
  9. 剑指 Offer 11. 旋转数组的最小数字
  10. 剑指 Offer 12. 矩阵中的路径
  11. 剑指 Offer 13. 机器人的运动范围
  12. 剑指 Offer 14- I. 剪绳子
  13. 剑指 Offer 14- II. 剪绳子 II
  14. 剑指 Offer 15. 二进制中1的个数
  15. 剑指 Offer 16. 数值的整数次方
  16. 剑指 Offer 17. 打印从1到最大的n位数
  17. 剑指 Offer 18. 删除链表的节点
  18. 剑指 Offer 19. 正则表达式匹配
  19. 剑指 Offer 20. 表示数值的字符串
  20. 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
  21. 剑指 Offer 22. 链表中倒数第k个节点
  22. 剑指 Offer 24. 反转链表
  23. 剑指 Offer 25. 合并两个排序的链表
  24. 剑指 Offer 26. 树的子结构
  25. 剑指 Offer 27. 二叉树的镜像
  26. 剑指 Offer 28. 对称的二叉树
  27. 剑指 Offer 29. 顺时针打印矩阵