推荐|剑指offer所有编程练习总结分析

高质量的题目：牛客剑指Offer题目通常设计精良，考察面试者在数据结构、算法和编程能力等方面的综合能力。
真实面试模拟：这些题目常常是从真实的面试题目中选取，因此做题可以帮助面试者熟悉面试流程和类型，提高应对面试的能力。
广泛覆盖的主题：牛客剑指Offer题目涵盖了很多经典的算法和数据结构，例如数组、链表、树、排序、查找等。这有助于面试者全面复习并加强对这些主题的理解和应用能力。
算法思维培养：通过解决这些题目，面试者能够培养和提升算法思维和问题解决能力，学会分析和优化算法，提高代码的效率和质量。
拓展知识面：牛客剑指Offer题目涉及的知识点不仅限于基础的数据结构和算法，还包括面向对象设计、操作系统、数据库等其他方面的知识，对于拓展面试者的知识面也有一定的帮助。

由于牛客剑指Offer题目经过整理和筛选，是面试备考的经典资源之一，因此它的重要性在面试准备过程中是很高的。做这些题目可以帮助面试者熟悉常见的面试题型、巩固基础知识、提升编程能力，为应对面试提供了很好的准备。然而，还需注意不仅仅局限于做题，理解背后的原理和思想同样重要，以便能够在面试时灵活运用和展示自己的能力。

二、对应题目分析和练习

1.JZ3-数组中重复的数字-(知识点：数组,难度：简单)

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

解题分析

可以利用哈希表或者原地置换的方式来解决这个问题。下面是原地置换的解题思路：

遍历数组nums，对于每个元素nums[i]，将其与索引i对应的元素nums[nums[i]]进行比较：

若nums[i]等于nums[nums[i]]，即找到了重复的数字，返回nums[i]；
否则，将nums[i]与nums[nums[i]]交换，将其放到正确的位置上，继续比较下一个元素。

重复上述步骤，直到找到重复的数字或遍历完整个数组。若遍历完数组仍未找到重复的数字，则返回-1表示没有重复数字。

该解法的时间复杂度为O(n)，空间复杂度为O(1)。

注意：在题目描述中未规定是否可以修改原始数组，因此可以根据实际情况选择是否采用原地置换的方式。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 找出数组中重复的数字。在一个长度为n的数组nums里的所有数字都在0~n-1的范围内。
 * 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
 * 请找出数组中任意一个重复的数字。
 * @date 2023/6/1 23:49
 */
public class FindRepeatNumber {
    /**
     * 可以利用哈希表或者原地置换的方式来解决这个问题。下面是原地置换的解题思路：
     * 遍历数组nums，对于每个元素nums[i]，将其与索引i对应的元素nums[nums[i]]进行比较：
     * •	若nums[i]等于nums[nums[i]]，即找到了重复的数字，返回nums[i]；
     * •	否则，将nums[i]与nums[nums[i]]交换，将其放到正确的位置上，继续比较下一个元素。
     * 重复上述步骤，直到找到重复的数字或遍历完整个数组。若遍历完数组仍未找到重复的数字，则返回-1表示没有重复数字。
     * 该解法的时间复杂度为O(n)，空间复杂度为O(1)。
     */
    public int findRepeatNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            // 数组为空或长度为0，返回-1表示无重复数字
            return -1;
        }
 
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // 当当前元素不等于索引时，需要进行交换
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) {
                    // 当前元素与它应该放置的位置上的元素相等，即找到了重复数字
                    return nums[i];
                }
                // 交换当前元素与它应该放置的位置上的元素
                swap(nums, i, nums[i]);
            }
        }
 
        // 遍历完整个数组仍未找到重复数字，返回-1表示无重复数字
        return -1;
    }
 
    private void swap(int[] nums, int i, int j) {
        // 交换数组中索引为i和索引为j的两个元素
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
 
    public static void main(String[] args) {
        FindRepeatNumber solution = new FindRepeatNumber();
        // 测试输入数组
        int[] nums = {2, 3, 1, 0, 2, 5, 3};
        // 调用方法查找重复数字
        int result = solution.findRepeatNumber(nums);
        // 输出结果
        System.out.println("重复的数字是: " + result);
    }
}

2.JZ4-二维数组中的查找-(知识点：数组,难度：中等)

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

解题分析

可以从二维数组的右上角（或左下角）开始查找，根据目标值与当前元素的大小关系，逐行缩小查找范围。

以右上角为例，假设目标值为target，初始时，将指针定位在右上角的元素arr[row][col]：

若arr[row][col]等于target，说明找到目标值，返回true；
若arr[row][col]大于target，由于当前元素所在列的下方元素都大于当前元素，可以排除当前列，将指针左移一列，即col减1；
若arr[row][col]小于target，由于当前元素所在行的左侧元素都小于当前元素，可以排除当前行，将指针下移一行，即row加1。

重复上述步骤，直到找到目标值或超出二维数组的范围。

该解法的时间复杂度为O(m+n)，其中m为二维数组的行数，n为二维数组的列数。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * @date 2023/6/1  22:53
 */
public class FindNumberIn2DArray {
    /**
     * 可以从二维数组的右上角（或左下角）开始查找，根据目标值与当前元素的大小关系，逐行缩小查找范围。
     * 以右上角为例，假设目标值为target，初始时，将指针定位在右上角的元素arr[row][col]：
     * •	若arr[row][col]等于target，说明找到目标值，返回true；
     * •	若arr[row][col]大于target，由于当前元素所在列的下方元素都大于当前元素，可以排除当前列，将指针左移一列，即col减1；
     * •	若arr[row][col]小于target，由于当前元素所在行的左侧元素都小于当前元素，可以排除当前行，将指针下移一行，即row加1。
     * 重复上述步骤，直到找到目标值或超出二维数组的范围。
     * 该解法的时间复杂度为O(m+n)，其中m为二维数组的行数，n为二维数组的列数。
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            // 矩阵为空，返回false
            return false;
        }
 
        // 矩阵的行数
        int rows = matrix.length;
        // 矩阵的列数
        int cols = matrix[0].length;
 
        int row = 0;
        // 指针初始位置为矩阵的右上角元素
        int col = cols - 1;
 
        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) {
                // 找到目标值，返回true
                return true;
            } else if (matrix[row][col] > target) {
                // 当前元素大于目标值，指针左移一列
                col--;
            } else {
                // 当前元素小于目标值，指针下移一行
                row++;
            }
        }
 
        // 遍历完矩阵仍未找到目标值，返回false
        return false;
    }
 
    public static void main(String[] args) {
        FindNumberIn2DArray solution = new FindNumberIn2DArray();
        // 测试输入二维数组
        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}
        };
        // 测试目标值
        int target = 9;
        // 调用方法查找目标值
        boolean result = solution.findNumberIn2DArray(matrix, target);
        // 输出结果
        System.out.println("是否找到目标值: " + result);
    }
 
}

3.JZ11-旋转数组的最小数字-(知识点：二分,难度：简单)

该题目直接可见数组知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第7题。

4.JZ17-打印从1到最大的n位数-(知识点：数组,难度：简单)

题目描述：打印从1到最大的n位数。题目要求按照从小到大的顺序打印出从1到最大的n位十进制数。

解题分析

最优的解题思路是使用数组模拟大数加法。具体步骤如下：

初始化一个长度为n的数组number，用于存储当前的大数。
通过递归或循环实现对数组number的增加，模拟大数加法。
每次增加时，从数组的最低位开始进行加1操作，然后判断是否产生进位。如果有进位，则将进位传递到更高位。
每次增加完成后，将数组number打印出来。
当数组number的最高位不为9时，继续增加；当最高位为9时，说明已经达到了最大的n位数，停止增加。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 打印从1到最大的n位数。
 * 题目要求按照从小到大的顺序打印出从1到最大的n位十进制数。
 * @date 2023/6/1  00:59
 */
public class PrintNumbers {
    /**
     * 最优的解题思路是使用数组模拟大数加法。具体步骤如下：
     * 1.	初始化一个长度为n的数组number，用于存储当前的大数。
     * 2.	通过递归或循环实现对数组number的增加，模拟大数加法。
     * 3.	每次增加时，从数组的最低位开始进行加1操作，然后判断是否产生进位。如果有进位，则将进位传递到更高位。
     * 4.	每次增加完成后，将数组number打印出来。
     * 5.	当数组number的最高位不为9时，继续增加；当最高位为9时，说明已经达到了最大的n位数，停止增加。
     */
    public void printNumbers(int n) {
        if (n <= 0) {
            return;
        }
        // 初始化长度为n的数组
        int[] number = new int[n];
 
        // 模拟大数加法，直到最大的n位数
        while (!increment(number)) {
            // 打印当前的大数
            printNumber(number);
        }
    }
 
    /**
     * 模拟大数加法
     */
    private boolean increment(int[] number) {
        // 进位标志
        int carry = 0;
 
        for (int i = number.length - 1; i >= 0; i--) {
            // 当前位数与进位的和
            int sum = number[i] + carry;
 
            if (i == number.length - 1) {
                // 最低位数加1
                sum++;
            }
 
            if (sum >= 10) {
                if (i == 0) {
                    // 已经达到最大的n位数，返回true
                    return true;
                }
                // 产生进位，当前位数减去10
                sum -= 10;
                // 设置进位标志
                carry = 1;
            } else {
                // 无进位，进位标志为0
                carry = 0;
            }
            // 更新当前位的值
            number[i] = sum;
        }
 
        return false;
    }
 
    /**
     * 打印当前的大数
     */
    private void printNumber(int[] number) {
        // 是否是前导0
        boolean isBeginning0 = true;
 
        for (int i = 0; i < number.length; i++) {
            if (isBeginning0 && number[i] != 0) {
                // 遇到第一个非0数字，取消前导0标志
                isBeginning0 = false;
            }
 
            if (!isBeginning0) {
                // 打印非0数字
                System.out.print(number[i]);
            }
        }
 
        // 换行
        System.out.println();
    }
 
    public static void main(String[] args) {
        PrintNumbers solution = new PrintNumbers();
 
        // 测试输入n的值
        int n = 3;
 
        // 调用方法打印从1到最大的n位数
        solution.printNumbers(n);
    }
}

5.JZ21-调整数组顺序使奇数位于偶数前面(一)-(知识点：数组,难度：简单)

题目描述：调整数组顺序使奇数位于偶数前面(一)。题目要求将一个整数数组中的奇数全部排在偶数的前面，并保持它们的相对顺序不变。

解题分析

最优的解题思路是使用双指针法。具体步骤如下：

定义两个指针，一个指针left从数组的左侧开始向右移动，另一个指针right从数组的右侧开始向左移动。
当left指针指向偶数而right指针指向奇数时，交换两个指针指向的元素，将奇数放到偶数的前面。
继续移动指针，直到left指针和right指针相遇。
此时，所有的奇数都已经移动到了偶数的前面，并且它们的相对顺序保持不变。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 调整数组顺序使奇数位于偶数前面(一)。
 * 题目要求将一个整数数组中的奇数全部排在偶数的前面，并保持它们的相对顺序不变。
 * @date 2023/6/2  23:04
 */
public class OrderOddEvenArrayI {
    /**
     * 最优的解题思路是使用双指针法。具体步骤如下：
     * 1.	定义两个指针，一个指针left从数组的左侧开始向右移动，另一个指针right从数组的右侧开始向左移动。
     * 2.	当left指针指向偶数而right指针指向奇数时，交换两个指针指向的元素，将奇数放到偶数的前面。
     * 3.	继续移动指针，直到left指针和right指针相遇。
     * 4.	此时，所有的奇数都已经移动到了偶数的前面，并且它们的相对顺序保持不变。
     */
    public void reOrderArray(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
 
        // 左指针
        int left = 0;
        // 右指针
        int right = array.length - 1;
 
        while (left < right) {
            // 移动左指针直到指向偶数
            while (left < right && array[left] % 2 != 0) {
                left++;
            }
 
            // 移动右指针直到指向奇数
            while (left < right && array[right] % 2 == 0) {
                right--;
            }
 
            // 交换左右指针指向的元素
            if (left < right) {
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }
    }
 
    public static void main(String[] args) {
        OrderOddEvenArrayI solution = new OrderOddEvenArrayI();
 
        // 测试输入数组
        int[] array = {1, 2, 3, 4, 5, 6, 7};
 
        // 调用方法调整数组顺序
        solution.reOrderArray(array);
 
        // 输出调整后的数组
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

6.JZ81-调整数组顺序使奇数位于偶数前面(二)-(知识点：数组+排序,难度：中等)

题目描述：调整数组顺序使奇数位于偶数前面(二)。题目要求在原有的奇数位于偶数前面的基础上，要求奇数之间和偶数之间的相对顺序保持不变，并且奇数之间的相对顺序也保持不变。

解题分析

最优的解题思路是使用插入排序的思想。具体步骤如下：

定义一个辅助数组evenArray，用于存放原数组中的偶数。
遍历原数组，将所有偶数按照它们在原数组中的顺序依次存放到evenArray中。
遍历原数组，将所有奇数按照它们在原数组中的顺序依次存放到原数组中的空白位置。
最后将evenArray中的偶数按照它们在evenArray中的顺序依次存放到原数组中剩余的空白位置。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 调整数组顺序使奇数位于偶数前面(二)。
 * 题目要求在原有的奇数位于偶数前面的基础上，
 * 要求奇数之间和偶数之间的相对顺序保持不变，并且奇数之间的相对顺序也保持不变。
 * @date 2023/6/2  23:12
 */
public class OrderOddEvenArrayII {
    /**
     * 最优的解题思路是使用插入排序的思想。具体步骤如下：
     * 1.	定义一个辅助数组evenArray，用于存放原数组中的偶数。
     * 2.	遍历原数组，将所有偶数按照它们在原数组中的顺序依次存放到evenArray中。
     * 3.	遍历原数组，将所有奇数按照它们在原数组中的顺序依次存放到原数组中的空白位置。
     * 4.	最后将evenArray中的偶数按照它们在evenArray中的顺序依次存放到原数组中剩余的空白位置。
     */
    public void reOrderArray(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
 
        // 存放偶数的辅助数组
        int[] evenArray = new int[array.length];
        // 偶数计数
        int evenCount = 0;
 
        // 遍历原数组，将偶数存放到oddArray中
        for (int num : array) {
            if (num % 2 == 0) {
                evenArray[evenCount++] = num;
            }
        }
 
        // 遍历原数组，将奇数按顺序存放到原数组中的空白位置
        // 原数组的索引
        int index = 0;
        for (int num : array) {
            if (num % 2 != 0) {
                array[index++] = num;
            }
        }
 
        // 将oddArray中的偶数按顺序存放到原数组中剩余的空白位置
        for (int i = 0; i < evenCount; i++) {
            array[index++] = evenArray[i];
        }
    }
 
    public static void main(String[] args) {
        OrderOddEvenArrayII solution = new OrderOddEvenArrayII();
 
        // 测试输入数组
        int[] array = {1, 2, 3, 4, 5, 6, 7};
 
        // 调用方法调整数组顺序
        solution.reOrderArray(array);
 
        // 输出调整后的数组
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

7.JZ29-顺时针打印矩阵-(知识点：数组,难度：简单)

题目描述：顺时针打印矩阵。给定一个二维矩阵，按照从外向里以顺时针的顺序依次打印出每一个元素。

解题分析

最优的解题思路是模拟顺时针打印的过程。具体步骤如下：

定义四个变量top、bottom、left、right分别表示当前打印范围的上边界、下边界、左边界和右边界。
进行循环，每次循环打印一圈，即从左到右、从上到下、从右到左、从下到上四个方向。
在每个方向上，按照当前边界的范围依次打印元素。
每次打印完一个方向后，更新边界，继续下一次循环打印下一圈。
循环终止条件是打印的元素数量达到矩阵的总元素数量。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.ArrayList;
 
/**
 * @author yanfengzhang
 * @description 顺时针打印矩阵。
 * 给定一个二维矩阵，按照从外向里以顺时针的顺序依次打印出每一个元素。
 * @date 2023/6/2  23:57
 */
public class PrintMatrix {
    /**
     * 最优的解题思路是模拟顺时针打印的过程。具体步骤如下：
     * 1.	定义四个变量top、bottom、left、right分别表示当前打印范围的上边界、下边界、左边界和右边界。
     * 2.	进行循环，每次循环打印一圈，即从左到右、从上到下、从右到左、从下到上四个方向。
     * 3.	在每个方向上，按照当前边界的范围依次打印元素。
     * 4.	每次打印完一个方向后，更新边界，继续下一次循环打印下一圈。
     * 5.	循环终止条件是打印的元素数量达到矩阵的总元素数量。
     */
    public ArrayList printMatrix(int[][] matrix) {
        ArrayList result = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }
 
        // 矩阵的行数
        int rows = matrix.length;
        // 矩阵的列数
        int cols = matrix[0].length;
        // 上边界
        int top = 0;
        // 下边界
        int bottom = rows - 1;
        // 左边界
        int left = 0;
        // 右边界
        int right = cols - 1;
 
        while (top <= bottom && left <= right) {
            // 从左到右打印一行
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            // 上边界下移
            top++;
 
            // 从上到下打印一列
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            // 右边界左移
            right--;
 
            // 从右到左打印一行
            if (top <= bottom) {
                // 避免重复打印
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                // 下边界上移
                bottom--;
            }
 
            // 从下到上打印一列
            if (left <= right) {
                // 避免重复打印
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                // 左边界右移
                left++;
            }
        }
 
        return result;
    }
 
    public static void main(String[] args) {
        PrintMatrix solution = new PrintMatrix();
 
        // 测试输入矩阵
        int[][] matrix = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
 
        // 调用方法打印矩阵
        ArrayList result = solution.printMatrix(matrix);
 
        // 输出打印结果 1 2 3 6 9 8 7 4 5
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

8.JZ10-斐波那契数列-(知识点：数组+递归+动态规划+快速幂+记忆化搜索,难度：入门)

题目描述：写一个函数，输入 n，求斐波那契数列的第 n 项。

解题分析

斐波那契数列是一个经典的递归问题，可以使用递归、动态规划、快速幂或记忆化搜索等方法来解决。

递归法：

当 n = 0 时，返回 0；
当 n = 1 时，返回 1；
当 n > 1 时，返回斐波那契数列的前两项之和，即 Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)。
这种方法简单易懂，但存在大量的重复计算，效率较低。

动态规划法：

使用一个数组 dp[] 来保存已经计算过的斐波那契数列的结果，初始将 dp[0] 置为 0，dp[1] 置为 1。
从 dp[2] 开始迭代计算，dp[i] = dp[i-1] + dp[i-2]。
最后返回 dp[n] 即为第 n 项的结果。
动态规划法避免了重复计算，时间复杂度为 O(n)，空间复杂度为 O(n)。

快速幂法：

利用矩阵乘法的思想来求解斐波那契数列。
构造矩阵 A = [[1, 1], [1, 0]]，初始矩阵 B = [[1], [0]]。
求 A 的 n 次幂，即 A^n。
结果矩阵为 B = A^n * B，最终返回 B[0][0] 即为第 n 项的结果。
这种方法的时间复杂度为 O(log n)。

记忆化搜索法：

使用一个数组 memo[] 来保存已经计算过的斐波那契数列的结果，初始将 memo[0] 置为 0，memo[1] 置为 1。
在计算第 n 项之前，先检查 memo[n] 是否已经计算过，如果是则直接返回 memo[n]。
否则，计算 memo[n] = Fibonacci(n-1) + Fibonacci(n-2)，并将结果保存在 memo[n] 中。
最后返回 memo[n] 即为第 n 项的结果。
这种方法避免了重复计算，时间复杂度为 O(n)，空间复杂度为 O(n)。

以上是针对斐波那契数列的常见解题思路，根据具体情况选择合适的方法来求解。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 写一个函数，输入 n，求斐波那契数列的第 n 项。
 * @date 2023/6/3  23:02
 */
public class Fibonacci {
    /***
     * 动态规划法：
     * 	•	使用一个数组 dp[] 来保存已经计算过的斐波那契数列的结果，初始将 dp[0] 置为 0，dp[1] 置为 1。
     * 	•	从 dp[2] 开始迭代计算，dp[i] = dp[i-1] + dp[i-2]。
     * 	•	最后返回 dp[n] 即为第 n 项的结果。
     * 	•	动态规划法避免了重复计算，时间复杂度为 O(n)，空间复杂度为 O(n)。
     */
    public int fibonacci(int n) {
        if (n <= 0) {
            return 0;
        }
 
        if (n == 1) {
            return 1;
        }
 
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
 
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
 
        return dp[n];
    }
 
    public static void main(String[] args) {
        Fibonacci solution = new Fibonacci();
 
        // 测试案例1：n = 0
        int result1 = solution.fibonacci(0);
        System.out.println("Fibonacci(0) = " + result1);
 
        // 测试案例2：n = 1
        int result2 = solution.fibonacci(1);
        System.out.println("Fibonacci(1) = " + result2);
 
        // 测试案例3：n = 5
        int result3 = solution.fibonacci(5);
        System.out.println("Fibonacci(5) = " + result3);
 
        // 测试案例4：n = 10
        int result4 = solution.fibonacci(10);
        System.out.println("Fibonacci(10) = " + result4);
    }
}

9.JZ39-数组中出现次数超过一半的数字-(知识点：哈希,难度：简单)

10.JZ45-把数组排成最小的数-(知识点：数组,难度：中等)

题目描述：输入一个非负整数数组，将数组中的数字拼接起来排成一个最小的数。例如，给定数组 [3, 32, 321]，将其拼接成的最小数为 321323。

解题分析

要将数组中的数字拼接成最小的数，可以使用自定义的比较规则进行排序。假设有两个数字 x 和 y，如果将它们按照 xy 和 yx 的方式拼接，若 xy < yx，则将 x 排在 y 前面，否则将 y 排在 x 前面。

具体步骤如下：

将整数数组转换为字符串数组，便于比较和拼接。
使用自定义的比较规则对字符串数组进行排序。比较规则为：若 str1 + str2 < str2 + str1，则将 str1 排在 str2 前面。
将排序后的字符串数组按顺序拼接成一个最小的数。
返回拼接后的最小数。

该方法的时间复杂度为 O(nlogn)，其中 n 为数组的长度。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.Arrays;
import java.util.Comparator;
 
/**
 * @author yanfengzhang
 * @description 输入一个非负整数数组，将数组中的数字拼接起来排成一个最小的数。
 * 例如，给定数组 [3, 32, 321]，将其拼接成的最小数为 321323。
 * @date 2023/6/3  22:05
 */
public class PrintMinNumber {
    /**
     * 要将数组中的数字拼接成最小的数，可以使用自定义的比较规则进行排序。
     * 假设有两个数字 x 和 y，如果将它们按照 xy 和 yx 的方式拼接，
     * 若 xy < yx，则将 x 排在 y 前面，否则将 y 排在 x 前面。
     * 
     * 具体步骤如下：
     * 1.	将整数数组转换为字符串数组，便于比较和拼接。
     * 2.	使用自定义的比较规则对字符串数组进行排序。
     * 比较规则为：若 str1 + str2 < str2 + str1，则将 str1 排在 str2 前面。
     * 3.	将排序后的字符串数组按顺序拼接成一个最小的数。
     * 4.	返回拼接后的最小数。
     * 
     * 该方法的时间复杂度为 O(nlogn)，其中 n 为数组的长度。
     */
    public String printMinNumber(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return "";
        }
 
        // 将整数数组转换为字符串数组
        String[] strs = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            strs[i] = String.valueOf(numbers[i]);
        }
 
        // 自定义比较器进行排序
        Arrays.sort(strs, new Comparator() {
            @Override
            public int compare(String s1, String s2) {
                String str1 = s1 + s2;
                String str2 = s2 + s1;
                return str1.compareTo(str2);
            }
        });
 
        // 拼接排序后的字符串数组
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str);
        }
 
        return sb.toString();
    }
 
    public static void main(String[] args) {
        PrintMinNumber solution = new PrintMinNumber();
 
        // 测试案例1
        int[] numbers1 = {3, 32, 321};
        String result1 = solution.printMinNumber(numbers1);
        System.out.println("PrintMinNumber([3, 32, 321]) = " + result1);
 
        // 测试案例2
        int[] numbers2 = {1, 2, 3, 4, 5};
        String result2 = solution.printMinNumber(numbers2);
        System.out.println("PrintMinNumber([1, 2, 3, 4, 5]) = " + result2);
    }
}

11.JZ47-礼物的最大价值-(知识点：数组+动态规划,难度：中等)

题目描述：在一个 m × n 的棋盘上，每个格子中放着一定数量的礼物，你可以从棋盘的左上角开始，每次向右或向下移动一格，直到到达棋盘的右下角。请计算出经过的路径所能拿到的礼物的最大价值。

解题分析

这是一个典型的动态规划问题。我们可以定义一个二维数组 dp[m][n]，其中 dp[i][j] 表示到达棋盘上第 (i,j) 个格子时能拿到的最大礼物价值。根据题目要求，我们可以得到状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

其中，dp[i-1][j] 表示从上方格子到达当前格子的最大价值，dp[i][j-1] 表示从左方格子到达当前格子的最大价值，grid[i][j] 表示当前格子中的礼物价值。

具体步骤如下：

创建一个大小为 (m+1) × (n+1) 的二维数组 dp，其中 dp[i][j] 表示到达棋盘上第 (i,j) 个格子时能拿到的最大礼物价值。
初始化边界条件，即第一行和第一列的最大礼物价值，dp[0][j] = dp[0][j-1] + grid[0][j] 和 dp[i][0] = dp[i-1][0] + grid[i][0]。
从第二行第二列开始遍历棋盘，根据状态转移方程更新 dp[i][j] 的值。
遍历完整个棋盘后，dp[m][n] 即为到达右下角格子时能拿到的最大礼物价值。

最终，返回 dp[m][n] 即可得到最大礼物价值。

该方法的时间复杂度为 O(m × n)，其中 m 和 n 分别为棋盘的行数和列数。

【注】这里假设棋盘上的礼物价值都为非负数。如果存在负数礼物，需要进行额外的处理。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 在一个 m × n 的棋盘上，
 * 每个格子中放着一定数量的礼物，你可以从棋盘的左上角开始，
 * 每次向右或向下移动一格，直到到达棋盘的右下角。
 * 请计算出经过的路径所能拿到的礼物的最大价值。
 * @date 2023/6/3  22:45
 */
public class GridMaxValue {
    /**
     * 这是一个典型的动态规划问题。我们可以定义一个二维数组 dp[m][n]，其中 dp[i][j] 表示到达棋盘上第 (i,j) 个格子时能拿到的最大礼物价值。根据题目要求，我们可以得到状态转移方程：
     * dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
     * 其中，dp[i-1][j] 表示从上方格子到达当前格子的最大价值，dp[i][j-1] 表示从左方格子到达当前格子的最大价值，grid[i][j] 表示当前格子中的礼物价值。
     * 
     * 具体步骤如下：
     * 1.	创建一个大小为 (m+1) × (n+1) 的二维数组 dp，其中 dp[i][j] 表示到达棋盘上第 (i,j) 个格子时能拿到的最大礼物价值。
     * 2.	初始化边界条件，即第一行和第一列的最大礼物价值，dp[0][j] = dp[0][j-1] + grid[0][j] 和 dp[i][0] = dp[i-1][0] + grid[i][0]。
     * 3.	从第二行第二列开始遍历棋盘，根据状态转移方程更新 dp[i][j] 的值。
     * 4.	遍历完整个棋盘后，dp[m][n] 即为到达右下角格子时能拿到的最大礼物价值。
     * 最终，返回 dp[m][n] 即可得到最大礼物价值。
     * 该方法的时间复杂度为 O(m × n)，其中 m 和 n 分别为棋盘的行数和列数。
     * 【注】这里假设棋盘上的礼物价值都为非负数。如果存在负数礼物，需要进行额外的处理。id
     */
    public int getMaxValue(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
 
        int m = grid.length;
        int n = grid[0].length;
 
        // 创建dp数组
        int[][] dp = new int[m + 1][n + 1];
 
        // 初始化边界条件
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i - 1][0];
        }
 
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j - 1];
        }
 
        // 动态规划计算最大礼物价值
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
 
        return dp[m][n];
    }
 
    public static void main(String[] args) {
        GridMaxValue solution = new GridMaxValue();
 
        int[][] grid = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
 
        int maxValue = solution.getMaxValue(grid);
        // 预期输出: 15
        System.out.println("Max value: " + maxValue);
    }
 
}

12.JZ53-数字在升序数组中出现的次数-(知识点：数组+二分,难度：简单)

题目描述：统计一个数字在升序数组中出现的次数。

解题分析

由于数组是升序的，可以利用二分查找的思路来解决这个问题。

首先使用二分查找找到该数字第一次出现的位置，记为first。如果数组中不存在该数字，直接返回0。如果存在，继续执行下一步。
使用二分查找找到该数字最后一次出现的位置，记为last。
该数字在数组中出现的次数为last - first + 1。

时间复杂度：O(logN)，其中 N 为数组的长度。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 统计一个数字在升序数组中出现的次数。
 * @date 2023/6/3  22:13
 */
public class NumberTimesInSortArray {
    /**
     * 由于数组是升序的，可以利用二分查找的思路来解决这个问题。
     * 1.	首先使用二分查找找到该数字第一次出现的位置，记为first。
     * •	如果数组中不存在该数字，直接返回0。
     * •	如果存在，继续执行下一步。
     * 2.	使用二分查找找到该数字最后一次出现的位置，记为last。
     * 3.	该数字在数组中出现的次数为last - first + 1。
     * 
     * 时间复杂度：O(logN)，其中 N 为数组的长度。
     */
    public int getNumberOfK(int[] array, int k) {
        if (array == null || array.length == 0) {
            return 0;
        }
 
        int first = binarySearchFirst(array, k);
        int last = binarySearchLast(array, k);
 
        if (first == -1 || last == -1) {
            return 0;
        }
 
        return last - first + 1;
    }
 
    private int binarySearchFirst(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
 
        while (left <= right) {
            int mid = left + (right - left) / 2;
 
            if (array[mid] < target) {
                left = mid + 1;
            } else if (array[mid] > target) {
                right = mid - 1;
            } else {
                if (mid == 0 || array[mid - 1] != target) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            }
        }
 
        return -1;
    }
 
    private int binarySearchLast(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
 
        while (left <= right) {
            int mid = left + (right - left) / 2;
 
            if (array[mid] < target) {
                left = mid + 1;
            } else if (array[mid] > target) {
                right = mid - 1;
            } else {
                if (mid == array.length - 1 || array[mid + 1] != target) {
                    return mid;
                } else {
                    left = mid + 1;
                }
            }
        }
 
        return -1;
    }
 
    public static void main(String[] args) {
        NumberTimesInSortArray solution = new NumberTimesInSortArray();
 
        int[] array = {1, 2, 3, 3, 3, 4, 5};
        int k = 3;
        int count = solution.getNumberOfK(array, k);
        // 预期输出: 3
        System.out.println("Count: " + count);
    }
 
}

13.JZ49-丑数-(知识点：基础数学+二分,难度：中等)

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

解题分析

要找到第 N 个丑数，我们可以从 1 开始逐个判断每个数是否是丑数。一个数 num 如果满足 num = 2^i * 3^j * 5^k，其中 i、j 和 k 都是非负整数，那么 num 就是丑数。

基于这个思路，我们可以使用动态规划来解决。我们创建一个数组 ugly 来保存已经找到的丑数，初始化 ugly[0] = 1，然后我们从 1 开始遍历，每次选择 ugly 中的数乘以 2、3 和 5 中的最小值，作为下一个丑数，同时更新对应的指针。具体步骤如下：

创建一个长度为 N 的数组 ugly，并初始化 ugly[0] = 1。
创建三个指针 p2、p3 和 p5，分别初始化为 0，表示下一个丑数应该乘以 2、3 和 5。
从 1 开始遍历到 N-1，每次选择 ugly[p2] * 2、ugly[p3] * 3 和 ugly[p5] * 5 中的最小值作为下一个丑数，并更新对应的指针：• 如果 ugly[p2] * 2 是最小值，则递增 p2。• 如果 ugly[p3] * 3 是最小值，则递增 p3。• 如果 ugly[p5] * 5 是最小值，则递增 p5。
返回 ugly[N-1]，即第 N 个丑数。

这种方法的时间复杂度为 O(N)，空间复杂度为 O(N)。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。
 * 求按从小到大的顺序的第 N 个丑数。
 * @date 2023/6/3  22:25
 */
public class UglyNumber {
    /**
     * 要找到第 N 个丑数，我们可以从 1 开始逐个判断每个数是否是丑数。
     * 一个数 num 如果满足 num = 2^i * 3^j * 5^k，其中 i、j 和 k 都是非负整数，那么 num 就是丑数。
     * 基于这个思路，我们可以使用动态规划来解决。
     * 我们创建一个数组 ugly 来保存已经找到的丑数，初始化 ugly[0] = 1，
     * 然后我们从 1 开始遍历，每次选择 ugly 中的数乘以 2、3 和 5 中的最小值，
     * 作为下一个丑数，同时更新对应的指针。具体步骤如下：
     * 1.	创建一个长度为 N 的数组 ugly，并初始化 ugly[0] = 1。
     * 2.	创建三个指针 p2、p3 和 p5，分别初始化为 0，表示下一个丑数应该乘以 2、3 和 5。
     * 3.	从 1 开始遍历到 N-1，每次选择 ugly[p2] * 2、ugly[p3] * 3 和 ugly[p5] * 5 中的最小值作为下一个丑数，并更新对应的指针：
     * •	如果 ugly[p2] * 2 是最小值，则递增 p2。
     * •	如果 ugly[p3] * 3 是最小值，则递增 p3。
     * •	如果 ugly[p5] * 5 是最小值，则递增 p5。
     * 4.	返回 ugly[N-1]，即第 N 个丑数。
     * 这种方法的时间复杂度为 O(N)，空间复杂度为 O(N)。
     */
    public int getUglyNumber(int index) {
        if (index <= 0) {
            return 0;
        }
 
        int[] ugly = new int[index];
        ugly[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
 
        for (int i = 1; i < index; i++) {
            int min = Math.min(ugly[p2] * 2, Math.min(ugly[p3] * 3, ugly[p5] * 5));
            ugly[i] = min;
 
            if (ugly[p2] * 2 == min) {
                p2++;
            }
            if (ugly[p3] * 3 == min) {
                p3++;
            }
            if (ugly[p5] * 5 == min) {
                p5++;
            }
        }
 
        return ugly[index - 1];
    }
 
    public static void main(String[] args) {
        UglyNumber solution = new UglyNumber();
 
        // 验证例子: 获取第 10 个丑数
        int index = 10;
        int result = solution.getUglyNumber(index);
        System.out.println("第 " + index + " 个丑数为: " + result);
    }
 
}

14.JZ51-数组中的逆序对-(知识点：数组+归并,难度：中等)

题目描述：在一个数组中，前面的数字比后面的数字大的情况下，将这样的数字对称为一个逆序对。求出数组中逆序对的总数。

解题分析

可以利用归并排序的思想来解决这个问题。归并排序的过程中，将两个有序的子数组合并成一个有序的数组时，可以统计逆序对的个数。具体步骤如下：

将原数组不断二分，直到划分成只有一个元素的子数组。
将相邻的两个子数组合并，合并的过程中统计逆序对的个数。
将合并后的子数组继续合并，直到最终合并成一个完整的有序数组。
返回逆序对的总数。

时间复杂度为 O(nlogn)，其中 n 为数组的长度。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 在一个数组中，前面的数字比后面的数字大的情况下，将这样的数字对称为一个逆序对。
 * 求出数组中逆序对的总数。
 * @date 2023/6/3  22:30
 */
public class InversePairs {
    // 逆序对的计数器
    private int count;
 
    /**
     * 可以利用归并排序的思想来解决这个问题。归并排序的过程中，将两个有序的子数组合并成一个有序的数组时，可以统计逆序对的个数。具体步骤如下：
     * 1.	将原数组不断二分，直到划分成只有一个元素的子数组。
     * 2.	将相邻的两个子数组合并，合并的过程中统计逆序对的个数。
     * 3.	将合并后的子数组继续合并，直到最终合并成一个完整的有序数组。
     * 4.	返回逆序对的总数。
     * 时间复杂度为 O(nlogn)，其中 n 为数组的长度。
     */
    public int inversePairs(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
 
        mergeSort(array, 0, array.length - 1);
 
        return count;
    }
 
    private void mergeSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
 
        int mid = (start + end) / 2;
        mergeSort(array, start, mid);
        mergeSort(array, mid + 1, end);
        merge(array, start, mid, end);
    }
 
    private void merge(int[] array, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start, p2 = mid + 1;
        int index = 0;
 
        while (p1 <= mid && p2 <= end) {
            if (array[p1] <= array[p2]) {
                temp[index++] = array[p1++];
            } else {
                temp[index++] = array[p2++];
                // 统计逆序对个数
                count += mid - p1 + 1;
            }
        }
 
        while (p1 <= mid) {
            temp[index++] = array[p1++];
        }
 
        while (p2 <= end) {
            temp[index++] = array[p2++];
        }
 
        System.arraycopy(temp, 0, array, start, temp.length);
    }
 
    public static void main(String[] args) {
        InversePairs solution = new InversePairs();
 
        // 验证例子: 数组 {7, 5, 6, 4} 中的逆序对个数
        int[] array = {7, 5, 6, 4};
        int result = solution.inversePairs(array);
        System.out.println("数组中的逆序对个数为: " + result);
    }
 
}

15.JZ66-构建乘积数组-(知识点：数组,难度：简单)

题目描述：给定一个数组 A[0,1,...,n-1]，请构建一个数组 B[0,1,...,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的所有元素的乘积。不能使用除法。

解题分析

可以将数组 B 看作两部分的乘积，即左边部分和右边部分的乘积。首先计算数组 B 中的左边部分乘积，然后再计算右边部分乘积。具体步骤如下：

初始化结果数组 B，长度为 n，并初始化为全 1。
计算左边部分的乘积。从左往右遍历数组 A，累乘每个元素并更新 B 中对应的位置，即 B[i] *= A[i-1]。
计算右边部分的乘积。从右往左遍历数组 A，累乘每个元素并更新 B 中对应的位置，即 B[i] *= A[i+1]。
返回最终的结果数组 B。

这样，数组 B 中的每个元素就是数组 A 中除了对应位置元素之外的所有元素的乘积。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.Arrays;
 
/**
 * @author yanfengzhang
 * @description 给定一个数组 A[0,1,...,n-1]，
 * 请构建一个数组 B[0,1,...,n-1]，
 * 其中 B[i] 的值是数组 A 中除了下标 i 以外的所有元素的乘积。
 * 不能使用除法。
 * @date 2023/6/4  22:34
 */
public class MultiplyArray {
    /**
     * 可以将数组 B 看作两部分的乘积，即左边部分和右边部分的乘积。
     * 首先计算数组 B 中的左边部分乘积，然后再计算右边部分乘积。具体步骤如下：
     * 1.	初始化结果数组 B，长度为 n，并初始化为全 1。
     * 2.	计算左边部分的乘积。从左往右遍历数组 A，累乘每个元素并更新 B 中对应的位置，即 B[i] *= A[i-1]。
     * 3.	计算右边部分的乘积。从右往左遍历数组 A，累乘每个元素并更新 B 中对应的位置，即 B[i] *= A[i+1]。
     * 4.	返回最终的结果数组 B。
     * 这样，数组 B 中的每个元素就是数组 A 中除了对应位置元素之外的所有元素的乘积。
     */
    public static int[] multiply(int[] A) {
        int length = A.length;
        int[] B = new int[length];
 
        // 计算左边部分的乘积
        B[0] = 1;
        for (int i = 1; i < length; i++) {
            B[i] = B[i - 1] * A[i - 1];
        }
 
        // 计算右边部分的乘积并与左边部分相乘
        int temp = 1;
        for (int i = length - 2; i >= 0; i--) {
            temp *= A[i + 1];
            B[i] *= temp;
        }
 
        return B;
    }
 
    public static void main(String[] args) {
        int[] A = {1, 2, 3, 4, 5};
        int[] B = multiply(A);
        System.out.println(Arrays.toString(B));
    }
 
}

16.JZ42-连续子数组的最大和-(知识点：贪心+动态规划,难度：简单)

题目描述：输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)。

解题分析

这是一个经典的动态规划问题。我们定义两个变量：maxSum 用于记录当前的最大子数组和，curSum 用于记录当前的子数组和。

我们遍历数组，对于每个元素，有两种情况：

如果 curSum 加上当前元素后仍然大于当前元素本身，说明当前元素属于当前的子数组，我们更新 curSum。
如果 curSum 加上当前元素后小于当前元素本身，说明当前元素是新的子数组的起点，我们将 curSum 更新为当前元素，并比较 curSum 和 maxSum，更新 maxSum。

最后返回 maxSum 即可得到最大子数组的和。

【注意】需要注意处理数组为空的情况，可以在开始时将 maxSum 和 curSum 初始化为数组的第一个元素。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。
 * 求所有子数组的和的最大值。要求时间复杂度为 O(n)。
 * @date 2023/6/4  22:39
 */
public class FindGreatestSumOfSubArray {
    /**
     * 这是一个经典的动态规划问题。我们定义两个变量：maxSum 用于记录当前的最大子数组和，curSum 用于记录当前的子数组和。
     * 我们遍历数组，对于每个元素，有两种情况：
     * 1.	如果 curSum 加上当前元素后仍然大于当前元素本身，说明当前元素属于当前的子数组，我们更新 curSum。
     * 2.	如果 curSum 加上当前元素后小于当前元素本身，说明当前元素是新的子数组的起点，
     * 我们将 curSum 更新为当前元素，并比较 curSum 和 maxSum，更新 maxSum。
     * 最后返回 maxSum 即可得到最大子数组的和。
     * 【注意】需要注意处理数组为空的情况，可以在开始时将 maxSum 和 curSum 初始化为数组的第一个元素。
     */
    public int findGreatestSumOfSubArray(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
 
        // 记录当前的最大子数组和
        int maxSum = array[0];
        // 记录当前的子数组和
        int curSum = array[0];
 
        for (int i = 1; i < array.length; i++) {
            if (curSum + array[i] > array[i]) {
                // 如果当前子数组和加上当前元素后仍然大于当前元素本身，说明当前元素属于当前的子数组
                curSum += array[i];
            } else {
                // 如果当前子数组和加上当前元素后小于当前元素本身，说明当前元素是新的子数组的起点
                // 更新当前子数组和为当前元素，并比较更新最大子数组和
                curSum = array[i];
            }
 
            if (curSum > maxSum) {
                // 比较更新最大子数组和
                maxSum = curSum;
            }
        }
 
        return maxSum;
    }
 
    public static void main(String[] args) {
        FindGreatestSumOfSubArray solution = new FindGreatestSumOfSubArray();
 
        int[] array1 = {1, -2, 3, 10, -4, 7, 2, -5};
        int result1 = solution.findGreatestSumOfSubArray(array1);
        // Expected output: 18
        System.out.println("Result 1: " + result1);
 
        int[] array2 = {-2, -3, -1, -4, -6};
        int result2 = solution.findGreatestSumOfSubArray(array2);
        // Expected output: -1
        System.out.println("Result 2: " + result2);
 
        int[] array3 = {1, 2, 3, 4, 5};
        int result3 = solution.findGreatestSumOfSubArray(array3);
        // Expected output: 15
        System.out.println("Result 3: " + result3);
    }
}

17.JZ85-a = b + c 的所有可能的组合-(知识点：回溯,难度：中等)

题目描述：给定一个整数 n，求满足 a = b + c 的所有可能的组合，其中 a、b、c 均为 n 位数，且 a、b、c 均由数字集合 {1, 2, …, 9} 中的数字组成。要求找出所有满足条件的 a=b+c 的组合。

解题分析

我们可以使用回溯法来解决这个问题。回溯法是一种通过不断地尝试可能的解决方案，并在不满足条件时回退的方法。

具体的解法如下：

定义一个递归函数，参数包括当前正在生成的数字 a、当前位数 cur、已经选择的数字集合 usedNums、结果集合 result。
在递归函数中，首先判断当前位数 cur 是否为 n，如果是，则判断 a 是否满足条件 a = b + c，如果满足则将 a 加入结果集合 result。
如果当前位数 cur 小于 n，则遍历数字集合 {1, 2, …, 9}，对于每个数字 num，如果 num 没有被使用过，则将其加入已经选择的数字集合 usedNums，然后递归调用函数生成下一位数的数字。
在递归调用返回后，需要将 num 从已经选择的数字集合 usedNums 中移除，以便生成其他可能的组合。
最后，返回结果集合 result。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
/**
 * @author yanfengzhang
 * @description 给定一个整数 n，求满足 a = b + c 的所有可能的组合，
 * 其中 a、b、c 均为 n 位数，且 a、b、c 均由数字集合 {1, 2, …, 9} 中的数字组成。
 * 要求找出所有满足条件的 a=b+c 的组合。
 * @date 2023/5/15  23:07
 */
public class ABCCombinations {
 
    /**
     * 我们可以使用回溯法来解决这个问题。回溯法是一种通过不断地尝试可能的解决方案，并在不满足条件时回退的方法。
     * 
     * 具体的解法如下：
     * 
     * 1.	定义一个递归函数，参数包括当前正在生成的数字 a、当前位数 cur、已经选择的数字集合 usedNums、结果集合 result。
     * 2.	在递归函数中，首先判断当前位数 cur 是否为 n，如果是，则判断 a 是否满足条件 a = b + c，如果满足则将 a 加入结果集合 result。
     * 3.	如果当前位数 cur 小于 n，则遍历数字集合 {1, 2, …, 9}，对于每个数字 num，如果 num 没有被使用过，则将其加入已经选择的数字集合 usedNums，然后递归调用函数生成下一位数的数字。
     * 4.	在递归调用返回后，需要将 num 从已经选择的数字集合 usedNums 中移除，以便生成其他可能的组合。
     * 5.	最后，返回结果集合 result。
     *
     * @param n
     * @return
     */
    public static List<int[]> findCombinations(int n) {
        // 用于存储满足条件的组合结果
        List<int[]> result = new ArrayList<>();
        // 已经使用的数字集合
        Set usedNums = new HashSet<>();
        // 调用递归函数生成组合
        generateCombinations(0, n, usedNums, result);
        return result;
    }
 
    private static void generateCombinations(int cur, int n, Set usedNums, List<int[]> result) {
        if (cur == n) {
            // 生成数字 a
            int a = concatenateDigits(usedNums);
            // 找到满足条件的 b 和 c
            int[] bc = findBC(a);
            if (bc[0] != -1 && bc[1] != -1) {
                // 将组合加入结果集合
                result.add(new int[]{a, bc[0], bc[1]});
            }
            return;
        }
 
        for (int num = 1; num <= 9; num++) {
            if (!usedNums.contains(num)) {
                // 将数字加入已使用集合
                usedNums.add(num);
                // 递归生成下一位数的数字
                generateCombinations(cur + 1, n, usedNums, result);
                // 回溯，将数字从已使用集合中移除，尝试其他可能的组合
                usedNums.remove(num);
            }
        }
    }
 
    private static int concatenateDigits(Set digits) {
        int result = 0;
        for (int digit : digits) {
            // 拼接数字
            result = result * 10 + digit;
        }
        return result;
    }
 
    private static int[] findBC(int a) {
        int[] bc = new int[2];
        // 初始化 b 为 -1
        bc[0] = -1;
        // 初始化 c 为 -1
        bc[1] = -1;
 
        for (int b = 1; b < a; b++) {
            int c = a - b;
            if (isValid(b) && isValid(c)) {
                bc[0] = b;
                bc[1] = c;
                break;
            }
        }
 
        return bc;
    }
 
    private static boolean isValid(int num) {
        Set digits = new HashSet<>();
        while (num > 0) {
            int digit = num % 10;
            if (digits.contains(digit)) {
                // 数字重复，不满足条件
                return false;
            }
            digits.add(digit);
            num /= 10;
        }
        // 数字不重复，满足条件
        return true;
    }
 
    public static void main(String[] args) {
        int n = 3;
        List<int[]> combinations = findCombinations(n);
        for (int[] combination : combinations) {
            int a = combination[0];
            int b = combination[1];
            int c = combination[2];
            // 输出满足条件的组合
            System.out.println(a + " = " + b + " + " + c);
        }
    }
}

18.JZ56-数组中只出现一次的两个数字-(知识点：哈希+位运算,难度：中等)

题目描述：给定一个整数数组nums，其中除两个数字之外，其他数字都出现了两次。请找出这两个只出现一次的数字。要求时间复杂度为O(n)，空间复杂度为O(1)。

解题分析

最优解题思路：

首先，我们知道如果只有一个数字只出现一次，而其他数字都出现了两次，那么可以使用异或运算来找到该数字。因为相同的数字异或运算结果为0，而任何数字与0异或运算结果为其本身。
对于这个问题，我们要找到两个只出现一次的数字，我们可以将所有数字进行异或运算，得到的结果为这两个数字的异或结果。假设为result。
因为result不为0，所以至少存在一位上为1。我们可以找到result中第一个为1的位的位置，记为第n位。
根据第n位是否为1，将数组中的数字分成两组：一组第n位为1，一组第n位为0。这样两个只出现一次的数字就被分配到了不同的组中。
对于每个组内的数字，再次使用异或运算，最终得到的两个结果就是我们要找的两个只出现一次的数字。

通过上述步骤，我们可以找到数组中只出现一次的两个数字。

请注意，题目没有要求按照特定的顺序返回这两个数字，所以返回顺序可以任意。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.Arrays;
 
/**
 * @author yanfengzhang
 * @description 给定一个整数数组nums，其中除两个数字之外，其他数字都出现了两次。
 * 请找出这两个只出现一次的数字。
 * 要求时间复杂度为O(n)，空间复杂度为O(1)。
 * @date 2023/6/4  23:35
 */
public class FindNumsAppearOnce {
    /**
     * 最优解题思路：
     * 1.	首先，我们知道如果只有一个数字只出现一次，而其他数字都出现了两次，那么可以使用异或运算来找到该数字。
     * 因为相同的数字异或运算结果为0，而任何数字与0异或运算结果为其本身。
     * 2.	对于这个问题，我们要找到两个只出现一次的数字，我们可以将所有数字进行异或运算，得到的结果为这两个数字的异或结果。假设为result。
     * 3.	因为result不为0，所以至少存在一位上为1。我们可以找到result中第一个为1的位的位置，记为第n位。
     * 4.	根据第n位是否为1，将数组中的数字分成两组：一组第n位为1，一组第n位为0。这样两个只出现一次的数字就被分配到了不同的组中。
     * 5.	对于每个组内的数字，再次使用异或运算，最终得到的两个结果就是我们要找的两个只出现一次的数字。
     * 通过上述步骤，我们可以找到数组中只出现一次的两个数字。
     * 请注意，题目没有要求按照特定的顺序返回这两个数字，所以返回顺序可以任意。
     */
    public void findNumsAppearOnce(int[] nums, int[] num1, int[] num2) {
        if (nums == null || nums.length < 2) {
            return;
        }
 
        int xorResult = 0;
        for (int num : nums) {
            xorResult ^= num;
        }
 
        // 找到结果中第一个为1的位
        int firstBit = findFirstBitIs1(xorResult);
 
        // 将数组分成两组进行异或运算
        for (int num : nums) {
            if (isBit1(num, firstBit)) {
                num1[0] ^= num;
            } else {
                num2[0] ^= num;
            }
        }
    }
 
    /**
     * 找到结果中第一个为1的位
     */
    private int findFirstBitIs1(int num) {
        int indexBit = 0;
        while ((num & 1) == 0) {
            num >>= 1;
            indexBit++;
        }
        return indexBit;
    }
 
    /**
     * 判断数字num的第indexBit位是否为1
     */
    private boolean isBit1(int num, int indexBit) {
        num >>= indexBit;
        return (num & 1) == 1;
    }
 
    public static void main(String[] args) {
        FindNumsAppearOnce solution = new FindNumsAppearOnce();
        int[] nums = {2, 4, 3, 6, 3, 2, 5, 5};
        int[] num1 = new int[1];
        int[] num2 = new int[1];
        solution.findNumsAppearOnce(nums, num1, num2);
        // 输出 [4]
        System.out.println(Arrays.toString(num1));
        // 输出 [6]
        System.out.println(Arrays.toString(num2));
    }
 
}

19.JZ57-和为S的两个数字-(知识点：数组+双指针,难度：中等)

该题目直接可见数组知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第1题。

20.JZ5-替换空格-(知识点：字符串,难度：简单)

题目描述：请实现一个函数，将一个字符串中的每个空格替换成 “%20”。例如，当字符串为 “We Are Happy” 时，替换后的字符串应为 “We%20Are%20Happy”。

解题分析

要替换字符串中的空格，可以遍历字符串的每个字符，当遇到空格时，将其替换为 “%20”。由于替换后的字符串长度会增加，所以可以先遍历一次字符串，统计出空格的个数，然后计算出替换后的字符串的长度。接下来从字符串末尾开始遍历，依次将字符复制到替换后的位置上，当遇到空格时，替换为 “%20”。最后得到的字符串即为替换后的结果。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 请实现一个函数，将一个字符串中的每个空格替换成 “%20”。
 * 例如，当字符串为 “We Are Happy” 时，替换后的字符串应为 “We%20Are%20Happy”。
 * @date 2023/6/4  23:40
 */
public class StrReplaceSpace {
    /**
     * 要替换字符串中的空格，可以遍历字符串的每个字符，当遇到空格时，将其替换为 “%20”。
     * 由于替换后的字符串长度会增加，所以可以先遍历一次字符串，统计出空格的个数，
     * 然后计算出替换后的字符串的长度。接下来从字符串末尾开始遍历，
     * 依次将字符复制到替换后的位置上，当遇到空格时，替换为 “%20”。
     * 最后得到的字符串即为替换后的结果。
     */
    public String replaceSpace(StringBuffer str) {
        if (str == null) {
            return null;
        }
 
        // 原始字符串的长度
        int originalLength = str.length();
        // 空格的个数
        int spaceCount = 0;
 
        // 统计空格的个数
        for (int i = 0; i < originalLength; i++) {
            if (str.charAt(i) == ' ') {
                spaceCount++;
            }
        }
 
        // 替换后的字符串的长度
        int newLength = originalLength + spaceCount * 2;
        // 替换后字符串的末尾索引
        int newIndex = newLength - 1;
 
        // 设置字符串的新长度
        str.setLength(newLength);
 
        // 从原字符串的末尾开始遍历，将字符复制到替换后的位置上
        for (int i = originalLength - 1; i >= 0; i--) {
            char c = str.charAt(i);
            if (c == ' ') {
                str.setCharAt(newIndex--, '0');
                str.setCharAt(newIndex--, '2');
                str.setCharAt(newIndex--, '%');
            } else {
                str.setCharAt(newIndex--, c);
            }
        }
 
        return str.toString();
    }
 
    public static void main(String[] args) {
        StrReplaceSpace solution = new StrReplaceSpace();
        StringBuffer str = new StringBuffer("We Are Happy");
        String result = solution.replaceSpace(str);
        // 输出 "We%20Are%20Happy"
        System.out.println(result);
    }
 
}

21.JZ19-正则表达式匹配-(知识点：字符串,难度：较难)

题目描述：请实现一个函数用来匹配包含’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’’表示它前面的字符可以出现任意次（包含0次）。本题中，匹配是指字符串的所有字符匹配整个模式。

解题分析

我们可以使用动态规划的方法来解决这个问题。

定义一个二维布尔数组dp，其中dp[i][j]表示字符串的前i个字符和模式的前j个字符是否匹配。初始化dp[0][0]为true，表示空字符串和空模式是匹配的。然后进行状态转移，分为以下几种情况：

当模式的第j个字符不是’*’时，如果字符串的第i个字符和模式的第j个字符匹配，即s[i] == p[j]或p[j] == ‘.’，那么只需判断前i-1个字符和前j-1个字符是否匹配，即dp[i][j] = dp[i-1][j-1]。
当模式的第j个字符是’*’时，表示它前面的字符可以出现任意次数（包括0次）。此时有两种情况：’‘前面的字符不匹配字符串的当前字符，即s[i] != p[j-1]，那么只能让’’前面的字符出现0次，所以将模式向后移动两个字符，即dp[i][j] = dp[i][j-2]。 ’’前面的字符匹配字符串的当前字符，即s[i] == p[j-1]或p[j-1] == ‘.’。那么有两种选择：一种是让’‘前面的字符出现0次，所以将模式向后移动两个字符，即dp[i][j] = dp[i][j-2]；另一种是让’*’前面的字符出现多次，所以将字符串向后移动一个字符，即dp[i][j] = dp[i-1][j]。

最终结果保存在dp[m][n]中，其中m和n分别是字符串和模式的长度。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 请实现一个函数用来匹配包含’.‘和’‘的正则表达式。
 * 模式中的字符’.‘表示任意一个字符，而’’表示它前面的字符可以出现任意次（包含0次）。
 * 本题中，匹配是指字符串的所有字符匹配整个模式。
 * @date 2023/6/4  00:43
 */
public class StrMatch {
    /**
     * 我们可以使用动态规划的方法来解决这个问题。
     * 定义一个二维布尔数组dp，其中dp[i][j]表示字符串的前i个字符和模式的前j个字符是否匹配。
     * 初始化dp[0][0]为true，表示空字符串和空模式是匹配的。然后进行状态转移，分为以下几种情况：
     * 1.	当模式的第j个字符不是’*’时，如果字符串的第i个字符和模式的第j个字符匹配，
     * 即s[i] == p[j]或p[j] == ‘.’，那么只需判断前i-1个字符和前j-1个字符是否匹配，即dp[i][j] = dp[i-1][j-1]。
     * 2.	当模式的第j个字符是’*’时，表示它前面的字符可以出现任意次数（包括0次）。此时有两种情况：
     * •	’‘前面的字符不匹配字符串的当前字符，即s[i] != p[j-1]，那么只能让’’前面的字符出现0次，
     * 所以将模式向后移动两个字符，即dp[i][j] = dp[i][j-2]。
     * •	’’前面的字符匹配字符串的当前字符，即s[i] == p[j-1]或p[j-1] == ‘.’。
     * 那么有两种选择：一种是让’‘前面的字符出现0次，所以将模式向后移动两个字符，即dp[i][j] = dp[i][j-2]；
     * 另一种是让’*’前面的字符出现多次，所以将字符串向后移动一个字符，即dp[i][j] = dp[i-1][j]。
     * 最终结果保存在dp[m][n]中，其中m和n分别是字符串和模式的长度。
     */
    public boolean match(char[] str, char[] pattern) {
        // 字符串的长度
        int m = str.length;
        // 模式的长度
        int n = pattern.length;
        // dp数组用于保存匹配结果，默认值为false
        boolean[][] dp = new boolean[m + 1][n + 1];
        // 空字符串和空模式匹配为true
        dp[0][0] = true;
 
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (pattern[j - 1] != '*') {
                    // 当前模式字符不是'*'
                    if (i > 0 && (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')) {
                        // 当前字符串字符和模式字符匹配，则结果取决于前一个字符的匹配结果
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    // 当前模式字符是'*'
                    if (j >= 2) {
                        // 忽略当前模式字符和'*'，即跳过'*'
                        dp[i][j] |= dp[i][j - 2];
                    }
                    if (i >= 1 && j >= 2 && (str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.')) {
                        // 字符串字符和模式'*'前的字符匹配，则结果取决于前一个字符串的匹配结果
                        dp[i][j] |= dp[i - 1][j];
                    }
                }
            }
        }
 
        // 返回字符串和模式是否匹配的结果
        return dp[m][n];
    }
 
    public static void main(String[] args) {
        StrMatch solution = new StrMatch();
        // 测试用例字符串
        char[] str = "aab".toCharArray();
        // 测试用例模式
        char[] pattern = "c*a*b".toCharArray();
        // 调用match函数进行匹配
        boolean result = solution.match(str, pattern);
        // 输出匹配结果，true表示匹配成功，false表示匹配失败
        System.out.println(result);
    }
 
}

22.JZ20-表示数值的字符串-(知识点：字符串,难度：较难)

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

例如，字符串”+100”、“5e2”、”-123”、“3.1416”、”-1E-16”都表示数值，但”12e”、“1a3.14”、“1.2.3”、”+-5”以及”12e+5.4”都不是。

解题分析

根据题目要求，我们需要判断给定的字符串是否能够表示数值。为了实现这个功能，我们可以使用有限状态自动机（Finite State Machine）的思想。我们需要定义多个状态，并根据当前字符和状态转移条件来更新状态，最终判断是否能够到达接受状态。

具体的状态定义和转移条件如下：

定义以下9种状态：起始空格、符号位、整数部分、小数点、小数部分、字符e、指数符号、指数整数部分、末尾空格。
定义以下4种字符类型：数字、正负号、小数点、字符e。
根据字符类型和当前状态，定义状态转移规则，更新当前状态。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
 * 例如，字符串”+100”、“5e2”、”-123”、“3.1416”、”-1E-16”都表示数值，
 * 但”12e”、“1a3.14”、“1.2.3”、”+-5”以及”12e+5.4”都不是。
 * @date 2023/6/4  23:47
 */
public class StriIsNumeric {
    /**
     * 根据题目要求，我们需要判断给定的字符串是否能够表示数值。
     * 为了实现这个功能，我们可以使用有限状态自动机（Finite State Machine）的思想。
     * 我们需要定义多个状态，并根据当前字符和状态转移条件来更新状态，最终判断是否能够到达接受状态。
     * 
     * 具体的状态定义和转移条件如下：
     * 1.	定义以下9种状态：起始空格、符号位、整数部分、小数点、小数部分、字符e、指数符号、指数整数部分、末尾空格。
     * 2.	定义以下4种字符类型：数字、正负号、小数点、字符e。
     * 3.	根据字符类型和当前状态，定义状态转移规则，更新当前状态。
     */
    public boolean isNumeric(char[] str) {
        if (str == null || str.length == 0) {
            return false;
        }
 
        // 当前字符索引
        int index = 0;
        // 字符串长度
        int len = str.length;
 
        // 跳过起始的空格
        while (index < len && str[index] == ' ') {
            index++;
        }
 
        // 判断符号位
        if (index < len && (str[index] == '+' || str[index] == '-')) {
            index++;
        }
 
        // 判断整数部分
        boolean isNumeric = scanDigits(str, index, len);
 
        // 判断小数部分
        if (index < len && str[index] == '.') {
            index++;
            // 小数部分可以没有整数部分，因此使用 || 进行判断
            isNumeric = scanDigits(str, index, len) || isNumeric;
        }
 
        // 判断指数部分
        if (index < len && (str[index] == 'e' || str[index] == 'E')) {
            index++;
            // 指数部分必须有整数部分，因此使用 && 进行判断
            isNumeric = isNumeric && scanExponent(str, index, len);
        }
 
        // 跳过末尾的空格
        while (index < len && str[index] == ' ') {
            index++;
        }
 
        // 如果所有字符都被处理并且符合数值的规则，则返回true
        return isNumeric && index == len;
    }
 
    // 判断是否是数字
    private boolean scanDigits(char[] str, int index, int len) {
        while (index < len && str[index] >= '0' && str[index] <= '9') {
            index++;
        }
 
        return index > 0 && index <= len;
    }
 
    // 判断指数部分
    private boolean scanExponent(char[] str, int index, int len) {
        // 判断指数部分的符号位
        if (index < len && (str[index] == '+' || str[index] == '-')) {
            index++;
        }
 
        // 判断指数部分的整数部分
        boolean hasDigits = scanDigits(str, index, len);
 
        // 如果指数部分存在整数部分，则返回true
        return hasDigits && index == len;
    }
 
    public static void main(String[] args) {
        StriIsNumeric solution = new StriIsNumeric();
 
        // 验证示例测试用例
        char[] str1 = {'+', '1', '0', '0'};
        // 应输出true
        System.out.println(solution.isNumeric(str1));
 
        char[] str2 = {'5', 'e', '2'};
        // 应输出true
        System.out.println(solution.isNumeric(str2));
 
        char[] str3 = {'-', '1', '2', '3'};
        // 应输出true
        System.out.println(solution.isNumeric(str3));
 
        char[] str4 = {'3', '.', '1', '4', '1', '6'};
        // 应输出true
        System.out.println(solution.isNumeric(str4));
 
        char[] str5 = {'-', '1', 'E', '-', '1', '6'};
        // 应输出true
        System.out.println(solution.isNumeric(str5));
    }
}

23.JZ38-字符串的排列-(知识点：字符串+递归,难度：中等)

题目描述：输入一个字符串，打印出该字符串中字符的所有排列。例如，输入字符串”abc”，则打印出由字符”a”, “b”, “c”所能排列出来的所有字符串：“abc”, “acb”, “bac”, “bca”, “cab”, “cba”。

解题分析

字符串的排列可以通过递归的方式进行求解。我们可以将字符串分为两部分：第一个字符和剩余字符。首先固定第一个字符，然后递归求解剩余字符的排列。对于剩余字符的排列，同样可以分为第一个字符和剩余字符，然后递归求解。重复这个过程，直到剩余字符为空，即可得到所有的排列。

具体步骤如下：

将字符串转换为字符数组，方便处理。
定义一个递归函数，参数包括字符数组、起始索引和结束索引。
如果起始索引等于结束索引，表示已经遍历到最后一个字符，将字符数组转换为字符串并输出。
遍历起始索引到结束索引的所有字符，依次将每个字符与起始索引的字符交换位置，然后递归调用函数处理剩余字符。
在递归调用完成后，需要将交换的字符复原，保证下一次循环的正确性。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.ArrayList;
import java.util.Arrays;
 
/**
 * @author yanfengzhang
 * @description 字符串的排列问题
 * @date 2023/6/5  22:52
 */
public class Permutation {
    /**
     * 回溯算法可以用于解决字符串的排列问题。下面是使用回溯算法解决字符串排列问题的思路：
     * 1.	将字符串转换为字符数组，方便处理。
     * 2.	创建一个布尔数组used，用于标记字符是否已经被使用过。
     * 3.	定义一个递归函数，参数包括字符数组、当前索引、已生成的排列、结果列表和used数组。
     * 4.	如果当前索引等于字符数组的长度，表示已经生成了一个排列，将其加入结果列表。
     * 5.	遍历字符数组的所有字符，如果字符没有被使用过，则将其添加到已生成的排列中，标记为已使用，然后递归调用函数处理下一个索引。
     * 6.	在递归调用完成后，需要将添加的字符移出已生成的排列，将标记置为未使用，以便进行下一次循环。
     */
    public ArrayList permutation(String str) {
        ArrayList result = new ArrayList<>();
        if (str == null || str.length() == 0) {
            return result;
        }
 
        // 将字符串转换为字符数组
        char[] arr = str.toCharArray();
        // 用于标记字符是否已经被使用过
        boolean[] used = new boolean[arr.length];
 
        // 对字符数组进行排序（可选）
        Arrays.sort(arr);
 
        permutationHelper(arr, 0, new StringBuilder(), result, used);
 
        return result;
    }
 
    private void permutationHelper(char[] arr, int index, StringBuilder sb, ArrayList result, boolean[] used) {
        if (index == arr.length) {
            // 当索引等于数组长度时，表示已经生成了一个排列
            // 将排列加入结果列表
            result.add(sb.toString());
        } else {
            for (int i = 0; i < arr.length; i++) {
                if (used[i] || (i > 0 && arr[i] == arr[i - 1] && !used[i - 1])) {
                    // 如果字符已经被使用过，或者当前字符与前一个字符相同且前一个字符未被使用，则跳过
                    continue;
                }
 
                // 添加字符到已生成的排列
                sb.append(arr[i]);
                // 标记字符为已使用
                used[i] = true;
 
                // 递归处理下一个索引
                permutationHelper(arr, index + 1, sb, result, used);
 
                // 移出已生成的排列的最后一个字符
                sb.deleteCharAt(sb.length() - 1);
                // 标记字符为未使用
                used[i] = false;
            }
        }
    }
 
    public static void main(String[] args) {
        Permutation solution = new Permutation();
 
        String str = "abc";
        ArrayList result = solution.permutation(str);
 
        for (String s : result) {
            System.out.println(s);
        }
    }
 
}

24.JZ48-最长不含重复字符的子字符串-(知识点：字符串,难度：中等)

25.JZ50-第一个只出现一次的字符-(知识点：字符串,难度：简单)

26.JZ58-左旋转字符串-(知识点：字符串,难度：中等)

题目描述：给定一个字符串 s 和一个整数 n，请将字符串左旋转 n 个字符。

解题分析

可以将字符串的左旋转操作拆分为两个步骤：

将前 n 个字符翻转。
将剩余的字符翻转。
将整个字符串翻转。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 给定一个字符串 s 和一个整数 n，请将字符串左旋转 n 个字符。
 * @date 2023/6/5  22:01
 */
public class StrLeftRotate {
    /**
     * 可以将字符串的左旋转操作拆分为两个步骤：
     * 1.	将前 n 个字符翻转。
     * 2.	将剩余的字符翻转。
     * 3.	将整个字符串翻转。
     */
    public String leftRotateString(String s, int n) {
        if (s == null || s.length() == 0) {
            return s;
        }
 
        char[] charArray = s.toCharArray();
        int length = charArray.length;
 
        // 对前 n 个字符翻转
        reverse(charArray, 0, n - 1);
 
        // 对剩余的字符翻转
        reverse(charArray, n, length - 1);
 
        // 对整个字符串翻转
        reverse(charArray, 0, length - 1);
 
        return new String(charArray);
    }
 
    // 翻转字符数组指定范围内的字符
    private void reverse(char[] charArray, int start, int end) {
        while (start < end) {
            char temp = charArray[start];
            charArray[start] = charArray[end];
            charArray[end] = temp;
            start++;
            end--;
        }
    }
 
    public static void main(String[] args) {
        StrLeftRotate solution = new StrLeftRotate();
 
        String s = "abcdefg";
        int n = 2;
 
        String rotatedString = solution.leftRotateString(s, n);
 
        System.out.println("左旋转后的字符串：" + rotatedString);
    }
}

27.JZ67-把字符串转换成整数-(知识点：字符串,难度：中等)

题目描述：请你写一个函数 StrToInt，实现将字符串转换成整数的功能。字符串可以包含空格字符，转换结果需要去掉前导空格，并且符号位只能是正负号（’+’ 或 ‘-’）。如果字符串中包含非数字字符或者空字符串，则返回 0。

解题分析

要将字符串转换成整数，可以按照以下步骤进行：

去掉字符串的前导空格。
判断字符串的符号位，记录正负号。
从字符串的第一个非空字符开始，遍历每个字符：• 如果当前字符是数字字符，则将其转换成数字，并累加到结果中。• 如果当前字符不是数字字符，则停止遍历。
根据符号位，给结果加上正负号。
如果结果超出整数的范围（即超出 Integer.MIN_VALUE 和 Integer.MAX_VALUE），则返回边界值。
如果字符串中没有有效的数字字符，则返回 0。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 请你写一个函数 StrToInt，实现将字符串转换成整数的功能。
 * 字符串可以包含空格字符，转换结果需要去掉前导空格，并且符号位只能是正负号（’+’ 或 ‘-’）。
 * 如果字符串中包含非数字字符或者空字符串，则返回 0。
 * @date 2023/6/5  23:03
 */
public class StrToInt {
    /**
     * 要将字符串转换成整数，可以按照以下步骤进行：
     * 1.	去掉字符串的前导空格。
     * 2.	判断字符串的符号位，记录正负号。
     * 3.	从字符串的第一个非空字符开始，遍历每个字符：
     * •	如果当前字符是数字字符，则将其转换成数字，并累加到结果中。
     * •	如果当前字符不是数字字符，则停止遍历。
     * 4.	根据符号位，给结果加上正负号。
     * 5.	如果结果超出整数的范围（即超出 Integer.MIN_VALUE 和 Integer.MAX_VALUE），则返回边界值。
     * 6.	如果字符串中没有有效的数字字符，则返回 0。
     */
    public int strToInt(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
 
        // 去掉前导空格
        str = str.trim();
        if (str.length() == 0) {
            return 0;
        }
 
        int index = 0;
        int sign = 1;
        int result = 0;
 
        // 判断符号位
        if (str.charAt(index) == '+' || str.charAt(index) == '-') {
            if (str.charAt(index) == '-') {
                sign = -1;
            }
            index++;
        }
 
        // 遍历字符数组
        while (index < str.length()) {
            char c = str.charAt(index);
            if (c < '0' || c > '9') {
                break;
            }
 
            // 计算结果
            int digit = c - '0';
            if (result > (Integer.MAX_VALUE - digit) / 10) {
                return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            result = result * 10 + digit;
 
            index++;
        }
 
        return result * sign;
    }
 
    public static void main(String[] args) {
        StrToInt solution = new StrToInt();
 
        String str = "   -12345";
        int result = solution.strToInt(str);
 
        System.out.println("转换后的整数：" + result);
    }
 
}

28.JZ73-翻转单词序列-(知识点：字符串双指针,难度：简单)

题目描述：请实现一个函数，将一个字符串中的单词进行翻转。例如，输入字符串 “I am a student.”，则输出 “student. a am I”。

解题分析

可以按照以下步骤实现翻转单词序列的功能：

首先去除字符串中的前导空格和尾部空格，可以使用 trim() 方法。
将字符串按空格进行分割，得到一个单词数组。
使用双指针的方法，对单词数组进行翻转。初始化两个指针 left 和 right，分别指向数组的首尾元素。• 交换指针指向的元素。• 左指针向右移动，右指针向左移动，直到两个指针相遇。
将翻转后的单词数组拼接成一个新的字符串，每个单词之间用空格分隔。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 请实现一个函数，将一个字符串中的单词进行翻转。
 * 例如，输入字符串 “I am a student.”，则输出 “student. a am I”。
 * @date 2023/6/5  22:35
 */
public class ReverseWords {
    /**
     * 可以按照以下步骤实现翻转单词序列的功能：
     * 1.	首先去除字符串中的前导空格和尾部空格，可以使用 trim() 方法。
     * 2.	将字符串按空格进行分割，得到一个单词数组。
     * 3.	使用双指针的方法，对单词数组进行翻转。初始化两个指针 left 和 right，分别指向数组的首尾元素。
     * •	交换指针指向的元素。
     * •	左指针向右移动，右指针向左移动，直到两个指针相遇。
     * 4.	将翻转后的单词数组拼接成一个新的字符串，每个单词之间用空格分隔。
     */
    public String reverseWords(String s) {
        // 去除前导空格和尾部空格
        s = s.trim();
 
        // 按空格分割字符串，得到单词数组
        String[] words = s.split("\\s+");
 
        int left = 0;
        int right = words.length - 1;
 
        // 双指针翻转单词数组
        while (left < right) {
            String temp = words[left];
            words[left] = words[right];
            words[right] = temp;
 
            left++;
            right--;
        }
 
        // 拼接单词数组成新的字符串
        StringBuilder sb = new StringBuilder();
        for (String word : words) {
            sb.append(word).append(" ");
        }
 
        // 去除最后一个空格
        sb.setLength(sb.length() - 1);
 
        return sb.toString();
    }
 
    public static void main(String[] args) {
        ReverseWords solution = new ReverseWords();
 
        String s = "I am a student.";
        String result = solution.reverseWords(s);
 
        System.out.println("翻转后的字符串：" + result);
    }
}

29.JZ74-合为S的连续正数序列-(知识点：穷举,难度：中等)

题目描述：输入一个正整数 target，输出所有和为 target 的连续正数序列（至少含有两个数）。序列内的数字要求按从小到大的顺序排列。

解题分析

可以使用穷举的方法来解决该问题。设定两个指针 start 和 end，分别表示连续序列的起始值和结束值。初始时，start 和 end 均为 1。根据连续序列的性质，可以进行如下操作：

如果从 start 到 end 的序列的和等于 target，将这个序列添加到结果列表中，并将 end 向后移动一位，继续寻找下一个序列。
如果从 start 到 end 的序列的和小于 target，将 end 向后移动一位，扩大序列范围，使得序列和增大。
如果从 start 到 end 的序列的和大于 target，将 start 向后移动一位，缩小序列范围，使得序列和减小。
当 start 大于等于 target 的一半时，即可停止寻找，因为在这之后的序列和一定大于 target。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.ArrayList;
import java.util.List;
 
/**
 * @author yanfengzhang
 * @description 输入一个正整数 target，输出所有和为 target 的连续正数序列（至少含有两个数）。
 * 序列内的数字要求按从小到大的顺序排列。
 * @date 2023/6/30  23:07
 */
public class FindContinuousSequence {
    /**
     * 可以使用穷举的方法来解决该问题。设定两个指针 start 和 end，分别表示连续序列的起始值和结束值。初始时，start 和 end 均为 1。根据连续序列的性质，可以进行如下操作：
     * •	如果从 start 到 end 的序列的和等于 target，将这个序列添加到结果列表中，并将 end 向后移动一位，继续寻找下一个序列。
     * •	如果从 start 到 end 的序列的和小于 target，将 end 向后移动一位，扩大序列范围，使得序列和增大。
     * •	如果从 start 到 end 的序列的和大于 target，将 start 向后移动一位，缩小序列范围，使得序列和减小。
     * •	当 start 大于等于 target 的一半时，即可停止寻找，因为在这之后的序列和一定大于 target。
     */
    public List> findContinuousSequence(int target) {
        List> result = new ArrayList<>();
        int start = 1;
        int end = 1;
        int sum = 0;
 
        while (start <= target / 2) {
            if (sum < target) {
                sum += end;
                end++;
            } else if (sum > target) {
                sum -= start;
                start++;
            } else {
                List sequence = new ArrayList<>();
                for (int i = start; i < end; i++) {
                    sequence.add(i);
                }
                result.add(sequence);
                sum -= start;
                start++;
            }
        }
 
        return result;
    }
 
    public static void main(String[] args) {
        FindContinuousSequence solution = new FindContinuousSequence();
 
        int target = 9;
        List> result = solution.findContinuousSequence(target);
 
        System.out.println("和为 " + target + " 的连续正数序列：");
        for (List sequence : result) {
            System.out.println(sequence);
        }
    }
 
}

30.JZ75-字符流中第一个不重复的字符(知识点：字符串,难度：中等)

题目描述：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 “go” 时，第一个只出现一次的字符是 “g”；当从该字符流中读出前六个字符 “google” 时，第一个只出现一次的字符是 “l”。

解题分析

为了快速找到字符流中第一个不重复的字符，可以借助哈希表和队列的结合使用。具体步骤如下：

创建一个哈希表 charCount，用于存储字符及其出现的次数。
创建一个队列 queue，用于按照字符流的顺序保存字符。
每次读入一个字符时，进行以下操作：

将字符添加到队列 queue 的末尾。
更新哈希表 charCount 中对应字符的出现次数。
遍历队列 queue，找到第一个在哈希表 charCount 中出现次数为 1 的字符，并返回。
如果队列 queue 中没有只出现一次的字符，则返回 ‘#’。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
 
/**
 * @author yanfengzhang
 * @description 请实现一个函数用来找出字符流中第一个只出现一次的字符。
 * 例如，当从字符流中只读出前两个字符 “go” 时，第一个只出现一次的字符是 “g”；
 * 当从该字符流中读出前六个字符 “google” 时，第一个只出现一次的字符是 “l”。
 * @date 2023/6/5  23:11
 */
public class StrFirstAppearingOnce {
    private Map charCount;
    private Queue queue;
 
    public StrFirstAppearingOnce() {
        charCount = new HashMap<>();
        queue = new LinkedList<>();
    }
 
    public void insert(char ch) {
        // 更新哈希表中字符的出现次数
        charCount.put(ch, charCount.getOrDefault(ch, 0) + 1);
        // 将字符添加到队列末尾
        queue.offer(ch);
    }
 
    /**
     * 为了快速找到字符流中第一个不重复的字符，可以借助哈希表和队列的结合使用。具体步骤如下：
     * 1.	创建一个哈希表 charCount，用于存储字符及其出现的次数。
     * 2.	创建一个队列 queue，用于按照字符流的顺序保存字符。
     * 3.	每次读入一个字符时，进行以下操作：
     * •	将字符添加到队列 queue 的末尾。
     * •	更新哈希表 charCount 中对应字符的出现次数。
     * •	遍历队列 queue，找到第一个在哈希表 charCount 中出现次数为 1 的字符，并返回。
     * •	如果队列 queue 中没有只出现一次的字符，则返回 ‘#’。
     */
    public char firstAppearingOnce() {
        // 遍历队列，找到第一个只出现一次的字符
        while (!queue.isEmpty()) {
            char ch = queue.peek();
            // 如果当前字符出现次数为 1，则返回该字符
            if (charCount.get(ch) == 1) {
                return ch;
            } else {
                // 否则，移除队列头部的字符
                queue.poll();
            }
        }
        // 如果队列为空，则返回 '#'
        return '#';
    }
 
    public static void main(String[] args) {
        StrFirstAppearingOnce solution = new StrFirstAppearingOnce();
 
        String stream = "google";
        for (char ch : stream.toCharArray()) {
            solution.insert(ch);
            char firstNonRepeating = solution.firstAppearingOnce();
            System.out.println("当前字符流：" + stream.substring(0, stream.indexOf(ch) + 1));
            System.out.println("第一个不重复的字符：" + firstNonRepeating);
        }
    }
 
}

31.JZ9—用两个栈实现队列(知识点：栈,难度：简单)

该题目直接可见栈知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第4题。

32.JZ12-矩阵中的路径-(知识点：DFS,难度：简单)

题目描述：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中的上、下、左、右四个相邻格子之间移动。如果一条路径经过了矩阵中的某一个格子，则该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串 “bfce” 的路径。

a b t g

c f c s

j d e h

解题分析

可以使用深度优先搜索（DFS）来解决这个问题。具体步骤如下：

遍历矩阵中的每个格子，将每个格子作为路径的起点。
在每个起点开始进行DFS搜索，判断是否存在一条路径可以匹配目标字符串。
首先判断当前起点是否越界或者与目标字符串的第一个字符不匹配，若不匹配则返回false。
若当前起点与目标字符串的第一个字符匹配，则开始进行DFS搜索。
在DFS搜索过程中，分别向上、下、左、右四个方向进行递归搜索，直到匹配完整个目标字符串或者无法继续匹配。
在递归搜索过程中，需要注意标记已访问的格子，以避免路径重复进入。
如果在搜索过程中匹配到了完整的目标字符串，则返回true；否则，返回false。
如果在遍历完所有起点后仍未找到匹配的路径，则返回false。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
 * 路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中的上、下、左、右四个相邻格子之间移动。
 * 如果一条路径经过了矩阵中的某一个格子，则该路径不能再次进入该格子。
 * 例如，在下面的3×4的矩阵中包含一条字符串 “bfce” 的路径。
 * a b t g
 * c f c s
 * j d e h
 * @date 2023/6/6  22:11
 */
public class PathInMatrix {
    /**
     * 可以使用深度优先搜索（DFS）来解决这个问题。具体步骤如下：
     * 1.	遍历矩阵中的每个格子，将每个格子作为路径的起点。
     * 2.	在每个起点开始进行DFS搜索，判断是否存在一条路径可以匹配目标字符串。
     * •	首先判断当前起点是否越界或者与目标字符串的第一个字符不匹配，若不匹配则返回false。
     * •	若当前起点与目标字符串的第一个字符匹配，则开始进行DFS搜索。
     * •	在DFS搜索过程中，分别向上、下、左、右四个方向进行递归搜索，直到匹配完整个目标字符串或者无法继续匹配。
     * •	在递归搜索过程中，需要注意标记已访问的格子，以避免路径重复进入。
     * •	如果在搜索过程中匹配到了完整的目标字符串，则返回true；否则，返回false。
     * 3.	如果在遍历完所有起点后仍未找到匹配的路径，则返回false。
     */
    public static boolean hasPath(char[][] matrix, String target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0 || target == null || target.length() == 0) {
            return false;
        }
 
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean[][] visited = new boolean[rows][cols];
 
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(matrix, i, j, target, 0, visited)) {
                    return true;
                }
            }
        }
 
        return false;
    }
 
    private static boolean dfs(char[][] matrix, int row, int col, String target, int index, boolean[][] visited) {
        if (index == target.length()) {
            // 匹配成功
            return true;
        }
 
        if (row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length ||
                matrix[row][col] != target.charAt(index) || visited[row][col]) {
            // 越界、字符不匹配或已访问过的情况
            return false;
        }
 
        // 标记当前格子为已访问
        visited[row][col] = true;
 
        // 在上、下、左、右四个方向递归搜索
        boolean found = dfs(matrix, row - 1, col, target, index + 1, visited) ||
                dfs(matrix, row + 1, col, target, index + 1, visited) ||
                dfs(matrix, row, col - 1, target, index + 1, visited) ||
                dfs(matrix, row, col + 1, target, index + 1, visited);
 
        // 恢复当前格子为未访问，方便其他路径使用
        visited[row][col] = false;
 
        return found;
    }
 
    public static void main(String[] args) {
        char[][] matrix = {
                {'a', 'b', 't', 'g'},
                {'c', 'f', 'c', 's'},
                {'j', 'd', 'e', 'h'}
        };
        String target = "bfce";
        boolean result = hasPath(matrix, target);
        // 输出: true
        System.out.println(result);
    }
}

33.JZ13-机器人的运动范围-(知识点：递归,难度：较难)

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

解题分析

该问题可以使用递归或深度优先搜索来解决。具体步骤如下：

定义一个辅助函数movingCountCore，用于计算机器人从坐标(i, j)开始能够到达的格子数量。
在movingCountCore函数中，首先判断当前坐标是否越界或已经访问过，若是，则返回0。
计算当前坐标(i, j)的数位之和，若大于给定的阈值k，则返回0。
将当前坐标标记为已访问。
递归计算机器人能够到达的上、下、左、右四个方向的格子数量，并将其累加起来。
返回累加结果加上当前格子本身，表示从当前格子出发能够到达的格子总数。
在主函数中调用movingCountCore函数，并返回最终结果。

这样就能够得到机器人能够到达的格子数量。

请注意，在解决问题时，可以使用一个辅助的二维数组来记录格子的访问状态，避免重复计算。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 地上有一个m行n列的方格，一个机器人从坐标(0, 0)的格子开始移动，
 * 它每次可以向上、下、左、右移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子。
 * 例如，当k为18时，机器人能够进入方格(35, 37)，因为3+5+3+7=18。
 * 但它不能进入方格(35, 38)，因为3+5+3+8=19。请问机器人能够到达多少个格子？
 * @date 2023/6/6  22:16
 */
public class RangeMotionForRobot {
    /**
     * 该问题可以使用递归或深度优先搜索来解决。具体步骤如下：
     * 1.	定义一个辅助函数movingCountCore，用于计算机器人从坐标(i, j)开始能够到达的格子数量。
     * 2.	在movingCountCore函数中，首先判断当前坐标是否越界或已经访问过，若是，则返回0。
     * 3.	计算当前坐标(i, j)的数位之和，若大于给定的阈值k，则返回0。
     * 4.	将当前坐标标记为已访问。
     * 5.	递归计算机器人能够到达的上、下、左、右四个方向的格子数量，并将其累加起来。
     * 6.	返回累加结果加上当前格子本身，表示从当前格子出发能够到达的格子总数。
     * 7.	在主函数中调用movingCountCore函数，并返回最终结果。
     * 
     * 这样就能够得到机器人能够到达的格子数量。
     */
    public int movingCount(int threshold, int rows, int cols) {
        // 创建一个二维数组用于记录格子的访问状态，初始值为false表示未访问过
        boolean[][] visited = new boolean[rows][cols];
        // 调用辅助函数进行递归计算
        return movingCountCore(threshold, 0, 0, rows, cols, visited);
    }
 
    private int movingCountCore(int threshold, int i, int j, int rows, int cols, boolean[][] visited) {
        // 判断坐标是否越界或已经访问过
        if (i < 0 || i >= rows || j < 0 || j >= cols || visited[i][j]) {
            return 0;
        }
 
        // 计算当前坐标的数位之和
        int sum = getDigitSum(i) + getDigitSum(j);
 
        // 判断数位之和是否大于阈值
        if (sum > threshold) {
            return 0;
        }
 
        // 标记当前坐标为已访问
        visited[i][j] = true;
 
        // 递归计算上、下、左、右四个方向的格子数量，并累加结果
        int count = 1 + movingCountCore(threshold, i - 1, j, rows, cols, visited)
                + movingCountCore(threshold, i + 1, j, rows, cols, visited)
                + movingCountCore(threshold, i, j - 1, rows, cols, visited)
                + movingCountCore(threshold, i, j + 1, rows, cols, visited);
 
        return count;
    }
 
    // 计算数位之和的辅助函数
    private int getDigitSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
 
    public static void main(String[] args) {
        RangeMotionForRobot solution = new RangeMotionForRobot();
 
        // 测试样例
        int threshold = 5;
        int rows = 10;
        int cols = 10;
        int count = solution.movingCount(threshold, rows, cols);
        System.out.println("能够到达的格子数量: " + count);
    }
}

34.JZ14-剪绳子-(知识点：基础数学,难度：中等)

题目描述：给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…，k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，剪成2、3、3三段，得到的最大乘积是18。

解题分析

这是一道典型的动态规划问题。我们可以定义一个长度为n+1的数组dp，dp[i]表示长度为i的绳子剪成若干段后的最大乘积。对于长度为i的绳子，我们可以选择剪一刀，将其分成两段，假设第一段的长度为j，那么第二段的长度就是i-j。我们可以选择继续将这两段绳子剪成若干段，或者保持不剪，取决于哪种方式可以得到最大的乘积。因此，我们可以得到状态转移方程：dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j)))，其中j的取值范围是从1到i/2。最后，dp[n]就是所求的最大乘积。

例如，对于长度为8的绳子，可以分别选择剪一刀后的两段长度为1和7、2和6、3和5、4和4。对于每种情况，我们可以选择继续剪成若干段或者保持不剪，取最大的乘积，然后更新dp数组。最后，dp[8]就是所求的最大乘积。

解题步骤：

创建一个长度为n+1的数组dp，并初始化dp[0]和dp[1]为0，dp[2]为1。
使用循环从3到n，计算每个dp[i]的最大乘积：• 内部使用循环从1到i/2，计算剪一刀后的两段的最大乘积，并选择最大值。• 将该最大值与剪一刀后的两段乘积进行比较，取较大值作为dp[i]的最大乘积。
返回dp[n]作为结果。

这样，我们就可以得到长度为n的绳子剪成若干段后的最大乘积。

请注意，当n小于等于3时，需要特殊处理，因为剪成若干段后的最大乘积小于等于n本身。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），
 * 每段绳子的长度记为k[0],k[1],…，k[m]。
 * 请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？
 * 例如，当绳子的长度是8时，剪成2、3、3三段，得到的最大乘积是18。
 * @date 2023/6/6  22:20
 */
public class CutRope {
    /**
     * 解题步骤：
     * 1.	创建一个长度为n+1的数组dp，并初始化dp[0]和dp[1]为0，dp[2]为1。
     * 2.	使用循环从3到n，计算每个dp[i]的最大乘积：
     * •	内部使用循环从1到i/2，计算剪一刀后的两段的最大乘积，并选择最大值。
     * •	将该最大值与剪一刀后的两段乘积进行比较，取较大值作为dp[i]的最大乘积。
     * 3.	返回dp[n]作为结果。
     * 
     * 这样，我们就可以得到长度为n的绳子剪成若干段后的最大乘积。
     */
    public int cutRope(int target) {
        if (target <= 1) {
            return 0;
        }
        if (target == 2) {
            return 1;
        }
        if (target == 3) {
            return 2;
        }
 
        // 创建长度为target+1的数组，用于存储最大乘积
        int[] dp = new int[target + 1];
        // 长度为0的绳子无法剪断，最大乘积为0
        dp[0] = 0;
        // 长度为1的绳子无法剪断，最大乘积为0
        dp[1] = 1;
        // 长度为2的绳子只能剪成1*1，最大乘积为1
        dp[2] = 2;
        // 长度为3的绳子只能剪成1*2，最大乘积为2
        dp[3] = 3;
 
        // 循环计算每个长度的最大乘积
        for (int i = 4; i <= target; i++) {
            // 内部循环计算剪一刀后的两段的最大乘积，并选择最大值
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
            }
        }
 
        return dp[target];
    }
 
    public static void main(String[] args) {
        CutRope solution = new CutRope();
        // 验证案例：长度为8的绳子可以剪成1*7、2*6、3*5、4*4，最大乘积为18
        int target = 8;
        int result = solution.cutRope(target);
        System.out.println("Max product for rope of length " + target + ": " + result);
    }
 
}

35.JZ83-大字符串相加-(基础数学,难度：简单)

题目描述：给定两个非负整数的大字符串表示，将它们相加并返回结果的大字符串表示。假设输入的大字符串都是有效的，且不包含前导零，除非本身就是数字 0。

解题分析

为了处理大整数的加法，我们可以使用类似于手工加法的方法，逐位相加，并将进位传递到下一位。我们从字符串的末尾开始逐位相加，模拟手工计算的过程。

具体的解法如下：

创建一个空的结果字符串，用于存储相加的结果。
定义两个指针分别指向两个输入字符串的末尾。
初始化一个进位变量为 0。
循环从末尾向前遍历两个输入字符串，直到两个字符串都遍历完毕。• 在每一位上，将当前位的数字相加，加上进位，并将结果转化为字符。• 如果相加结果超过 9，更新进位为 1，否则更新进位为 0。• 将相加结果的个位数添加到结果字符串的开头。
如果还有一个字符串没有遍历完毕，则继续遍历该字符串的剩余位，并加上进位。
如果最后进位为 1，则将字符 ‘1’ 添加到结果字符串的开头。
将结果字符串返回。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 给定两个非负整数的大字符串表示，将它们相加并返回结果的大字符串表示。
 * 假设输入的大字符串都是有效的，且不包含前导零，除非本身就是数字 0。
 * @date 2023/6/15  23:05
 */
public class AddStrings {
    /**
     * 为了处理大整数的加法，我们可以使用类似于手工加法的方法，逐位相加，并将进位传递到下一位。我们从字符串的末尾开始逐位相加，模拟手工计算的过程。
     * 
     * 具体的解法如下：
     * 
     * 1.	创建一个空的结果字符串，用于存储相加的结果。
     * 2.	定义两个指针分别指向两个输入字符串的末尾。
     * 3.	初始化一个进位变量为 0。
     * 4.	循环从末尾向前遍历两个输入字符串，直到两个字符串都遍历完毕。
     * •	在每一位上，将当前位的数字相加，加上进位，并将结果转化为字符。
     * •	如果相加结果超过 9，更新进位为 1，否则更新进位为 0。
     * •	将相加结果的个位数添加到结果字符串的开头。
     * 5.	如果还有一个字符串没有遍历完毕，则继续遍历该字符串的剩余位，并加上进位。
     * 6.	如果最后进位为 1，则将字符 ‘1’ 添加到结果字符串的开头。
     * 7.	将结果字符串返回。
     *
     * @param num1
     * @param num2
     * @return
     */
    public static String addStrings(String num1, String num2) {
        // num1字符串的指针
        int i = num1.length() - 1;
        // num2字符串的指针
        int j = num2.length() - 1;
        // 进位
        int carry = 0;
        // 结果字符串
        StringBuilder result = new StringBuilder();
 
        while (i >= 0 || j >= 0) {
            // 将当前位的数字相加，并加上进位
            if (i >= 0) {
                carry += num1.charAt(i) - '0';
                i--;
            }
            if (j >= 0) {
                carry += num2.charAt(j) - '0';
                j--;
            }
 
            // 将相加结果的个位数添加到结果字符串的开头
            result.insert(0, carry % 10);
            // 更新进位
            carry /= 10;
        }
 
        // 如果还有进位，则在结果字符串开头添加 '1'
        if (carry == 1) {
            result.insert(0, '1');
        }
 
        return result.toString();
    }
 
    public static void main(String[] args) {
        String num1 = "123";
        String num2 = "456";
        String sum = addStrings(num1, num2);
        // 输出相加结果
        System.out.println("Sum: " + sum);
    }
}

36.JZ15-二进制中1的个数-(知识点：基础数学,难度：简单)

题目描述：请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

解题分析

要计算一个整数的二进制表示中 1 的个数，可以利用位运算的特性。一个整数 n 与 1 进行按位与运算（n & 1），如果结果为 1，则说明 n 的二进制表示最右边一位是 1；如果结果为 0，则说明 n 的二进制表示最右边一位是 0。然后，将 n 右移一位（n >>= 1），继续进行上述操作，直到 n 变为 0。统计结果为 1 的次数即为所求。

具体步骤如下：

初始化计数器 count 为 0。
循环判断 n 是否为 0，若不为 0，执行以下步骤：• 判断 n 的最右位是否为 1：n & 1，若结果为 1，count 加 1。• 右移 n 一位：n >>= 1。
返回计数器 count。

这种解法的时间复杂度为 O(log₂n)，其中 n 为输入的整数。因为在每一次循环中，n 都会右移一位，循环的次数取决于 n 的二进制位数。

请注意，对于负数的情况，右移操作会在最高位补 1，因此循环可能会无限进行下去。为了避免这种情况，可以使用无符号右移操作（>>>）来替代有符号右移操作（>>）。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。
 * 例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
 * @date 2023/6/6  22:28
 */
public class NumberOfOne {
    /**
     * 要计算一个整数的二进制表示中 1 的个数，可以利用位运算的特性。
     * 一个整数 n 与 1 进行按位与运算（n & 1），如果结果为 1，则说明 n 的二进制表示最右边一位是 1；
     * 如果结果为 0，则说明 n 的二进制表示最右边一位是 0。然后，将 n 右移一位（n >>= 1），
     * 继续进行上述操作，直到 n 变为 0。统计结果为 1 的次数即为所求。
     * 
     * 具体步骤如下：
     * 1.	初始化计数器 count 为 0。
     * 2.	循环判断 n 是否为 0，若不为 0，执行以下步骤：
     * •	判断 n 的最右位是否为 1：n & 1，若结果为 1，count 加 1。
     * •	右移 n 一位：n >>= 1。
     * 3.	返回计数器 count。
     * 这种解法的时间复杂度为 O(log₂n)，其中 n 为输入的整数。
     * 因为在每一次循环中，n 都会右移一位，循环的次数取决于 n 的二进制位数。
     */
    public int numberOfOne(int n) {
        // 用于记录1的个数
        int count = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                // n的最右位为1，计数器加1
                count++;
            }
            // 右移一位
            n >>>= 1;
        }
        return count;
    }
 
    public static void main(String[] args) {
        NumberOfOne solution = new NumberOfOne();
        // 测试样例
        int n = 9;
        int count = solution.numberOfOne(n);
        System.out.println("Number of 1s in " + n + "'s binary representation: " + count);
    }
}

37.JZ16-数值的整数次方字-(知识点：基础数学,难度：中等)

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

解题分析

求一个数的整数次方，可以使用快速幂的方法来降低计算复杂度。快速幂的核心思想是将指数按照二进制展开，通过不断平方和乘积的方式快速计算幂。

具体步骤如下：

判断指数exponent的正负情况，如果为负，则将base取倒数，同时将指数变为正数。
初始化结果result为1。
循环计算，每次将base平方，如果当前指数的二进制位为1，则将result乘以当前base的值。
最终返回结果result。

需要注意的是，由于计算机对浮点数的表示有精度限制，因此在判断浮点数是否等于0时，不能直接使用==运算符，而是要考虑它们的差值是否在一个很小的范围内。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 实现函数double Power(double base, int exponent)，求base的exponent次方。
 * 不得使用库函数，同时不需要考虑大数问题。
 * @date 2023/6/6  22:37
 */
public class NumberPower {
    /**
     * 求一个数的整数次方，可以使用快速幂的方法来降低计算复杂度。
     * 快速幂的核心思想是将指数按照二进制展开，通过不断平方和乘积的方式快速计算幂。
     * 具体步骤如下：
     * 1.	判断指数exponent的正负情况，如果为负，则将base取倒数，同时将指数变为正数。
     * 2.	初始化结果result为1。
     * 3.	循环计算，每次将base平方，如果当前指数的二进制位为1，则将result乘以当前base的值。
     * 4.	最终返回结果result。
     * 需要注意的是，由于计算机对浮点数的表示有精度限制，因此在判断浮点数是否等于0时，不能直接使用==运算符，而是要考虑它们的差值是否在一个很小的范围内。
     */
    public double power(double base, int exponent) {
        if (base == 0 && exponent < 0) {
            throw new IllegalArgumentException("Invalid input: base cannot be 0 when exponent is negative.");
        }
 
        int absExponent = Math.abs(exponent);
        double result = powerWithUnsignedExponent(base, absExponent);
 
        if (exponent < 0) {
            result = 1.0 / result;
        }
 
        return result;
    }
 
    private double powerWithUnsignedExponent(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent == 1) {
            return base;
        }
 
        double result = powerWithUnsignedExponent(base, exponent >> 1);
        result *= result;
 
        if ((exponent & 0x1) == 1) {
            result *= base;
        }
 
        return result;
    }
 
    public static void main(String[] args) {
        NumberPower solution = new NumberPower();
        // 测试样例
        double base = 2.0;
        int exponent = 5;
        double result = solution.power(base, exponent);
        System.out.println(base + " ^ " + exponent + " = " + result);
    }
 
}

38.JZ62-圆圈中最后剩下的数-(知识点：基础数学,难度：中等)

题目描述：0, 1, …, n-1 这 n 个数字排成一个圆圈，从数字 0 开始每次从这个圆圈中删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。

解题分析

可以使用约瑟夫环问题的解法来解决这个问题。约瑟夫环问题是一个经典的数学问题，其解法可以通过递推公式来得到。

具体步骤如下：

创建一个长度为 n 的列表，用于表示圆圈中的数字。
初始化变量 index 为 0，表示当前要删除的数字的索引。
循环进行以下操作，直到列表中只剩下一个数字：• 计算下一个要删除的数字的索引：(index + m - 1) % n，其中 m 表示每次删除的数字间隔，n 表示当前剩余数字的个数。• 删除列表中对应索引的数字。• 更新 n 的值为 n - 1，表示剩余数字的个数减少了一个。
最终剩下的数字即为所求结果。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.ArrayList;
import java.util.List;
 
/**
 * @author yanfengzhang
 * @description 0, 1, …, n-1 这 n 个数字排成一个圆圈，
 * 从数字 0 开始每次从这个圆圈中删除第 m 个数字。
 * 求出这个圆圈里剩下的最后一个数字。
 * @date 2023/6/6  22:53
 */
public class LastRemainingInCircle {
    /**
     * 可以使用约瑟夫环问题的解法来解决这个问题。约瑟夫环问题是一个经典的数学问题，其解法可以通过递推公式来得到。
     * 具体步骤如下：
     * 1.	创建一个长度为 n 的列表，用于表示圆圈中的数字。
     * 2.	初始化变量 index 为 0，表示当前要删除的数字的索引。
     * 3.	循环进行以下操作，直到列表中只剩下一个数字：
     * •	计算下一个要删除的数字的索引：(index + m - 1) % n，其中 m 表示每次删除的数字间隔，n 表示当前剩余数字的个数。
     * •	删除列表中对应索引的数字。
     * •	更新 n 的值为 n - 1，表示剩余数字的个数减少了一个。
     * 4.	最终剩下的数字即为所求结果。
     */
    public int lastRemaining(int n, int m) {
        if (n <= 0 || m <= 0) {
            return -1;
        }
 
        List circle = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            circle.add(i);
        }
 
        int index = 0;
        while (circle.size() > 1) {
            index = (index + m - 1) % circle.size();
            circle.remove(index);
        }
 
        return circle.get(0);
    }
 
    public static void main(String[] args) {
        LastRemainingInCircle solution = new LastRemainingInCircle();
        // 测试样例
        int n = 7;
        int m = 3;
        int result = solution.lastRemaining(n, m);
        System.out.println("Last remaining number: " + result);
    }
}

39.JZ63-买卖股票的最好时机-(知识点：贪心+动态规划,难度：简单)

该题目直接可见动态规划总结与编程练习_张彦峰ZYF的博客-CSDN博客中的第18题。

40.JZ64-求1+2+3+···+n数字之和-(知识点：基础数学,难度：中等)

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

解题分析

要求不能使用循环语句和条件判断语句来求解数字之和，可以考虑使用递归来实现。

具体步骤如下：

使用递归函数 sumNums，传入一个参数 n 表示要求和的范围，初始值为 n。
使用逻辑运算符 && 来判断递归的终止条件，当 n=0 时终止递归。
在递归过程中，使用 n-1 来缩小范围，并通过递归调用 sumNums(n-1) 来求解前 n-1 个数字的和。
将递归得到的结果与 n 相加，即可得到 1+2+3+…+n 的和。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 求 1+2+3+…+n 的和，
 * 要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句（A?B:C）。
 * @date 2023/6/6  23:35
 */
public class NumsSum {
    /**
     * 要求不能使用循环语句和条件判断语句来求解数字之和，可以考虑使用递归来实现。
     * 具体步骤如下：
     * 1.	使用递归函数 sumNums，传入一个参数 n 表示要求和的范围，初始值为 n。
     * 2.	使用逻辑运算符 && 来判断递归的终止条件，当 n=0 时终止递归。
     * 3.	在递归过程中，使用 n-1 来缩小范围，并通过递归调用 sumNums(n-1) 来求解前 n-1 个数字的和。
     * 4.	将递归得到的结果与 n 相加，即可得到 1+2+3+…+n 的和。
     */
    public int sumNums(int n) {
        boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
        return n;
    }
 
    public static void main(String[] args) {
        NumsSum solution = new NumsSum();
        // 测试样例
        int n = 5;
        int result = solution.sumNums(n);
        System.out.println("Sum of numbers: " + result);
    }
}

41.JZ65—不用加减乘除做加法(知识点：基础数学,难度：简单)

题目描述：写一个函数，求两个整数之和，要求在函数体内不得使用四则运算符号（+、-、*、/）。

解题分析

要实现两个整数的加法，不能使用四则运算符号，可以考虑使用位运算来进行操作。

具体步骤如下：

使用位运算的异或操作（^）计算两个数的无进位和。异或操作可以将两个数的二进制位进行相加，不考虑进位。
使用位运算的与操作（&）和左移操作（<<）计算进位值。与操作可以得到两个数相加时的进位，左移操作将进位值向左移动一位。
将无进位和与进位值相加，得到最终的和。
重复上述步骤，直到没有进位为止。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 写一个函数，求两个整数之和，
 * 要求在函数体内不得使用四则运算符号（+、-、*、/）。
 * @date 2023/6/6  23:37
 */
public class AddDeal {
    /**
     * 要实现两个整数的加法，不能使用四则运算符号，可以考虑使用位运算来进行操作。
     * 具体步骤如下：
     * 1.	使用位运算的异或操作（^）计算两个数的无进位和。异或操作可以将两个数的二进制位进行相加，不考虑进位。
     * 2.	使用位运算的与操作（&）和左移操作（<<）计算进位值。与操作可以得到两个数相加时的进位，左移操作将进位值向左移动一位。
     * 3.	将无进位和与进位值相加，得到最终的和。
     * 4.	重复上述步骤，直到没有进位为止。
     */
    public int add(int a, int b) {
        while (b != 0) {
            // 无进位和
            int sum = a ^ b;
            // 进位值
            int carry = (a & b) << 1;
            a = sum;
            b = carry;
        }
        return a;
    }
 
    public static void main(String[] args) {
        AddDeal solution = new AddDeal();
        // 测试样例
        int a = 5;
        int b = 7;
        int result = solution.add(a, b);
        System.out.println("Sum: " + result);
    }
}

42.JZ43-从1到n整数中1出现的次数-(知识点：基础数学,难度：中等)

题目描述：输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。例如，输入 12，从 1 到 12 这些整数中，1 出现的次数是 5（1、10、11、12）。

解题分析

要求从 1 到 n 整数中 1 出现的次数，可以使用数学的方法来解决。

具体步骤如下：

将 n 拆分为若干位数，从个位开始，设当前位为 weight。
计算当前位上 1 出现的次数，分为以下三种情况：• weight = 0：当前位为 0，1 出现次数为 high * digit。• weight = 1：当前位为 1，1 出现次数为 high * digit + low + 1。• weight > 1：当前位大于 1，1 出现次数为 (high + 1) * digit。
遍历每一位，累加每个位上 1 出现的次数。
返回累加的结果即为从 1 到 n 整数中 1 出现的总次数。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。
 * 例如，输入 12，从 1 到 12 这些整数中，1 出现的次数是 5（1、10、11、12）。
 * @date 2023/6/6  23:44
 */
public class DigitOnes {
    /**
     * 要求从 1 到 n 整数中 1 出现的次数，可以使用数学的方法来解决。
     * 具体步骤如下：
     * 1.	将 n 拆分为若干位数，从个位开始，设当前位为 weight。
     * 2.	计算当前位上 1 出现的次数，分为以下三种情况：
     * •	weight = 0：当前位为 0，1 出现次数为 high * digit。
     * •	weight = 1：当前位为 1，1 出现次数为 high * digit + low + 1。
     * •	weight > 1：当前位大于 1，1 出现次数为 (high + 1) * digit。
     * 3.	遍历每一位，累加每个位上 1 出现的次数。
     * 4.	返回累加的结果即为从 1 到 n 整数中 1 出现的总次数。
     */
    public int countDigitOne(int n) {
        int count = 0;
        int digit = 1;
        int high = n / 10;
        int cur = n % 10;
        int low = 0;
 
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                count += high * digit;
            } else if (cur == 1) {
                count += high * digit + low + 1;
            } else {
                count += (high + 1) * digit;
            }
 
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
 
        return count;
    }
 
    public static void main(String[] args) {
        DigitOnes solution = new DigitOnes();
        // 测试样例
        int n = 12;
        int result = solution.countDigitOne(n);
        System.out.println("Count of digit one: " + result);
    }
}

43.JZ6-从尾到头打印链表-(知识点：链表,难度：简单)

题目描述：输入一个链表的头节点，从尾到头反过来打印出每个节点的值。

解题分析

这道题要求从尾到头打印链表，可以使用递归或者辅助栈来实现。

递归方法：

递归函数的作用是先递归打印链表的下一个节点，再打印当前节点的值。
当遇到空节点时，即到达链表尾部，开始回溯并打印节点的值。

辅助栈方法：

遍历链表，将每个节点的值依次压入栈中。
遍历完成后，依次从栈中弹出节点的值，即可实现从尾到头打印。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import org.zyf.javabasic.letcode.list.base.ListNode;
 
/**
 * @author yanfengzhang
 * @description 输入一个链表的头节点，从尾到头反过来打印出每个节点的值。
 * @date 2023/6/6  23:46
 */
public class PrintList {
    /**
     * 这道题要求从尾到头打印链表，可以使用递归或者辅助栈来实现。
     * 1.	递归方法：
     * •	递归函数的作用是先递归打印链表的下一个节点，再打印当前节点的值。
     * •	当遇到空节点时，即到达链表尾部，开始回溯并打印节点的值。
     * 2.	辅助栈方法：
     * •	遍历链表，将每个节点的值依次压入栈中。
     * •	遍历完成后，依次从栈中弹出节点的值，即可实现从尾到头打印。
     */
    public void printListReversingly(ListNode head) {
        if (head != null) {
            if (head.next != null) {
                printListReversingly(head.next);
            }
            System.out.println(head.val);
        }
    }
 
    public static void main(String[] args) {
        PrintList solution = new PrintList();
 
        // 构建链表: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
 
        // 打印链表
        solution.printListReversingly(head);
    }
}

44.JZ18-删除链表的节点-(知识点：链表,难度：简单)

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

解题分析

删除链表中的节点有以下几种情况：

要删除的节点是头节点：直接将头指针指向头节点的下一个节点即可。
要删除的节点不是头节点：遍历链表，找到要删除的节点的前一个节点，将前一个节点的指针指向要删除节点的下一个节点。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import org.zyf.javabasic.letcode.list.base.ListNode;
 
/**
 * @author yanfengzhang
 * @description 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
 * @date 2023/7/1  19:48
 */
public class DeleteListNode {
    /**
     * 删除链表中的节点有以下几种情况：
     * 1.	要删除的节点是头节点：直接将头指针指向头节点的下一个节点即可。
     * 2.	要删除的节点不是头节点：
     * 遍历链表，找到要删除的节点的前一个节点，将前一个节点的指针指向要删除节点的下一个节点。
     */
    public ListNode deleteNode(ListNode head, int val) {
        // 处理头节点是要删除的节点的情况
        if (head != null && head.val == val) {
            return head.next;
        }
 
        ListNode cur = head;
        ListNode prev = null;
 
        // 遍历链表查找要删除的节点
        while (cur != null) {
            if (cur.val == val) {
                // 删除节点
                prev.next = cur.next;
                break;
            }
            prev = cur;
            cur = cur.next;
        }
 
        return head;
    }
 
    public static void main(String[] args) {
        DeleteListNode solution = new DeleteListNode();
 
        // 构建链表: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
 
        int val = 3;
 
        // 删除节点
        ListNode newHead = solution.deleteNode(head, val);
 
        // 打印链表
        ListNode cur = newHead;
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
    }
 
}

45.JZ76-删除链表中的重复结点-(知识点：链表,难度：中等)

该题目直接可见链表知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第7题。

46.JZ22-链表中的第k个结点-(知识点：链表,难度：简单)

题目描述：输入一个链表，输出该链表中倒数第k个节点。假设该链表中节点数量大于等于k。

解题分析

要找到链表中倒数第k个节点，可以使用双指针法。定义两个指针fast和slow，初始时都指向链表的头节点。

首先，让fast指针先向前移动k个位置，然后同时移动fast和slow指针，直到fast指针到达链表末尾。此时，slow指针指向的节点就是倒数第k个节点。

具体步骤如下：

初始化两个指针fast和slow，都指向链表的头节点。
让fast指针先向前移动k个位置。
同时移动fast和slow指针，直到fast指针到达链表末尾。
返回slow指针指向的节点。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import org.zyf.javabasic.letcode.list.base.ListNode;
 
/**
 * @author yanfengzhang
 * @description 输入一个链表，输出该链表中倒数第k个节点。
 * 假设该链表中节点数量大于等于k。
 * @date 2023/6/6  23:50
 */
public class KthFromEnd {
    /**
     * 要找到链表中倒数第k个节点，可以使用双指针法。定义两个指针fast和slow，初始时都指向链表的头节点。
     * 首先，让fast指针先向前移动k个位置，然后同时移动fast和slow指针，
     * 直到fast指针到达链表末尾。此时，slow指针指向的节点就是倒数第k个节点。
     * 具体步骤如下：
     * 1.	初始化两个指针fast和slow，都指向链表的头节点。
     * 2.	让fast指针先向前移动k个位置。
     * 3.	同时移动fast和slow指针，直到fast指针到达链表末尾。
     * 4.	返回slow指针指向的节点。
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
 
        // 让fast指针先向前移动k个位置
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
 
        // 同时移动fast和slow指针
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
 
        return slow;
    }
 
    public static void main(String[] args) {
        KthFromEnd solution = new KthFromEnd();
 
        // 构建链表: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
 
        int k = 2;
 
        // 获取倒数第k个节点
        ListNode kthNode = solution.getKthFromEnd(head, k);
 
        // 打印倒数第k个节点的值
        System.out.println(kthNode.val);
    }
 
}

50.JZ35-复杂链表的复制-(知识点：链表,难度：较难)

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

解题分析

要复制一个复杂链表，需要考虑节点的复制以及random指针的复制。可以采用以下步骤进行复制：

遍历原链表，复制每个节点，并将复制后的节点插入到原节点的后面。例如，对于原链表节点A，复制后的节点为A’，则将A’插入到A后面。
遍历原链表，复制random指针。对于每个复制后的节点A’，其对应的原节点为A，如果A的random指针指向节点B，则A’的random指针指向B的复制节点B’。
将复制后的链表拆分成两个链表，一个是原链表，一个是复制链表。遍历原链表，根据每个节点的位置关系，将其从链表中断开，形成两个独立的链表。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 请实现一个函数，复制一个复杂链表。
 * 在复杂链表中，每个节点除了有一个next指针指向下一个节点，
 * 还有一个random指针指向链表中的任意节点或者null。
 * @date 2023/6/6  00:52
 */
public class ComxCopyList {
    /**
     * 要复制一个复杂链表，需要考虑节点的复制以及random指针的复制。可以采用以下步骤进行复制：
     * 1.	遍历原链表，复制每个节点，并将复制后的节点插入到原节点的后面。例如，对于原链表节点A，复制后的节点为A’，则将A’插入到A后面。
     * 2.	遍历原链表，复制random指针。对于每个复制后的节点A’，其对应的原节点为A，如果A的random指针指向节点B，则A’的random指针指向B的复制节点B’。
     * 3.	将复制后的链表拆分成两个链表，一个是原链表，一个是复制链表。遍历原链表，根据每个节点的位置关系，将其从链表中断开，形成两个独立的链表。
     */
    public ListNode copyRandomList(ListNode head) {
        if (head == null) {
            return null;
        }
 
        // 复制每个节点并插入到原节点后面
        ListNode cur = head;
        while (cur != null) {
            ListNode copyNode = new ListNode(cur.val);
            copyNode.next = cur.next;
            cur.next = copyNode;
            cur = copyNode.next;
        }
 
        // 复制random指针
        cur = head;
        while (cur != null) {
            ListNode copyNode = cur.next;
            if (cur.random != null) {
                copyNode.random = cur.random.next;
            }
            cur = copyNode.next;
        }
 
        // 拆分成两个链表
        cur = head;
        ListNode newHead = head.next;
        while (cur != null) {
            ListNode copyNode = cur.next;
            cur.next = copyNode.next;
            if (copyNode.next != null) {
                copyNode.next = copyNode.next.next;
            }
            cur = cur.next;
        }
 
        return newHead;
    }
 
    class ListNode {
        int val;
        ListNode next;
        ListNode random;
 
        ListNode(int val) {
            this.val = val;
        }
    }
 
    public void main(String[] args) {
        ComxCopyList solution = new ComxCopyList();
 
        // 构建复杂链表
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        head.random = node3;
        node2.random = node5;
        node4.random = node2;
 
        // 打印链表
        ListNode cur = copyRandomList(head);
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
    }
}

51.JZ52-两个链表的第一个公共的结点-(知识点：链表,难度：简单)

该题目直接可见链表知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第5题。

52.JZ26-树的子结构-(知识点：树,难度：中等)

题目描述：输入两棵二叉树A和B，判断B是不是A的子结构。二叉树节点的定义如下：

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int val) {

this.val = val;

}

}

解题分析

要判断B是否是A的子结构，可以分为两步进行：

在树A中找到与树B根节点值相同的节点，作为起始点进行匹配。
在匹配的起始点处，判断树A中以该节点为根节点的子树是否包含树B，即判断两个子树是否结构相同。

具体步骤如下：

遍历树A，寻找与树B根节点值相同的节点• 如果找到了与树B根节点值相同的节点，则进入第2步。• 如果遍历完树A仍未找到相同的节点，则返回false。
以找到的相同节点为起始点，判断树A中以该节点为根节点的子树是否包含树B。

如果树B为null，表示树B已经匹配完毕，返回true。
如果树A为null，表示树A已经遍历完毕，而树B还未匹配完毕，返回false。
如果树A的节点值与树B的节点值不相同，返回false。
分别判断树A的左子树和右子树是否包含树B，如果两者有一个为true，则返回true；否则返回false。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import org.zyf.javabasic.letcode.tree.base.TreeNode;
 
/**
 * @author yanfengzhang
 * @description 输入两棵二叉树A和B，判断B是不是A的子结构。二叉树节点的定义如下：
 * class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * 
 * TreeNode(int val) {
 * this.val = val;
 * }
 * }
 * @date 2023/6/17 00:06
 */
public class SubStructure {
    /**
     * 要判断B是否是A的子结构，可以分为两步进行：
     * 1.	在树A中找到与树B根节点值相同的节点，作为起始点进行匹配。
     * 2.	在匹配的起始点处，判断树A中以该节点为根节点的子树是否包含树B，即判断两个子树是否结构相同。
     * 具体步骤如下：
     * 1.	遍历树A，寻找与树B根节点值相同的节点。
     * •	如果找到了与树B根节点值相同的节点，则进入第2步。
     * •	如果遍历完树A仍未找到相同的节点，则返回false。
     * 2.	以找到的相同节点为起始点，判断树A中以该节点为根节点的子树是否包含树B。
     * •	如果树B为null，表示树B已经匹配完毕，返回true。
     * •	如果树A为null，表示树A已经遍历完毕，而树B还未匹配完毕，返回false。
     * •	如果树A的节点值与树B的节点值不相同，返回false。
     * •	分别判断树A的左子树和右子树是否包含树B，如果两者有一个为true，则返回true；否则返回false。
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
 
        // 在树A中找到与树B根节点值相同的节点
        if (A.val == B.val && isMatch(A, B)) {
            return true;
        }
 
        // 递归判断树A的左子树和右子树是否包含树B
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
 
    private boolean isMatch(TreeNode A, TreeNode B) {
        // 如果树B已经匹配完毕，返回true
        if (B == null) {
            return true;
        }
 
        // 如果树A遍历完毕，而树B还未匹配完毕，返回false
        if (A == null) {
            return false;
        }
 
        // 如果节点值不相同，返回false
        if (A.val != B.val) {
            return false;
        }
 
        // 递归判断树A的左子树和右子树是否包含树B
        return isMatch(A.left, B.left) && isMatch(A.right, B.right);
    }
 
    public static void main(String[] args) {
        SubStructure solution = new SubStructure();
 
        // 构建二叉树A
        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);
 
        // 构建二叉树B
        TreeNode B = new TreeNode(4);
        B.left = new TreeNode(1);
 
        boolean result = solution.isSubStructure(A, B);
        // 打印结果
        System.out.println(result);
    }
}

53.JZ27-二叉树的镜像-(知识点：树,难度：简单)

该题目直接可见树相关知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第12题。

54.JZ28-对称的二叉树-(知识点：树,难度：简单)

该题目直接可见树相关知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第4题。

55.JZ30—包含main函数的栈(知识点：栈,难度：简单)

该题目直接可见栈知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第2题。

理解得到栈最小元素的min函数这个功能，言外之意要求我们对当前栈弹出的应该是当前栈内的最小元素，而栈又是“先进后出”的数据结构，所以要确保通过每次压入比较得到最小元素，并将最小元素放到栈顶保证弹出时正好是当前栈的最小值，但这样就打破了栈的定义，所以我们需要添加一个成员变量来存放最小值同时需要新建一个辅助栈来实现每次弹出都保证弹出最小值。画个表分析如下：

这样一来如果每次都把最小元素压入辅助栈，那么就能保证辅助栈的栈顶一直是最小值。当最小元素从数据栈内被弹出之后，同时弹出辅助栈的栈顶元素，此时辅助栈的新栈顶元素就是下一个最小值。

56.JZ31-栈的压入弹出序列-(知识点：栈,难度：中等)

题目描述：给定两个整数数组 pushed 和 popped，分别表示压栈序列和弹出序列。判断该弹出序列是否可能是压栈序列的弹出顺序。

解题分析

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。不妨直接根据举例看能不能分析下它的规律，就以上述两种情况分析，如下表：

总结：判断一个序列是不是栈的弹出序列的规律：

如果下一个弹出的数字刚好为栈顶元素，那么直接弹出；
如果下一个弹出的数字不在栈顶，，我们把压栈序列中还没有入栈的数字压入到一个辅助栈，直到把下一个需要弹出的数字压入栈顶为止；
如果所有的数字都压入栈了，仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

根据规律编写代码：可以利用一个辅助栈来模拟压栈和弹出的过程。遍历压栈序列，依次将元素压入辅助栈中。每次压入后，都检查辅助栈的栈顶元素是否与弹出序列的当前元素相同。如果相同，则将栈顶元素弹出，并将弹出序列的指针向后移动一位。最后，检查辅助栈是否为空，若为空则说明弹出序列是合法的。

详细的解题步骤如下：

初始化一个辅助栈和一个指向弹出序列的指针popIndex，并将其初始值设为0。
遍历压栈序列，依次将元素压入辅助栈中。
每次压入后，判断辅助栈的栈顶元素是否与弹出序列中的当前元素相等。• 如果相等，则将栈顶元素弹出，并将popIndex指针后移一位。• 如果不相等，则继续压入下一个元素。
遍历完压栈序列后，检查辅助栈是否为空。如果为空，则说明弹出序列是合法的，返回true；否则返回false。

这种解法的时间复杂度是O(N)，其中N是压栈序列的长度。

请注意，题目中未明确规定压栈序列和弹出序列的长度是否相等或者存在重复元素，因此在实际解题时需要考虑这些情况。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.Stack;
 
/**
 * @author yanfengzhang
 * @description 给定两个整数数组 pushed 和 popped，分别表示压栈序列和弹出序列。
 * 判断该弹出序列是否可能是压栈序列的弹出顺序。
 * @date 2023/6/7  22:10
 */
public class StackSequences {
    /**
     * 可以利用一个辅助栈来模拟压栈和弹出的过程。遍历压栈序列，依次将元素压入辅助栈中。
     * 每次压入后，都检查辅助栈的栈顶元素是否与弹出序列的当前元素相同。
     * 如果相同，则将栈顶元素弹出，并将弹出序列的指针向后移动一位。
     * 最后，检查辅助栈是否为空，若为空则说明弹出序列是合法的。
     * 详细的解题步骤如下
     * 1.	初始化一个辅助栈和一个指向弹出序列的指针popIndex，并将其初始值设为0。
     * 2.	遍历压栈序列，依次将元素压入辅助栈中。
     * 3.	每次压入后，判断辅助栈的栈顶元素是否与弹出序列中的当前元素相等。
     * •	如果相等，则将栈顶元素弹出，并将popIndex指针后移一位。
     * •	如果不相等，则继续压入下一个元素。
     * 4.	遍历完压栈序列后，检查辅助栈是否为空。如果为空，则说明弹出序列是合法的，返回true；否则返回false。
     * 这种解法的时间复杂度是O(N)，其中N是压栈序列的长度。
     * 请注意，题目中未明确规定压栈序列和弹出序列的长度是否相等或者存在重复元素，因此在实际解题时需要考虑这些情况。
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack stack = new Stack<>();
        // 弹出序列的指针
        int popIndex = 0;
 
        for (int num : pushed) {
            // 将元素压入辅助栈
            stack.push(num);
 
            // 检查辅助栈的栈顶元素是否与弹出序列中的当前元素相等
            while (!stack.isEmpty() && stack.peek() == popped[popIndex]) {
                // 弹出栈顶元素
                stack.pop();
                // 弹出序列的指针后移一位
                popIndex++;
            }
        }
 
        // 检查辅助栈是否为空，如果为空则说明弹出序列是合法的
        return stack.isEmpty();
    }
 
    public static void main(String[] args) {
        StackSequences solution = new StackSequences();
 
        // 验证样例1
        int[] pushed1 = {1, 2, 3, 4, 5};
        int[] popped1 = {4, 5, 3, 2, 1};
        boolean result1 = solution.validateStackSequences(pushed1, popped1);
        // 输出: true
        System.out.println(result1);
 
        // 验证样例2
        int[] pushed2 = {1, 2, 3, 4, 5};
        int[] popped2 = {4, 3, 5, 1, 2};
        boolean result2 = solution.validateStackSequences(pushed2, popped2);
        // 输出: false
        System.out.println(result2);
    }
}

57.JZ7-重建二叉树-(知识点：树,难度：中等)

题目描述：给定二叉树的前序遍历和中序遍历的结果，请重建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，输入前序遍历序列 [3,9,20,15,7] 和中序遍历序列 [9,3,15,20,7]，则重建二叉树并返回其根节点。

解题分析

根据前序遍历的特点，第一个元素是根节点。根据中序遍历的特点，根节点的左边是左子树的中序遍历结果，右边是右子树的中序遍历结果。

定义一个递归函数 buildTree，接收前序遍历序列 preorder、中序遍历序列 inorder、前序遍历序列的起始位置 preStart、前序遍历序列的结束位置 preEnd、中序遍历序列的起始位置 inStart、中序遍历序列的结束位置 inEnd。
若 preStart > preEnd，说明当前子树为空，返回 null。
创建根节点，值为前序遍历序列的第一个元素 preorder[preStart]。
在中序遍历序列中找到根节点的位置，将中序遍历序列分为左子树和右子树的部分。
根据左子树的长度，确定前序遍历序列中左子树和右子树的范围。
递归构建左子树，调用 buildTree，传入相应的参数。
递归构建右子树，调用 buildTree，传入相应的参数。
返回根节点。

通过递归构建二叉树，可以得到最终的二叉树结构。

解题步骤：

创建 buildTree 函数，传入前序遍历序列 preorder 和中序遍历序列 inorder。
调用 buildTree 函数，传入相应的参数，返回重建后的二叉树的根节点。

这样，就能得到重建的二叉树。

注意：在实现中需要使用额外的数据结构，如数组、哈希表等，以便快速查找元素在中序遍历序列中的位置。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import org.zyf.javabasic.letcode.tree.base.TreeNode;
 
import java.util.HashMap;
import java.util.Map;
 
/**
 * @author yanfengzhang
 * @description 给定二叉树的前序遍历和中序遍历的结果，请重建该二叉树并返回其根节点。
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如，输入前序遍历序列 [3,9,20,15,7] 和中序遍历序列 [9,3,15,20,7]，则重建二叉树并返回其根节点。
 * @date 2023/6/7  00:15
 */
public class BuildTree {
    /**
     * 根据前序遍历的特点，第一个元素是根节点。根据中序遍历的特点，根节点的左边是左子树的中序遍历结果，右边是右子树的中序遍历结果。
     * 1.	定义一个递归函数 buildTree，接收前序遍历序列 preorder、中序遍历序列 inorder、前序遍历序列的起始位置 preStart、
     * 前序遍历序列的结束位置 preEnd、中序遍历序列的起始位置 inStart、中序遍历序列的结束位置 inEnd。
     * 2.	若 preStart > preEnd，说明当前子树为空，返回 null。
     * 3.	创建根节点，值为前序遍历序列的第一个元素 preorder[preStart]。
     * 4.	在中序遍历序列中找到根节点的位置，将中序遍历序列分为左子树和右子树的部分。
     * 5.	根据左子树的长度，确定前序遍历序列中左子树和右子树的范围。
     * 6.	递归构建左子树，调用 buildTree，传入相应的参数。
     * 7.	递归构建右子树，调用 buildTree，传入相应的参数。
     * 8.	返回根节点。
     * 通过递归构建二叉树，可以得到最终的二叉树结构。
     * 解题步骤：
     * 1.	创建 buildTree 函数，传入前序遍历序列 preorder 和中序遍历序列 inorder。
     * 2.	调用 buildTree 函数，传入相应的参数，返回重建后的二叉树的根节点。
     * 这样，就能得到重建的二叉树。
     * 注意：在实现中需要使用额外的数据结构，如数组、哈希表等，以便快速查找元素在中序遍历序列中的位置。
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 创建哈希表，用于快速查找中序遍历序列中元素的位置
        Map inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
 
        return buildTree(preorder,
                0,
                preorder.length - 1,
                inorder, 0,
                inorder.length - 1,
                inorderMap);
    }
 
    private TreeNode buildTree(int[] preorder,
                               int preStart,
                               int preEnd,
                               int[] inorder,
                               int inStart,
                               int inEnd,
                               Map inorderMap) {
        if (preStart > preEnd) {
            return null;
        }
 
        // 根据前序遍历序列的第一个元素创建根节点
        int rootValue = preorder[preStart];
        TreeNode root = new TreeNode(rootValue);
 
        // 在中序遍历序列中找到根节点的位置
        int rootIndex = inorderMap.get(rootValue);
 
        // 计算左子树的长度
        int leftSubtreeSize = rootIndex - inStart;
 
        // 递归构建左子树
        root.left = buildTree(preorder,
                preStart + 1,
                preStart + leftSubtreeSize,
                inorder,
                inStart,
                rootIndex - 1,
                inorderMap);
 
        // 递归构建右子树
        root.right = buildTree(preorder,
                preStart + leftSubtreeSize + 1,
                preEnd, inorder,
                rootIndex + 1,
                inEnd,
                inorderMap);
 
        return root;
    }
 
    public static void main(String[] args) {
        BuildTree solution = new BuildTree();
 
        // 构建前序遍历序列和中序遍历序列
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
 
        // 构建二叉树
        TreeNode root = solution.buildTree(preorder, inorder);
 
        // 验证结果
        // 二叉树构建完成后，可以根据需要进行遍历等操作
        // 这里只验证构建的树结构是否正确
        System.out.println(root.val);
        System.out.println(root.left.val);
        System.out.println(root.right.val);
    }
}

58.JZ8-二叉树的下一个结点-(知识点：树,难度：中等)

题目描述：给定一棵二叉树和其中的一个节点，请找出中序遍历顺序的下一个节点并返回。注意，树中的节点不仅包含左右子节点，同时包含指向父节点的指针。

解题分析

最优解题思路：根据中序遍历的顺序，下一个节点有以下几种情况：

如果当前节点有右子树，则下一个节点是右子树的最左节点；
如果当前节点没有右子树，但是它是其父节点的左子节点，则下一个节点是其父节点；
如果当前节点没有右子树，且它是其父节点的右子节点，则需要沿着父节点的指针一直向上找，直到找到一个节点是其父节点的左子节点，那么这个父节点就是下一个节点。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 给定一棵二叉树和其中的一个节点，请找出中序遍历顺序的下一个节点并返回。
 * 注意，树中的节点不仅包含左右子节点，同时包含指向父节点的指针。
 * @date 2023/6/8  23:30
 */
public class NextTreeNode {
    /**
     * 根据中序遍历的顺序，下一个节点有以下几种情况：
     * 1.	如果当前节点有右子树，则下一个节点是右子树的最左节点；
     * 2.	如果当前节点没有右子树，但是它是其父节点的左子节点，则下一个节点是其父节点；
     * 3.	如果当前节点没有右子树，且它是其父节点的右子节点，则需要沿着父节点的指针一直向上找，
     * 直到找到一个节点是其父节点的左子节点，那么这个父节点就是下一个节点。
     */
    public TreeNode getNext(TreeNode pNode) {
        if (pNode == null) {
            return null;
        }
 
        // 如果当前节点有右子树，则下一个节点是右子树的最左节点
        if (pNode.right != null) {
            TreeNode node = pNode.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }
 
        // 如果当前节点没有右子树，且它是其父节点的左子节点，则下一个节点是其父节点
        if (pNode.parent != null && pNode.parent.left == pNode) {
            return pNode.parent;
        }
 
        // 如果当前节点没有右子树，且它是其父节点的右子节点，则需要沿着父节点的指针向上找
        // 直到找到一个节点是其父节点的左子节点，那么这个父节点就是下一个节点
        TreeNode parent = pNode.parent;
        while (parent != null && parent.right == pNode) {
            pNode = parent;
            parent = pNode.parent;
        }
        return parent;
    }
 
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
 
        TreeNode(int val) {
            this.val = val;
        }
    }
 
    public static void main(String[] args) {
        NextTreeNode solution = new NextTreeNode();
 
        // 构建二叉树
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
 
        root.left = node2;
        root.right = node3;
        node2.parent = root;
        node3.parent = root;
 
        node2.left = node4;
        node2.right = node5;
        node4.parent = node2;
        node5.parent = node2;
 
        node3.left = node6;
        node3.right = node7;
        node6.parent = node3;
        node7.parent = node3;
 
        TreeNode next = solution.getNext(node5);
        if (next != null) {
            // 打印结果
            System.out.println(next.val);
        } else {
            System.out.println("null");
        }
    }
}

59. JZ32-回文串-(知识点：字符串,难度：简单)

题目描述：给定一个字符串，请编写一个函数判断它是否是一个回文串。回文串是指正着读和倒着读都一样的字符串，忽略字母的大小写。

解题分析

判断一个字符串是否是回文串的一种常见方法是使用双指针。定义两个指针，一个指向字符串的开头，另一个指向字符串的末尾。然后，分别向中间移动指针，并比较两个指针所指向的字符是否相同。具体步骤如下：

初始化两个指针，一个指向字符串的开头，即索引为 0，另一个指向字符串的末尾，即索引为字符串长度减一。
循环遍历字符串，直到两个指针相遇为止。
在循环中，比较两个指针所指向的字符是否相同。如果相同，则继续向中间移动指针；如果不同，则说明字符串不是回文串，返回 false。
如果循环结束时没有发现不同字符，则说明字符串是回文串，返回 true。

需要注意的是，在比较字符时应忽略字母的大小写。可以使用字符转换函数将字符统一转换为小写或大写，然后进行比较。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 给定一个字符串，请编写一个函数判断它是否是一个回文串。
 * 回文串是指正着读和倒着读都一样的字符串，忽略字母的大小写。
 * @date 2023/6/15  23:37
 */
public class PalindromeStr {
    /**
     * 判断一个字符串是否是回文串的一种常见方法是使用双指针。
     * 定义两个指针，一个指向字符串的开头，另一个指向字符串的末尾。
     * 然后，分别向中间移动指针，并比较两个指针所指向的字符是否相同。具体步骤如下：
     * 1.	初始化两个指针，一个指向字符串的开头，即索引为 0，另一个指向字符串的末尾，即索引为字符串长度减一。
     * 2.	循环遍历字符串，直到两个指针相遇为止。
     * 3.	在循环中，比较两个指针所指向的字符是否相同。如果相同，则继续向中间移动指针；如果不同，则说明字符串不是回文串，返回 false。
     * 4.	如果循环结束时没有发现不同字符，则说明字符串是回文串，返回 true。
     * 
     * 需要注意的是，在比较字符时应忽略字母的大小写。可以使用字符转换函数将字符统一转换为小写或大写，然后进行比较。
     */
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
 
        int left = 0;
        int right = s.length() - 1;
 
        while (left < right) {
            char c1 = Character.toLowerCase(s.charAt(left));
            char c2 = Character.toLowerCase(s.charAt(right));
 
            if (!Character.isLetterOrDigit(c1)) {
                left++;
            } else if (!Character.isLetterOrDigit(c2)) {
                right--;
            } else if (c1 != c2) {
                return false;
            } else {
                left++;
                right--;
            }
        }
 
        return true;
    }
 
    public static void main(String[] args) {
        PalindromeStr solution = new PalindromeStr();
        String s1 = "A man, a plan, a canal: Panama";
        String s2 = "race a car";
 
        boolean isPalindrome1 = solution.isPalindrome(s1);
        boolean isPalindrome2 = solution.isPalindrome(s2);
 
        // 输出: true
        System.out.println("字符串 \"" + s1 + "\" 是否是回文串: " + isPalindrome1);
        // 输出: false
        System.out.println("字符串 \"" + s2 + "\" 是否是回文串: " + isPalindrome2);
    }
}

60.JZ33-二叉搜索树的后序遍历序列-(知识点：树,难度：中等)

题目描述：输入一个整数数组 postorder，表示二叉搜索树的后序遍历序列。判断该序列是否是某个二叉搜索树的后序遍历结果。

解题分析

根据二叉搜索树的性质，后序遍历的最后一个元素是根节点，而前面的元素可以分为左子树和右子树两部分。左子树的所有元素都小于根节点的值，右子树的所有元素都大于根节点的值。

首先，找到根节点，即后序遍历序列的最后一个元素。然后，遍历序列，找到第一个大于根节点的元素，该元素之前的部分即为左子树的后序遍历序列，该元素之后的部分即为右子树的后序遍历序列。

接下来，递归地判断左子树和右子树是否是二叉搜索树的后序遍历序列。若左子树和右子树都是二叉搜索树的后序遍历序列，则整个序列是二叉搜索树的后序遍历序列。

递归的终止条件为序列为空或只有一个元素，此时即为二叉搜索树的后序遍历序列。

假设序列的长度为 n，递归过程中需要遍历整个序列，因此时间复杂度为 O(n)。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 输入一个整数数组 postorder，表示二叉搜索树的后序遍历序列。
 * 判断该序列是否是某个二叉搜索树的后序遍历结果。
 * @date 2023/6/10  22:09
 */
public class VerifyPostorder {
    /**
     * 根据二叉搜索树的性质，后序遍历的最后一个元素是根节点，而前面的元素可以分为左子树和右子树两部分.
     * 左子树的所有元素都小于根节点的值，右子树的所有元素都大于根节点的值。
     * 首先，找到根节点，即后序遍历序列的最后一个元素。
     * 然后，遍历序列，找到第一个大于根节点的元素，
     * 该元素之前的部分即为左子树的后序遍历序列，该元素之后的部分即为右子树的后序遍历序列。
     * 接下来，递归地判断左子树和右子树是否是二叉搜索树的后序遍历序列。
     * 若左子树和右子树都是二叉搜索树的后序遍历序列，则整个序列是二叉搜索树的后序遍历序列。
     * 
     * 递归的终止条件为序列为空或只有一个元素，此时即为二叉搜索树的后序遍历序列。
     * 【时间复杂度】假设序列的长度为 n，递归过程中需要遍历整个序列，因此时间复杂度为 O(n)。
     */
    public boolean verifyPostorder(int[] postorder) {
        if (postorder == null || postorder.length == 0) {
            return true;
        }
 
        return verify(postorder, 0, postorder.length - 1);
    }
 
    private boolean verify(int[] postorder, int start, int end) {
        // 终止条件：当start大于等于end时，表示只有一个节点或没有节点，满足条件
        if (start >= end) {
            return true;
        }
 
        // 根节点的值
        int root = postorder[end];
        // 左子树的最后一个节点
        int leftEnd = start;
 
        // 找到左子树的边界，左子树的所有节点值小于根节点的值
        while (postorder[leftEnd] < root) {
            leftEnd++;
        }
 
        // 遍历右子树，右子树的所有节点值大于根节点的值
        for (int i = leftEnd; i < end; i++) {
            if (postorder[i] < root) {
                // 右子树中存在小于根节点的值，不满足二叉搜索树的性质
                return false;
            }
        }
 
        // 递归判断左子树和右子树是否是二叉搜索树的后序遍历序列
        return verify(postorder, start, leftEnd - 1) && verify(postorder, leftEnd, end - 1);
    }
 
    public static void main(String[] args) {
        VerifyPostorder solution = new VerifyPostorder();
 
        // 测试用例1: 是二叉搜索树的后序遍历序列
        int[] postorder1 = {1, 3, 2, 6, 5};
        boolean result1 = solution.verifyPostorder(postorder1);
        // 输出: true
        System.out.println(result1);
 
        // 测试用例2: 不是二叉搜索树的后序遍历序列
        int[] postorder2 = {1, 6, 3, 2, 5};
        boolean result2 = solution.verifyPostorder(postorder2);
        // 输出: false
        System.out.println(result2);
    }
}

61.JZ82-判断二叉树中是否存在和为某一个值的路径-(知识点：树,难度：简单)

题目描述：给定一个二叉树和一个目标值target，判断该二叉树中是否存在从根节点到叶子节点的路径，使得路径上的节点值之和等于target。

解题分析

可以使用递归的方式来解决该问题。从根节点开始，递归地遍历左子树和右子树，并更新目标值为target减去当前节点的值。如果当前节点是叶子节点且目标值等于当前节点的值，说明存在路径满足要求。否则，继续递归遍历左子树和右子树。最终返回左子树或右子树中是否存在满足要求的路径。

具体步骤如下：

如果根节点为空，直接返回false。
如果根节点是叶子节点且目标值等于当前节点的值，返回true。
递归遍历左子树和右子树，更新目标值为target减去当前节点的值，并判断左子树或右子树中是否存在满足要求的路径，如果存在，则返回true。
如果左子树和右子树中都不存在满足要求的路径，返回false。

这种递归的解法可以利用二叉树的前序遍历实现。

时间复杂度分析：假设二叉树的节点数为N，每个节点都需要遍历一次，因此时间复杂度为O(N)。

空间复杂度分析：递归调用栈的深度最大为二叉树的高度，如果二叉树是平衡二叉树，则空间复杂度为O(logN)；如果二叉树是非平衡二叉树，则空间复杂度为O(N)。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import org.zyf.javabasic.letcode.tree.base.TreeNode;
 
/**
 * @author yanfengzhang
 * @description 给定一个二叉树和一个目标值target，
 * 判断该二叉树中是否存在从根节点到叶子节点的路径，使得路径上的节点值之和等于target。
 * @date 2023/6/10  23:12
 */
public class verifyPathSumTree {
    /**
     * 可以使用递归的方式来解决该问题。从根节点开始，递归地遍历左子树和右子树，并更新目标值为target减去当前节点的值。
     * 如果当前节点是叶子节点且目标值等于当前节点的值，说明存在路径满足要求。
     * 否则，继续递归遍历左子树和右子树。最终返回左子树或右子树中是否存在满足要求的路径。
     * 具体步骤如下：
     * 1.	如果根节点为空，直接返回false。
     * 2.	如果根节点是叶子节点且目标值等于当前节点的值，返回true。
     * 3.	递归遍历左子树和右子树，更新目标值为target减去当前节点的值，并判断左子树或右子树中是否存在满足要求的路径，如果存在，则返回true。
     * 4.	如果左子树和右子树中都不存在满足要求的路径，返回false。
     * 
     * 这种递归的解法可以利用二叉树的前序遍历实现。
     * 时间复杂度分析：假设二叉树的节点数为N，每个节点都需要遍历一次，因此时间复杂度为O(N)。
     * 空间复杂度分析：递归调用栈的深度最大为二叉树的高度，
     * 如果二叉树是平衡二叉树，则空间复杂度为O(logN)；如果二叉树是非平衡二叉树，则空间复杂度为O(N)。
     */
    public boolean hasPathSum(TreeNode root, int target) {
        // 根节点为空，返回false
        if (root == null) {
            return false;
        }
 
        // 当前节点是叶子节点且目标值等于当前节点的值，返回true
        if (root.left == null && root.right == null && target == root.val) {
            return true;
        }
 
        // 递归遍历左子树和右子树，更新目标值为target减去当前节点的值
        boolean leftResult = hasPathSum(root.left, target - root.val);
        boolean rightResult = hasPathSum(root.right, target - root.val);
 
        // 如果左子树或右子树存在满足要求的路径，返回true
        if (leftResult || rightResult) {
            return true;
        }
 
        // 左子树和右子树都不存在满足要求的路径，返回false
        return false;
    }
 
    public static void main(String[] args) {
        verifyPathSumTree solution = new verifyPathSumTree();
 
        // 构建二叉树
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);
 
        int target = 22;
        boolean result = solution.hasPathSum(root, target);
        System.out.println(result);
    }
 
}

62.JZ34-二叉树中从根结点到叶子结点和为某一个值的所有路径-(知识点：树,难度：中等)

题目描述：输入一颗二叉树的根结点和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

解题分析

使用回溯法（Backtracking）解决问题。从根节点开始遍历树，每遍历到一个节点，将当前节点加入路径中，并更新目标值。然后分别递归遍历当前节点的左子树和右子树。当遍历到叶子节点时，判断当前路径上节点值之和是否等于目标值，如果是，则将当前路径加入结果集中。最后将当前节点从路径中移除，继续遍历其他路径。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import org.zyf.javabasic.letcode.tree.base.TreeNode;
 
import java.util.ArrayList;
 
/**
 * @author yanfengzhang
 * @description 输入一颗二叉树的根结点和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。
 * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 * @date 2023/6/11  22:15
 */
public class FindPathInTree {
    /**
     * 使用回溯法（Backtracking）解决问题。
     * 从根节点开始遍历树，每遍历到一个节点，将当前节点加入路径中，并更新目标值。
     * 然后分别递归遍历当前节点的左子树和右子树。
     * 当遍历到叶子节点时，判断当前路径上节点值之和是否等于目标值，
     * 如果是，则将当前路径加入结果集中。
     * 最后将当前节点从路径中移除，继续遍历其他路径。
     */
    public ArrayList> findPath(TreeNode root, int target) {
        ArrayList> result = new ArrayList<>();
        ArrayList path = new ArrayList<>();
 
        findPathHelper(root, target, path, result);
 
        return result;
    }
 
    private void findPathHelper(TreeNode root, int target,
                                ArrayList path,
                                ArrayList> result) {
        // 当前节点为空，直接返回
        if (root == null) {
            return;
        }
 
        // 将当前节点加入路径中
        path.add(root.val);
 
        // 当前节点是叶子节点且目标值等于当前节点的值
        if (root.left == null && root.right == null && target == root.val) {
            // 将当前路径加入结果集
            result.add(new ArrayList<>(path));
        }
 
        // 递归遍历左子树和右子树，更新目标值为target减去当前节点的值
        findPathHelper(root.left, target - root.val, path, result);
        findPathHelper(root.right, target - root.val, path, result);
 
        // 当前节点遍历完成后，将当前节点从路径中移除，回溯到上一层节点
        path.remove(path.size() - 1);
    }
 
    public static void main(String[] args) {
        FindPathInTree solution = new FindPathInTree();
 
        // 构建二叉树
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(12);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(7);
 
        int target = 22;
        ArrayList> result = solution.findPath(root, target);
        System.out.println(result);
    }
}

63.JZ84-最大公约数和最小公倍数-(知识点：基础数学,难度：中等)

题目描述：给定两个正整数 a 和 b，求它们的最大公约数和最小公倍数。

解题分析

可以利用辗转相除法求解最大公约数。该算法基于如下原理：两个数的最大公约数等于其中较小数和两数相除的余数的最大公约数。具体步骤如下：

若 a 小于 b，则交换 a 和 b 的值，保证 a 大于等于 b。
若 b 等于 0，则 a 即为最大公约数，返回 a。
计算 a 除以 b 的余数，即 a mod b，将其赋值给临时变量 temp。
将 b 赋值给 a，将 temp 赋值给 b。
重复步骤 2-4，直到 b 等于 0，此时 a 即为最大公约数。

最小公倍数可以通过最大公约数求解。两个数的最小公倍数等于两数相乘的结果除以最大公约数。因此，可以先求解最大公约数，然后用两数相乘除以最大公约数即可得到最小公倍数。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 给定两个正整数 a 和 b，求它们的最大公约数和最小公倍数。
 * @date 2023/6/16  23:39
 */
public class GCDAndLCM {
    /**
     * 最大公约数 - Greatest Common Divisor (GCD)
     */
    public int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
 
    /**
     * 最小公倍数 - Least Common Multiple (LCM)
     */
    public int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
 
    public static void main(String[] args) {
        GCDAndLCM solution = new GCDAndLCM();
        int a = 12;
        int b = 18;
        int gcd = solution.gcd(a, b);
        int lcm = solution.lcm(a, b);
        // 输出: 6
        System.out.println("最大公约数: " + gcd);
        // 输出: 36
        System.out.println("最小公倍数: " + lcm);
    }
}

64.JZ36-二叉搜索树与双向链表-(知识点：分治,难度：中等)

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

解题分析

本题可以使用中序遍历的思想进行求解。具体步骤如下：

定义一个全局变量 pre，用于保存当前节点的前一个节点。
定义一个递归函数 convertHelper，接收一个当前节点作为参数。
在 convertHelper 中，首先递归处理当前节点的左子树，即调用 convertHelper(node.left)。
在左子树递归完成后，将当前节点与前一个节点 pre 建立双向连接关系，即 node.left = pre，if pre != null then pre.right = node。
更新 pre 为当前节点 node。
递归处理当前节点的右子树，即调用 convertHelper(node.right)。
最后返回双向链表的头节点，即最左侧的节点。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import org.zyf.javabasic.letcode.tree.base.TreeNode;
 
/**
 * @author yanfengzhang
 * @description 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
 * 要求不能创建任何新的节点，只能调整树中节点指针的指向。
 * @date 2023/6/12  22:25
 */
public class TreeListConvert {
    // 全局变量，用于保存当前节点的前一个节点
    private TreeNode pre;
 
    /**
     * 本题可以使用中序遍历的思想进行求解。具体步骤如下：
     * 1.	定义一个全局变量 pre，用于保存当前节点的前一个节点。
     * 2.	定义一个递归函数 convertHelper，接收一个当前节点作为参数。
     * 3.	在 convertHelper 中，首先递归处理当前节点的左子树，即调用 convertHelper(node.left)。
     * 4.	在左子树递归完成后，将当前节点与前一个节点 pre 建立双向连接关系，即 node.left = pre，if pre != null then pre.right = node。
     * 5.	更新 pre 为当前节点 node。
     * 6.	递归处理当前节点的右子树，即调用 convertHelper(node.right)。
     * 7.	最后返回双向链表的头节点，即最左侧的节点。
     */
    public TreeNode convert(TreeNode root) {
        if (root == null) {
            return null;
        }
 
        // 递归处理二叉搜索树
        convertHelper(root);
 
        // 返回双向链表的头节点，即最左侧的节点
        TreeNode head = root;
        while (head.left != null) {
            head = head.left;
        }
        return head;
    }
 
    private void convertHelper(TreeNode node) {
        if (node == null) {
            return;
        }
 
        // 递归处理左子树
        convertHelper(node.left);
 
        // 当前节点与前一个节点建立双向连接
        node.left = pre;
        if (pre != null) {
            pre.right = node;
        }
        pre = node;
 
        // 递归处理右子树
        convertHelper(node.right);
    }
 
    public static void main(String[] args) {
        TreeListConvert solution = new TreeListConvert();
 
        // 构建二叉搜索树
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
 
        TreeNode result = solution.convert(root);
        printDoubleLinkedList(result);
    }
 
    // 打印双向链表
    private static void printDoubleLinkedList(TreeNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.right;
        }
    }
}

65.JZ37-序列化二叉树-(知识点：树,难度：较难)

该题目直接可见树相关知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第13题。

66.JZ40-最小的K个数-(知识点：排序,难度：中等)

题目描述：输入一个整数数组，找出其中最小的K个数。例如，输入数组为[4,5,1,6,2,7,3,8]，则最小的4个数为[1,2,3,4]。

解题分析

可以使用堆排序或者快速选择算法来解决该问题。

堆排序思路：

构建一个最大堆，堆中存放数组的前K个元素。
遍历数组的剩余元素，如果当前元素比堆顶元素小，则将堆顶元素替换为当前元素，并进行堆调整。
遍历完数组后，堆中的元素即为最小的K个数。

快速选择思路：

使用快速排序的思想进行选择。
随机选择一个枢轴元素，将数组分为两部分，左边部分小于等于枢轴元素，右边部分大于枢轴元素。
如果枢轴元素的下标恰好等于K-1，则左边部分的元素即为最小的K个数。
如果枢轴元素的下标大于K-1，则在左边部分继续快速选择。
如果枢轴元素的下标小于K-1，则在右边部分继续快速选择。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.ArrayList;
 
/**
 * @author yanfengzhang
 * @description 输入一个整数数组，找出其中最小的K个数。
 * 例如，输入数组为[4,5,1,6,2,7,3,8]，则最小的4个数为[1,2,3,4]。
 * @date 2023/6/12  23:29
 */
public class LeastNumbers {
    /**
     * 可以使用堆排序或者快速选择算法来解决该问题。
     * 堆排序思路：
     * •	构建一个最大堆，堆中存放数组的前K个元素。
     * •	遍历数组的剩余元素，如果当前元素比堆顶元素小，则将堆顶元素替换为当前元素，并进行堆调整。
     * •	遍历完数组后，堆中的元素即为最小的K个数。
     * 
     * 快速选择思路：
     * •	使用快速排序的思想进行选择。
     * •	随机选择一个枢轴元素，将数组分为两部分，左边部分小于等于枢轴元素，右边部分大于枢轴元素。
     * •	如果枢轴元素的下标恰好等于K-1，则左边部分的元素即为最小的K个数。
     * •	如果枢轴元素的下标大于K-1，则在左边部分继续快速选择。
     * •	如果枢轴元素的下标小于K-1，则在右边部分继续快速选择
     */
    public ArrayList getLeastNumbers(int[] input, int k) {
        ArrayList result = new ArrayList<>();
 
        if (input == null || input.length == 0 || k <= 0 || k > input.length) {
            return result;
        }
 
        // 使用快速选择算法
        quickSelect(input, 0, input.length - 1, k);
 
        // 将最小的K个数加入结果列表
        for (int i = 0; i < k; i++) {
            result.add(input[i]);
        }
 
        return result;
    }
 
    private void quickSelect(int[] nums, int left, int right, int k) {
        if (left >= right) {
            return;
        }
 
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == k - 1) {
            return;
        } else if (pivotIndex > k - 1) {
            quickSelect(nums, left, pivotIndex - 1, k);
        } else {
            quickSelect(nums, pivotIndex + 1, right, k);
        }
    }
 
    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int i = left + 1;
        int j = right;
 
        while (true) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
 
            while (i <= j && nums[j] > pivot) {
                j--;
            }
 
            if (i > j) {
                break;
            }
 
            swap(nums, i, j);
            i++;
            j--;
        }
 
        swap(nums, left, j);
        return j;
    }
 
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
 
    public static void main(String[] args) {
        LeastNumbers solution = new LeastNumbers();
 
        int[] input = {4, 5, 1, 6, 2, 7, 3, 8};
        int k = 4;
 
        ArrayList result = solution.getLeastNumbers(input, k);
        System.out.println(result);
    }
}

67.JZ41数据流中的中位数-(知识点：排序,难度：中等)

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

解题分析

我们可以使用两个堆来解决这个问题：一个最大堆用于存储数据流中较小的一半数值，一个最小堆用于存储数据流中较大的一半数值。其中最大堆中的数都小于最小堆中的数。

每当读入一个新的数值，我们先判断两个堆的大小。如果两个堆的大小相等，说明数据流中已经读入偶数个数值，此时将该数值插入最大堆中，然后将最大堆的堆顶元素插入最小堆中。如果两个堆的大小不相等，说明数据流中已经读入奇数个数值，此时将该数值插入最小堆中，然后将最小堆的堆顶元素插入最大堆中。

这样，无论是奇数个还是偶数个数值，中位数都可以通过最大堆和最小堆的堆顶元素来计算得到。需要注意的是，为了保证最大堆中的元素都小于最小堆中的元素，我们在插入数值时需要做一些调整操作。

最终，我们可以通过查询最大堆和最小堆的堆顶元素来得到中位数。该解法的时间复杂度为O(logn)。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.PriorityQueue;
 
/**
 * @author yanfengzhang
 * @description 如何得到一个数据流中的中位数？
 * 如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值；
 * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 * @date 2023/6/13  23:33
 */
public class MedianInStream {
    // 最大堆，存储数据流中较小的一半数值
    private PriorityQueue maxHeap;
    // 最小堆，存储数据流中较大的一半数值
    private PriorityQueue minHeap;
 
    public MedianInStream() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }
 
    public void insert(Integer num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
 
        // 调整两个堆的大小，保证最大堆的大小不小于最小堆的大小
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
 
    public Double getMedian() {
        // 数据流中的数值个数为奇数，直接返回最大堆的堆顶元素
        if (maxHeap.size() > minHeap.size()) {
            return (double) maxHeap.peek();
        }
        // 数据流中的数值个数为偶数，返回最大堆和最小堆堆顶元素的平均值
        else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
 
    public static void main(String[] args) {
        MedianInStream solution = new MedianInStream();
 
        // 向数据流中插入数值
        solution.insert(1);
        solution.insert(2);
        solution.insert(3);
        solution.insert(4);
 
        // 获取中位数并打印结果// 输出: 2.5
        System.out.println(solution.getMedian());
    }
 
}

68.JZ44-数字序列中某一位的数字-(知识点：模拟,难度：简单)

题目描述：数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。

解题分析

我们可以观察到数字序列的规律，可以分为以下几个步骤：

确定目标数字所在的数字位数（位数从1开始），例如第9位是两位数。
确定目标数字所在的具体数字。例如，对于两位数，我们需要确定是10、11、12还是其他数字。
确定目标数字在所在数字中的位置。例如，对于两位数，我们需要确定是第一位还是第二位。

根据以上步骤，我们可以通过模拟来解题。具体步骤如下：

初始化变量digits为1，表示当前数字的位数。
初始化变量count为9，表示当前位数的数字总个数。
初始化变量start为1，表示当前位数的起始数字。
当n小于digits * count时，说明目标数字一定在当前位数的数字中，进行下一步操作。
计算目标数字在当前位数的数字中的位置，即index = (n - 1) / digits。
计算目标数字具体是哪个数字，即num = start + index。
计算目标数字在具体数字中的位置，即position = (n - 1) % digits。
将目标数字转化为字符串，并返回第position位上的数字。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 数字以0123456789101112131415…的格式序列化到一个字符序列中。
 * 在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。
 * 请写一个函数，求任意第n位对应的数字。
 * @date 2023/6/8  22:22
 */
public class DigitAtIndex {
    /**
     * 我们可以观察到数字序列的规律，可以分为以下几个步骤：
     * 1.	确定目标数字所在的数字位数（位数从1开始），例如第9位是两位数。
     * 2.	确定目标数字所在的具体数字。例如，对于两位数，我们需要确定是10、11、12还是其他数字。
     * 3.	确定目标数字在所在数字中的位置。例如，对于两位数，我们需要确定是第一位还是第二位。
     * 根据以上步骤，我们可以通过模拟来解题。具体步骤如下：
     * 1.	初始化变量digits为1，表示当前数字的位数。
     * 2.	初始化变量count为9，表示当前位数的数字总个数。
     * 3.	初始化变量start为1，表示当前位数的起始数字。
     * 4.	当n小于digits * count时，说明目标数字一定在当前位数的数字中，进行下一步操作。
     * 5.	计算目标数字在当前位数的数字中的位置，即index = (n - 1) / digits。
     * 6.	计算目标数字具体是哪个数字，即num = start + index。
     * 7.	计算目标数字在具体数字中的位置，即position = (n - 1) % digits。
     * 8.	将目标数字转化为字符串，并返回第position位上的数字。
     */
    public int digitAtIndex(int n) {
        if (n < 0) {
            return -1;
        }
 
        // 当前数字的位数
        int digits = 1;
        // 当前位数的数字总个数
        long count = 9;
        // 当前位数的起始数字
        int start = 1;
 
        while (n > digits * count) {
            n -= digits * count;
            digits++;
            count *= 10;
            start *= 10;
        }
 
        // 目标数字
        int num = start + (n - 1) / digits;
        // 目标数字在具体数字中的位置
        int position = (n - 1) % digits;
 
        String numStr = String.valueOf(num);
        return numStr.charAt(position) - '0';
    }
 
    public static void main(String[] args) {
        DigitAtIndex solution = new DigitAtIndex();
 
        int n = 5;
        int digit = solution.digitAtIndex(n);
        System.out.println("The digit at index " + n + " is: " + digit);
    }
 
}

69.JZ46-把数字翻译成字符串-(知识点：动态规划,难度：中等)

题目描述：给定一个数字，按照如下规则把它翻译成字符串：0翻译成”a”，1翻译成”b”，……，25翻译成”z”。一个数字可能有多个翻译。求给定数字所有可能的翻译方法的总数。

解题分析

这是一个动态规划的问题。我们可以定义一个dp数组，其中dp[i]表示前i个数字的翻译方法的总数。对于当前位置i，有两种情况：

如果第i-1位和第i位组成的两位数在10到25之间（包含10和25），那么可以把第i位和第i-1位看作一个整体进行翻译。则dp[i] = dp[i-2] + dp[i-1]。
如果第i-1位和第i位组成的两位数不在10到25之间，那么只能把第i位单独翻译。则dp[i] = dp[i-1]。

初始情况下，dp[0] = 1，dp[1] = 1，因为只有一个数字时只有一种翻译方式。

最终结果为dp[n]，其中n为给定数字的位数。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 给定一个数字，按照如下规则把它翻译成字符串：0翻译成”a”，1翻译成”b”，……，25翻译成”z”。
 * 一个数字可能有多个翻译。求给定数字所有可能的翻译方法的总数。
 * @date 2023/6/8  22:25
 */
public class TranslateNumToStr {
    /**
     * 这是一个动态规划的问题。我们可以定义一个dp数组，其中dp[i]表示前i个数字的翻译方法的总数。
     * 对于当前位置i，有两种情况：
     * 1.	如果第i-1位和第i位组成的两位数在10到25之间（包含10和25），那么可以把第i位和第i-1位看作一个整体进行翻译。则dp[i] = dp[i-2] + dp[i-1]。
     * 2.	如果第i-1位和第i位组成的两位数不在10到25之间，那么只能把第i位单独翻译。则dp[i] = dp[i-1]。
     * 初始情况下，dp[0] = 1，dp[1] = 1，因为只有一个数字时只有一种翻译方式。
     * 最终结果为dp[n]，其中n为给定数字的位数。
     */
    public int translateNum(int num) {
        String numStr = String.valueOf(num);
        int n = numStr.length();
 
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
 
        for (int i = 2; i <= n; i++) {
            String twoDigits = numStr.substring(i - 2, i);
            if (twoDigits.compareTo("10") >= 0 && twoDigits.compareTo("25") <= 0) {
                dp[i] = dp[i - 2] + dp[i - 1];
            } else {
                dp[i] = dp[i - 1];
            }
        }
 
        return dp[n];
    }
 
    public static void main(String[] args) {
        TranslateNumToStr solution = new TranslateNumToStr();
 
        int num = 12258;
        int count = solution.translateNum(num);
        System.out.println("The total number of translation methods is: " + count);
    }
}

70.JZ54-二叉树的深度-(知识点：树,难度：简单)

该题目直接可见树相关知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第2题。

71.JZ59-滑动窗口的最大值-(知识点：队列,难度：较难)

该题目直接可见队列知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第4题。

72.JZ61-扑克牌顺子-(知识点：模拟,难度：简单)

题目描述：从扑克牌中随机抽取 5 张牌，判断是不是一个顺子，即这 5 张牌是否连续。其中 A 表示 1，J 表示 11，Q 表示 12，K 表示 13，而大、小王可以看成任意数字。

解题分析

要判断一手牌是否为顺子，需要满足以下条件：

除了大小王以外，牌中没有重复的数字；
所有牌中的最大值减去最小值小于等于 4。

具体步骤如下：

对数组进行排序，将大小王放在最后，以便判断最大值和最小值；
统计大小王的个数，记为 count；
统计排序后的数组中相邻数字之间的间隔数目，记为 gap；
如果 gap 小于等于 count，说明可以通过使用大小王填补间隔，构成连续的顺子；
如果 gap 大于 count，说明无法通过大小王填补间隔，不能构成连续的顺子。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.Arrays;
 
/**
 * @author yanfengzhang
 * @description 从扑克牌中随机抽取 5 张牌，判断是不是一个顺子，即这 5 张牌是否连续。
 * 其中 A 表示 1，J 表示 11，Q 表示 12，K 表示 13，而大、小王可以看成任意数字。
 * @date 2023/6/8  22:36
 */
public class StraightPoker {
    /**
     * 要判断一手牌是否为顺子，需要满足以下条件：
     * 1.	除了大小王以外，牌中没有重复的数字；
     * 2.	所有牌中的最大值减去最小值小于等于 4。
     * 具体步骤如下：
     * 1.	对数组进行排序，将大小王放在最后，以便判断最大值和最小值；
     * 2.	统计大小王的个数，记为 count；
     * 3.	统计排序后的数组中相邻数字之间的间隔数目，记为 gap；
     * 4.	如果 gap 小于等于 count，说明可以通过使用大小王填补间隔，构成连续的顺子；
     * 5.	如果 gap 大于 count，说明无法通过大小王填补间隔，不能构成连续的顺子。
     */
    public boolean isStraight(int[] nums) {
        if (nums == null || nums.length != 5) {
            return false;
        }
 
        // 对数组进行排序
        Arrays.sort(nums);
 
        // 大小王的个数
        int count = 0;
        // 相邻数字之间的间隔数目
        int gap = 0;
 
        // 统计大小王的个数
        for (int num : nums) {
            if (num == 0) {
                count++;
            }
        }
 
        // 统计相邻数字之间的间隔数目
        for (int i = count; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                // 存在重复数字，不是顺子
                return false;
            }
            gap += nums[i + 1] - nums[i] - 1;
        }
 
        // 判断是否可以通过大小王填补间隔
        return gap <= count;
    }
 
    public static void main(String[] args) {
        StraightPoker solution = new StraightPoker();
        int[] nums1 = {1, 2, 3, 4, 5};
        int[] nums2 = {0, 0, 1, 2, 5};
        // true
        System.out.println(solution.isStraight(nums1));
        // true
        System.out.println(solution.isStraight(nums2));
    }
 
}

73.JZ69-跳台阶-(知识点：动态规划,难度：简单)

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

解题分析

我们可以使用动态规划的思路来解决这个问题。设跳上第 n 级台阶的跳法总数为 f(n)。青蛙最后一步可以跳上第 n-1 级台阶，也可以跳上第 n-2 级台阶。

如果青蛙最后一步跳上第 n-1 级台阶，那么前面的跳法总数为 f(n-1)。
如果青蛙最后一步跳上第 n-2 级台阶，那么前面的跳法总数为 f(n-2)。

所以，跳上第 n 级台阶的总跳法数为 f(n) = f(n-1) + f(n-2)。其中，初始条件为 f(1) = 1，f(2) = 2。

具体步骤如下：

定义一个数组 dp，dp[i] 表示跳上第 i 级台阶的跳法总数。
初始化 dp[1] = 1，dp[2] = 2。
从 i = 3 开始遍历到 n，根据状态转移方程 dp[i] = dp[i-1] + dp[i-2] 计算 dp[i] 的值。
返回 dp[n]，即跳上第 n 级台阶的跳法总数。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 一个青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。
 * 求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
 * @date 2023/6/8  22:38
 */
public class JumpFloorI {
    /**
     * 设跳上第 n 级台阶的跳法总数为 f(n)。青蛙最后一步可以跳上第 n-1 级台阶，也可以跳上第 n-2 级台阶。
     * •	如果青蛙最后一步跳上第 n-1 级台阶，那么前面的跳法总数为 f(n-1)。
     * •	如果青蛙最后一步跳上第 n-2 级台阶，那么前面的跳法总数为 f(n-2)。
     * 所以，跳上第 n 级台阶的总跳法数为 f(n) = f(n-1) + f(n-2)。其中，初始条件为 f(1) = 1，f(2) = 2。
     * 具体步骤如下：
     * 1.	定义一个数组 dp，dp[i] 表示跳上第 i 级台阶的跳法总数。
     * 2.	初始化 dp[1] = 1，dp[2] = 2。
     * 3.	从 i = 3 开始遍历到 n，根据状态转移方程 dp[i] = dp[i-1] + dp[i-2] 计算 dp[i] 的值。
     * 4.	返回 dp[n]，即跳上第 n 级台阶的跳法总数。
     */
    public int jumpFloor(int n) {
        if (n <= 2) {
            return n;
        }
 
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
 
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
 
        return dp[n];
    }
 
    public static void main(String[] args) {
        JumpFloorI solution = new JumpFloorI();
        int n = 5;
        // 输出结果为 8
        System.out.println(solution.jumpFloor(n));
    }
 
}

74.JZ71-跳台阶扩展问题-(知识点：动态规划,难度：简单)

题目描述：一个青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶，或者跳上 m 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

解题分析

这是跳台阶问题的扩展版本，可以使用动态规划的思路来解决。设跳上第 n 级台阶的跳法总数为 f(n)。青蛙最后一步可以跳上第 n-1 级台阶，也可以跳上第 n-2 级台阶，或者跳上第 n-m 级台阶。

如果青蛙最后一步跳上第 n-1 级台阶，那么前面的跳法总数为 f(n-1)。
如果青蛙最后一步跳上第 n-2 级台阶，那么前面的跳法总数为 f(n-2)。
如果青蛙最后一步跳上第 n-m 级台阶，那么前面的跳法总数为 f(n-m)。

所以，跳上第 n 级台阶的总跳法数为 f(n) = f(n-1) + f(n-2) + … + f(n-m)。其中，初始条件为 f(1) = 1，f(2) = 2，…，f(m) = m。

具体步骤如下：

定义一个数组 dp，dp[i] 表示跳上第 i 级台阶的跳法总数。
初始化 dp[1] = 1，dp[2] = 2，…，dp[m] = m。
从 i = m+1 开始遍历到 n，根据状态转移方程 dp[i] = dp[i-1] + dp[i-2] + … + dp[i-m] 计算 dp[i] 的值。
返回 dp[n]，即跳上第 n 级台阶的跳法总数。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 一个青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶，或者跳上 m 级台阶。
 * 求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
 * @date 2023/6/8  22:41
 */
public class JumpFloorII {
    /**
     * 设跳上第 n 级台阶的跳法总数为 f(n)。青蛙最后一步可以跳上第 n-1 级台阶，也可以跳上第 n-2 级台阶，或者跳上第 n-m 级台阶。
     * •	如果青蛙最后一步跳上第 n-1 级台阶，那么前面的跳法总数为 f(n-1)。
     * •	如果青蛙最后一步跳上第 n-2 级台阶，那么前面的跳法总数为 f(n-2)。
     * •	如果青蛙最后一步跳上第 n-m 级台阶，那么前面的跳法总数为 f(n-m)。
     * 所以，跳上第 n 级台阶的总跳法数为 f(n) = f(n-1) + f(n-2) + … + f(n-m)。其中，初始条件为 f(1) = 1，f(2) = 2，…，f(m) = m。
     * 
     * 具体步骤如下：
     * 1.	定义一个数组 dp，dp[i] 表示跳上第 i 级台阶的跳法总数。
     * 2.	初始化 dp[1] = 1，dp[2] = 2，…，dp[m] = m。
     * 3.	从 i = m+1 开始遍历到 n，根据状态转移方程 dp[i] = dp[i-1] + dp[i-2] + … + dp[i-m] 计算 dp[i] 的值。
     * 4.	返回 dp[n]，即跳上第 n 级台阶的跳法总数。
     */
    public int jumpFloorII(int n, int m) {
        if (n <= m) {
            return n;
        }
 
        int[] dp = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            dp[i] = i;
        }
 
        for (int i = m + 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i] += dp[i - j];
            }
        }
 
        return dp[n];
    }
 
    public static void main(String[] args) {
        JumpFloorII solution = new JumpFloorII();
        int n = 5;
        int m = 2;
        // 输出结果为 8
        System.out.println(solution.jumpFloorII(n, m));
    }
}

75.JZ70-矩阵覆盖-(知识点：动态规划,难度：中等)

题目描述：我们可以用 2x1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2x1 的小矩形无重叠地覆盖一个 2xn 的大矩形，总共有多少种方法？

解题分析

这是一个经典的动态规划问题，可以使用递推的方式解决。设覆盖 2xn 大矩形的方法数为 f(n)。我们考虑最后一步，可以使用一个 2x1 的小矩形横着放在最后一列，也可以使用两个 2x1 的小矩形竖着放在最后一列。

如果最后一列使用一个横着放置的小矩形，那么前面的方法数为 f(n-1)。
如果最后一列使用两个竖着放置的小矩形，那么前面的方法数为 f(n-2)。

因此，覆盖 2xn 大矩形的方法数为 f(n) = f(n-1) + f(n-2)。初始条件为 f(1) = 1，f(2) = 2。

具体步骤如下：

定义一个数组 dp，dp[i] 表示覆盖 2xi 大矩形的方法数。
初始化 dp[1] = 1，dp[2] = 2。
从 i = 3 开始遍历到 n，根据状态转移方程 dp[i] = dp[i-1] + dp[i-2] 计算 dp[i] 的值。
返回 dp[n]，即覆盖 2xn 大矩形的方法数。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
/**
 * @author yanfengzhang
 * @description 我们可以用 2x1 的小矩形横着或者竖着去覆盖更大的矩形。
 * 请问用 n 个 2x1 的小矩形无重叠地覆盖一个 2xn 的大矩形，总共有多少种方法？
 * @date 2023/6/8  23:44
 */
public class CoverJZ {
    /**
     * 设覆盖 2xn 大矩形的方法数为 f(n)。我们考虑最后一步，可以使用一个 2x1 的小矩形横着放在最后一列，也可以使用两个 2x1 的小矩形竖着放在最后一列。
     * •	如果最后一列使用一个横着放置的小矩形，那么前面的方法数为 f(n-1)。
     * •	如果最后一列使用两个竖着放置的小矩形，那么前面的方法数为 f(n-2)。
     * 因此，覆盖 2xn 大矩形的方法数为 f(n) = f(n-1) + f(n-2)。初始条件为 f(1) = 1，f(2) = 2。
     * 
     * 具体步骤如下：
     * 1.	定义一个数组 dp，dp[i] 表示覆盖 2xi 大矩形的方法数。
     * 2.	初始化 dp[1] = 1，dp[2] = 2。
     * 3.	从 i = 3 开始遍历到 n，根据状态转移方程 dp[i] = dp[i-1] + dp[i-2] 计算 dp[i] 的值。
     * 4.	返回 dp[n]，即覆盖 2xn 大矩形的方法数。
     */
    public int rectCover(int n) {
        if (n <= 2) {
            return n;
        }
 
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
 
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
 
        return dp[n];
    }
 
    public static void main(String[] args) {
        CoverJZ solution = new CoverJZ();
        int n = 5;
        // 输出结果为 8
        System.out.println(solution.rectCover(n));
    }
}

76.JZ78-把二叉树打印出多行-(知识点：树,难度：中等)

题目描述：请实现一个函数按照层次打印二叉树，即从根节点开始，逐层从左往右打印节点值。

解题分析

这是一个典型的二叉树层次遍历问题，可以使用队列辅助实现。

首先将根节点入队。
当队列不为空时，循环执行以下操作：• 弹出队列的首个节点，并打印该节点的值。• 将该节点的左右子节点（如果存在）依次入队。
重复步骤2，直到队列为空。

通过这种方式，可以按照层次打印二叉树的节点值。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import org.zyf.javabasic.letcode.tree.base.TreeNode;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
/**
 * @author yanfengzhang
 * @description 请实现一个函数按照层次打印二叉树，即从根节点开始，逐层从左往右打印节点值。
 * @date 2023/6/8  23:46
 */
public class PrintTree {
    /**
     * 这是一个典型的二叉树层次遍历问题，可以使用队列辅助实现。
     * 1.	首先将根节点入队。
     * 2.	当队列不为空时，循环执行以下操作：
     * •	弹出队列的首个节点，并打印该节点的值。
     * •	将该节点的左右子节点（如果存在）依次入队。
     * 3.	重复步骤2，直到队列为空。
     * 
     * 通过这种方式，可以按照层次打印二叉树的节点值。
     */
    public ArrayList> printTree(TreeNode root) {
        ArrayList> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
 
        Queue queue = new LinkedList<>();
        queue.offer(root);
 
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList level = new ArrayList<>();
 
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
 
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
 
            result.add(level);
        }
 
        return result;
    }
 
    public static void main(String[] args) {
        PrintTree solution = new PrintTree();
 
        // 构建二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
 
        ArrayList> result = solution.printTree(root);
        System.out.println(result);
    }
 
}

77.JZ77-按之字形顺序打印二叉树-(知识点：树,难度：中等)

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

解题分析

该问题可以通过层次遍历二叉树并使用双端队列来实现。具体步骤如下：

创建一个结果列表 result 来存储最终的打印结果。
若二叉树根节点为空，直接返回结果列表 result。
创建一个双端队列 deque，用于层次遍历二叉树。
将根节点加入 deque。
创建一个布尔变量 leftToRight，初始值为 true，表示当前层的打印顺序从左到右。
进入循环，直到 deque 为空。• 获取当前层的节点个数 size。• 创建一个列表 level，用于存储当前层的节点值。• 遍历当前层的节点：• 若 leftToRight 为 true，从队列的头部弹出节点，并将其值加入 level。• 若 leftToRight 为 false，从队列的尾部弹出节点，并将其值加入 level。• 若节点有左子节点，则将左子节点加入队列的尾部。• 若节点有右子节点，则将右子节点加入队列的尾部。• 将 level 加入结果列表 result。• 反转 leftToRight 的值，以改变下一层的打印顺序。
返回结果列表 result。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import org.zyf.javabasic.letcode.tree.base.TreeNode;
 
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
 
/**
 * @author yanfengzhang
 * @description 请实现一个函数按照之字形顺序打印二叉树，
 * 即第一行按照从左到右的顺序打印，
 * 第二行按照从右到左的顺序打印，
 * 第三行再按照从左到右的顺序打印，以此类推。
 * @date 2023/6/8  00:49
 */
public class PrintTreeForZ {
    /**
     * 该问题可以通过层次遍历二叉树并使用双端队列来实现。
     * 具体步骤如下：
     * 1.	创建一个结果列表 result 来存储最终的打印结果。
     * 2.	若二叉树根节点为空，直接返回结果列表 result。
     * 3.	创建一个双端队列 deque，用于层次遍历二叉树。
     * 4.	将根节点加入 deque。
     * 5.	创建一个布尔变量 leftToRight，初始值为 true，表示当前层的打印顺序从左到右。
     * 6.	进入循环，直到 deque 为空。
     * •	获取当前层的节点个数 size。
     * •	创建一个列表 level，用于存储当前层的节点值。
     * •	遍历当前层的节点：
     * •	若 leftToRight 为 true，从队列的头部弹出节点，并将其值加入 level。
     * •	若 leftToRight 为 false，从队列的尾部弹出节点，并将其值加入 level。
     * •	若节点有左子节点，则将左子节点加入队列的尾部。
     * •	若节点有右子节点，则将右子节点加入队列的尾部。
     * •	将 level 加入结果列表 result。
     * •	反转 leftToRight 的值，以改变下一层的打印顺序。
     * 7.	返回结果列表 result。
     */
    public ArrayList> printTree(TreeNode root) {
        ArrayList> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
 
        Deque deque = new LinkedList<>();
        deque.offer(root);
        boolean leftToRight = true;
 
        while (!deque.isEmpty()) {
            int size = deque.size();
            ArrayList level = new ArrayList<>();
 
            for (int i = 0; i < size; i++) {
                TreeNode node;
                if (leftToRight) {
                    node = deque.pollFirst();
                } else {
                    node = deque.pollLast();
                }
                level.add(node.val);
 
                if (leftToRight) {
                    if (node.left != null) {
                        deque.offerLast(node.left);
                    }
                    if (node.right != null) {
                        deque.offerLast(node.right);
                    }
                } else {
                    if (node.right != null) {
                        deque.offerFirst(node.right);
                    }
                    if (node.left != null) {
                        deque.offerFirst(node.left);
                    }
                }
            }
 
            leftToRight = !leftToRight;
            result.add(level);
        }
 
        return result;
    }
 
    public static void main(String[] args) {
        PrintTreeForZ solution = new PrintTreeForZ();
 
        // 构建二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
 
        ArrayList> result = solution.printTree(root);
        for (ArrayList level : result) {
            System.out.println(level);
        }
    }
}

78.JZ79-判定是不是平衡二叉树-(知识点：树,难度：简单)

该题目直接可见树相关知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第17题。

79.JZ68-二叉搜索树的最近公共祖先-(知识点：树,难度：简单)

题目描述：给定一个二叉搜索树 (BST)，找到该树中两个指定节点的最近公共祖先（LCA）。一个节点也可以是它自己的祖先。

解题分析

由于二叉搜索树具有左子树节点值小于根节点值，右子树节点值大于根节点值的特点，可以利用这个特点进行求解。

从根节点开始遍历二叉搜索树。
如果当前节点的值大于 p 和 q 的值，说明 p 和 q 分别位于当前节点的左子树中，因此需要向左子树移动。
如果当前节点的值小于 p 和 q 的值，说明 p 和 q 分别位于当前节点的右子树中，因此需要向右子树移动。
如果当前节点的值不满足上述两种情况，则说明当前节点就是最近公共祖先节点。

可以使用迭代或递归的方式实现该算法。以下是使用迭代的解题思路：

初始化当前节点为根节点。
进入循环，直到找到最近公共祖先为止。
如果当前节点的值大于 p 和 q 的值，则将当前节点移动到左子节点。
如果当前节点的值小于 p 和 q 的值，则将当前节点移动到右子节点。
否则，当前节点即为最近公共祖先，退出循环。
返回最近公共祖先节点。

请注意，题目中假设给定的两个节点一定存在于该二叉搜索树中。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import org.zyf.javabasic.letcode.tree.base.TreeNode;
 
/**
 * @author yanfengzhang
 * @description 给定一个二叉搜索树 (BST)，找到该树中两个指定节点的最近公共祖先（LCA）。
 * 一个节点也可以是它自己的祖先。
 * @date 2023/6/9  22:52
 */
public class CommonAncestor {
    /**
     * 由于二叉搜索树具有左子树节点值小于根节点值，右子树节点值大于根节点值的特点，可以利用这个特点进行求解。
     * 1.	从根节点开始遍历二叉搜索树。
     * 2.	如果当前节点的值大于 p 和 q 的值，说明 p 和 q 分别位于当前节点的左子树中，因此需要向左子树移动。
     * 3.	如果当前节点的值小于 p 和 q 的值，说明 p 和 q 分别位于当前节点的右子树中，因此需要向右子树移动。
     * 4.	如果当前节点的值不满足上述两种情况，则说明当前节点就是最近公共祖先节点。
     * 可以使用迭代或递归的方式实现该算法。
     * 
     * 以下是使用迭代的解题思路：
     * 1.	初始化当前节点为根节点。
     * 2.	进入循环，直到找到最近公共祖先为止。
     * 3.	如果当前节点的值大于 p 和 q 的值，则将当前节点移动到左子节点。
     * 4.	如果当前节点的值小于 p 和 q 的值，则将当前节点移动到右子节点。
     * 5.	否则，当前节点即为最近公共祖先，退出循环。
     * 6.	返回最近公共祖先节点。
     * 请注意，题目中假设给定的两个节点一定存在于该二叉搜索树中。
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 遍历二叉搜索树，寻找最近公共祖先
        while (root != null) {
            // 当前节点的值大于 p 和 q 的值，向左子树移动
            if (root.val > p.val && root.val > q.val) {
                root = root.left;
            }
            // 当前节点的值小于 p 和 q 的值，向右子树移动
            else if (root.val < p.val && root.val < q.val) {
                root = root.right;
            }
            // 当前节点的值不满足上述两种情况，即为最近公共祖先节点
            else {
                break;
            }
        }
 
        return root;
    }
 
    public static void main(String[] args) {
        CommonAncestor solution = new CommonAncestor();
 
        // 构建二叉搜索树
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        root.left.right.left = new TreeNode(3);
        root.left.right.right = new TreeNode(5);
 
        // 节点2
        TreeNode p = root.left;
        // 节点8
        TreeNode q = root.right;
 
        TreeNode ancestor = solution.lowestCommonAncestor(root, p, q);
        // 打印最近公共祖先节点的值
        System.out.println(ancestor.val);
    }
 
}

80.JZ86-在二叉树中找到两个节点的最近公共祖先-(知识点：树,难度：中等)

该题目直接可见树相关知识及编程练习总结_张彦峰ZYF的博客-CSDN博客中的第5题。

81.JZ54-二叉搜索树的第K个节点-(知识点：树,难度：中等)

题目描述：给定一棵二叉搜索树，请找出其中第k大的节点。

解题分析

二叉搜索树的特点是，左子树上的节点值都小于根节点值，右子树上的节点值都大于根节点值。因此，中序遍历二叉搜索树可以得到一个递增的节点值序列。

根据这个特点，可以使用中序遍历的思想来解决该问题。具体步骤如下：

对二叉搜索树进行中序遍历，即先遍历左子树，再访问根节点，最后遍历右子树。
在中序遍历的过程中，使用一个计数器记录当前遍历到的节点的序号，当计数器等于k时，表示找到了第k大的节点。
在遍历过程中，如果找到了第k大的节点，则直接返回该节点的值。

具体代码展示验证


package org.zyf.javabasic.letcode.jzoffer;
 
import org.zyf.javabasic.letcode.tree.base.TreeNode;
 
/**
 * @author yanfengzhang
 * @description 给定一棵二叉搜索树，请找出其中第k大的节点。
 * @date 2023/6/9  22:58
 */
public class kthLargestTree {
    // 计数器，记录当前遍历到的节点序号
    private int count = 0;
    // 存储第k大的节点的值
    private int result = 0;
 
    /**
     * 二叉搜索树的特点是，左子树上的节点值都小于根节点值，右子树上的节点值都大于根节点值。因此，中序遍历二叉搜索树可以得到一个递增的节点值序列。
     * 根据这个特点，可以使用中序遍历的思想来解决该问题。具体步骤如下：
     * 1.	对二叉搜索树进行中序遍历，即先遍历左子树，再访问根节点，最后遍历右子树。
     * 2.	在中序遍历的过程中，使用一个计数器记录当前遍历到的节点的序号，当计数器等于k时，表示找到了第k大的节点。
     * 3.	在遍历过程中，如果找到了第k大的节点，则直接返回该节点的值。
     */
    public int kthLargest(TreeNode root, int k) {
        // 从右子树开始进行中序遍历，即先遍历右子树，再访问根节点，最后遍历左子树
        inorderTraversal(root, k);
        return result;
    }
 
    private void inorderTraversal(TreeNode root, int k) {
        if (root == null) {
            return;
        }
 
        // 遍历右子树
        inorderTraversal(root.right, k);
 
        // 计数器加1
        count++;
        // 如果计数器等于k，表示找到了第k大的节点
        if (count == k) {
            result = root.val;
            return;
        }
 
        // 遍历左子树
        inorderTraversal(root.left, k);
    }
 
    public static void main(String[] args) {
        kthLargestTree solution = new kthLargestTree();
 
        // 构建二叉搜索树
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.left.left.left = new TreeNode(1);
 
        int k = 3;
 
        int kthLargest = solution.kthLargest(root, k);
        System.out.println(kthLargest);
    }
}

82.JZx-中文数字表达转实际数字格式-(知识点：哈希,难度：中等)

题目描述：如果输入是一个中文的数字表达，如何高效的返回其对应的实际数字格式表达？

比方说输入是“五十万零五百”，输出"500500"

解题分析

对于中文数字转阿拉伯数字的问题，可以使用递归的思路来解决。具体实现步骤如下：

定义一个字典，将中文数字和阿拉伯数字一一对应起来。
定义一个递归函数 chinese_to_arabic，该函数接受一个中文数字字符串作为参数，并返回对应的阿拉伯数字。
在 chinese_to_arabic 函数中，首先判断输入的字符串是否为空，如果为空则返回 0。
如果字符串不为空，则取出第一个字符，判断其是否为“零”，如果是则递归调用 chinese_to_arabic 函数处理剩余的字符串。
如果第一个字符不是“零”，则判断其是否为单位字符（亿、万、千、百、十），如果是，则递归调用 chinese_to_arabic 函数处理前面的字符串，并将结果乘以对应的单位值。
如果第一个字符既不是“零”，也不是单位字符，则将其转换为对应的阿拉伯数字，并递归调用 chinese_to_arabic 函数处理剩余的字符串。
将递归得到的结果累加起来，并返回最终结果。

具体代码展示


package org.zyf.javabasic.letcode.jzoffer;
 
import java.util.HashMap;
 
/**
 * 如果输入是一个中文的数字表达，如何高效的返回其对应的实际数字格式表达？
 * 比方说输入是“五十万零五百”，输出"500500"
 */
public class ChineseNumberConverter {
    // 定义中文数字和阿拉伯数字的对应关系
    private static final HashMap chineseNum = new HashMap<>();
    private static final HashMap unit = new HashMap<>();
 
    static {
        chineseNum.put('零', 0);
        chineseNum.put('一', 1);
        chineseNum.put('二', 2);
        chineseNum.put('三', 3);
        chineseNum.put('四', 4);
        chineseNum.put('五', 5);
        chineseNum.put('六', 6);
        chineseNum.put('七', 7);
        chineseNum.put('八', 8);
        chineseNum.put('九', 9);
 
        unit.put('亿', 100000000);
        unit.put('万', 10000);
        unit.put('千', 1000);
        unit.put('百', 100);
        unit.put('十', 10);
    }
 
    public static int chineseToArabic(String chineseNumStr) {
        if (chineseNumStr == null || chineseNumStr.isEmpty()) {
            return 0;
        }
 
        // 如果字符串以“零”开头，则递归调用 chineseToArabic 处理剩余的字符串
        if (chineseNumStr.charAt(0) == '零') {
            return chineseToArabic(chineseNumStr.substring(1));
        }
 
        // 如果字符串以单位字符（亿、万、千、百、十）结尾，则递归调用 chineseToArabic 处理前面的字符串，并将结果乘以对应的单位值
        if (unit.containsKey(chineseNumStr.charAt(chineseNumStr.length() - 1))) {
            return chineseToArabic(chineseNumStr.substring(0, chineseNumStr.length() - 1)) * unit.get(chineseNumStr.charAt(chineseNumStr.length() - 1));
        }
 
        // 如果字符串不以“零”或单位字符结尾，则将其转换为对应的阿拉伯数字，并递归调用 chineseToArabic 处理剩余的字符串
        int result = 0;
        for (int i = 0; i < chineseNumStr.length(); i++) {
            char c = chineseNumStr.charAt(i);
            if (chineseNum.containsKey(c)) {
                int num = chineseNum.get(c);
                int unitValue = (int) Math.pow(10, chineseNumStr.length() - i - 1);
                result += num * unitValue;
            }
        }
        return result;
    }
 
    public static void main(String[] args) {
        String chineseNumStr = "五十万零五百";
        int arabicNum = chineseToArabic(chineseNumStr);
        // 输出结果为 500500
        System.out.println(arabicNum);
    }
}

文章知识点与官方知识档案匹配，可进一步学习相关知识

算法技能树首页概览62532 人正在系统学习中

一、剑指offer整体介绍

二、对应题目分析和练习

1.JZ3-数组中重复的数字-(知识点：数组,难度：简单)

2.JZ4-二维数组中的查找-(知识点：数组,难度：中等)

3.JZ11-旋转数组的最小数字-(知识点：二分,难度：简单)

4.JZ17-打印从1到最大的n位数-(知识点：数组,难度：简单)

5.JZ21-调整数组顺序使奇数位于偶数前面(一)-(知识点：数组,难度：简单)

6.JZ81-调整数组顺序使奇数位于偶数前面(二)-(知识点：数组+排序,难度：中等)

7.JZ29-顺时针打印矩阵-(知识点：数组,难度：简单)

8.JZ10-斐波那契数列-(知识点：数组+递归+动态规划+快速幂+记忆化搜索,难度：入门)

9.JZ39-数组中出现次数超过一半的数字-(知识点：哈希,难度：简单)

10.JZ45-把数组排成最小的数-(知识点：数组,难度：中等)

11.JZ47-礼物的最大价值-(知识点：数组+动态规划,难度：中等)

12.JZ53-数字在升序数组中出现的次数-(知识点：数组+二分,难度：简单)

13.JZ49-丑数-(知识点：基础数学+二分,难度：中等)

14.JZ51-数组中的逆序对-(知识点：数组+归并,难度：中等)

15.JZ66-构建乘积数组-(知识点：数组,难度：简单)

16.JZ42-连续子数组的最大和-(知识点：贪心+动态规划,难度：简单)

17.JZ85-a = b + c 的所有可能的组合-(知识点：回溯,难度：中等)

18.JZ56-数组中只出现一次的两个数字-(知识点：哈希+位运算,难度：中等)

19.JZ57-和为S的两个数字-(知识点：数组+双指针,难度：中等)

20.JZ5-替换空格-(知识点：字符串,难度：简单)

21.JZ19-正则表达式匹配-(知识点：字符串,难度：较难)

22.JZ20-表示数值的字符串-(知识点：字符串,难度：较难)

23.JZ38-字符串的排列-(知识点：字符串+递归,难度：中等)

24.JZ48-最长不含重复字符的子字符串-(知识点：字符串,难度：中等)

25.JZ50-第一个只出现一次的字符-(知识点：字符串,难度：简单)

26.JZ58-左旋转字符串-(知识点：字符串,难度：中等)

27.JZ67-把字符串转换成整数-(知识点：字符串,难度：中等)

28.JZ73-翻转单词序列-(知识点：字符串 双指针,难度：简单)

29.JZ74-合为S的连续正数序列-(知识点：穷举,难度：中等)

30.JZ75-字符流中第一个不重复的字符(知识点：字符串,难度：中等)

31.JZ9—用两个栈实现队列(知识点：栈,难度：简单)

32.JZ12-矩阵中的路径-(知识点：DFS,难度：简单)

33.JZ13-机器人的运动范围-(知识点：递归,难度：较难)

34.JZ14-剪绳子-(知识点：基础数学,难度：中等)

35.JZ83-大字符串相加-(基础数学,难度：简单)

36.JZ15-二进制中1的个数-(知识点：基础数学,难度：简单)

37.JZ16-数值的整数次方字-(知识点：基础数学,难度：中等)

38.JZ62-圆圈中最后剩下的数-(知识点：基础数学,难度：中等)

39.JZ63-买卖股票的最好时机-(知识点：贪心+动态规划,难度：简单)

40.JZ64-求1+2+3+···+n数字之和-(知识点：基础数学,难度：中等)

41.JZ65—不用加减乘除做加法(知识点：基础数学,难度：简单)

42.JZ43-从1到n整数中1出现的次数-(知识点：基础数学,难度：中等)

43.JZ6-从尾到头打印链表-(知识点：链表,难度：简单)

44.JZ18-删除链表的节点-(知识点：链表,难度：简单)

45.JZ76-删除链表中的重复结点-(知识点：链表,难度：中等)

46.JZ22-链表中的第k个结点-(知识点：链表,难度：简单)

47.JZ23-链表中环的入口结点-(知识点：链表,难度：中等)

48.JZ24-反转链表-(知识点：链表,难度：简单)

49.JZ25-合并两个排序的链表-(知识点：链表,难度：简单)

50.JZ35-复杂链表的复制-(知识点：链表,难度：较难)

51.JZ52-两个链表的第一个公共的结点-(知识点：链表,难度：简单)

52.JZ26-树的子结构-(知识点：树,难度：中等)

53.JZ27-二叉树的镜像-(知识点：树,难度：简单)

54.JZ28-对称的二叉树-(知识点：树,难度：简单)

55.JZ30—包含main函数的栈(知识点：栈,难度：简单)

56.JZ31-栈的压入弹出序列-(知识点：栈,难度：中等)

57.JZ7-重建二叉树-(知识点：树,难度：中等)

58.JZ8-二叉树的下一个结点-(知识点：树,难度：中等)

59. JZ32-回文串-(知识点：字符串,难度：简单)

60.JZ33-二叉搜索树的后序遍历序列-(知识点：树,难度：中等)

61.JZ82-判断二叉树中是否存在和为某一个值的路径-(知识点：树,难度：简单)

62.JZ34-二叉树中从根结点到叶子结点和为某一个值的所有路径-(知识点：树,难度：中等)

63.JZ84-最大公约数和最小公倍数-(知识点：基础数学,难度：中等)

64.JZ36-二叉搜索树与双向链表-(知识点：分治,难度：中等)

65.JZ37-序列化二叉树-(知识点：树,难度：较难)

66.JZ40-最小的K个数-(知识点：排序,难度：中等)

67.JZ41数据流中的中位数-(知识点：排序,难度：中等)

68.JZ44-数字序列中某一位的数字-(知识点：模拟,难度：简单)

69.JZ46-把数字翻译成字符串-(知识点：动态规划,难度：中等)

70.JZ54-二叉树的深度-(知识点：树,难度：简单)

71.JZ59-滑动窗口的最大值-(知识点：队列,难度：较难)

72.JZ61-扑克牌顺子-(知识点：模拟,难度：简单)

73.JZ69-跳台阶-(知识点：动态规划,难度：简单)

74.JZ71-跳台阶扩展问题-(知识点：动态规划,难度：简单)

75.JZ70-矩阵覆盖-(知识点：动态规划,难度：中等)

76.JZ78-把二叉树打印出多行-(知识点：树,难度：中等)

77.JZ77-按之字形顺序打印二叉树-(知识点：树,难度：中等)

78.JZ79-判定是不是平衡二叉树-(知识点：树,难度：简单)

28.JZ73-翻转单词序列-(知识点：字符串双指针,难度：简单)