LeetCode 面试经典 150 题回顾

指针初始化：初始化三个指针，p1 指向 nums1 的有效元素的最后一个位置（即 m - 1），p2 指向 nums2 的最后一个元素（即 n - 1），p 指向合并后数组的最后一个位置（即 m + n - 1）。
从后向前比较：从数组的末尾开始，比较 nums1[p1] 和 nums2[p2] 的大小，将较大的值放在 nums1[p] 处，然后移动对应的指针；重复上述步骤，直到其中一个数组的所有元素都已被合并。
处理剩余元素：如果 nums2 中还有未合并的元素，需要将它们全部复制到 nums1 的前部。这是因为 nums1 中的前部位置可能已经填满了所有来自 nums1 的元素，剩余位置应由 nums2 的元素填充。

复杂度分析

该算法的时间复杂度为 O(m + n)，因为我们只需遍历两个数组各一次，即可完成合并。空间复杂度为 O(1)，因为合并过程是在 nums1 原地进行的，没有使用额外的空间。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

/**
 * @program: zyfboot-javabasic
 * @description: 合并两个有序数组
 * @author: zhangyanfeng
 * @create: 2024-08-24 19:43
 **/
public class Merge {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 初始化三个指针
        int p1 = m - 1; // 指向nums1的有效元素末尾
        int p2 = n - 1; // 指向nums2的末尾
        int p = m + n - 1; // 指向合并后数组的末尾

        // 从后向前遍历合并
        while (p1 >= 0 && p2 >= 0) {
            // 比较nums1[p1]和nums2[p2]，将较大值放在nums1[p]
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--; // 移动指针p1
            } else {
                nums1[p] = nums2[p2];
                p2--; // 移动指针p2
            }
            p--; // 移动指针p
        }

        // 如果nums2还有剩余元素，则将其复制到nums1前部
        while (p2 >= 0) {
            nums1[p] = nums2[p2];
            p2--;
            p--;
        }
    }

    public static void main(String[] args) {
        Merge solution = new Merge();
        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int m = 3;
        int[] nums2 = {2, 5, 6};
        int n = 3;

        solution.merge(nums1, m, nums2, n);

        // 输出合并后的nums1
        for (int num : nums1) {
            System.out.print(num + " ");
        }
        // 输出结果应为: 1 2 2 3 5 6
    }
}

2.移除元素（简单）

题目描述

解题思路

直接见数组知识及编程练习总结-CSDN博客中第17题。

3.删除有序数组中的重复项（简单）

题目描述

解题思路

这道题要求在原地删除数组中重复出现的元素，使得每个元素只出现一次，且要求返回删除重复元素后数组的新长度。由于 nums 数组已经是按非严格递增排序的，我们可以通过双指针法来解决这个问题。

双指针法:
- 快指针（fast）：用于遍历整个数组。
- 慢指针（slow）：用于记录不重复元素的位置。

具体步骤如下：

初始化 slow 指针指向数组的第一个元素，fast 指针从第二个元素开始遍历数组。
如果 nums[fast] 与 nums[slow] 不相等，说明遇到了新的元素，我们将 slow 向前移动一位，并将 fast 指针指向的值复制到 slow 位置。
不断重复上述过程，直到快指针遍历完整个数组。

最终，慢指针的值加1（即 slow + 1）就是数组中不重复元素的数量，也就是我们需要返回的长度。

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。每个元素最多只被遍历一次。
空间复杂度：O(1)，我们只用了常数级别的额外空间。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

/**
 * @program: zyfboot-javabasic
 * @description: 删除有序数组中的重复项
 * @author: zhangyanfeng
 * @create: 2024-08-24 20:27
 **/
public class RemoveDuplicates {
    public int removeDuplicates(int[] nums) {
        // 如果数组为空，直接返回0
        if (nums.length == 0) {
            return 0;
        }

        // 初始化慢指针
        int slow = 0;

        // 快指针从1开始遍历
        for (int fast = 1; fast < nums.length; fast++) {
            // 如果当前元素和慢指针元素不同
            if (nums[fast] != nums[slow]) {
                // 慢指针前移
                slow++;
                // 将快指针的值赋给慢指针当前位置
                nums[slow] = nums[fast];
            }
        }

        // 返回不重复元素的数量
        return slow + 1;
    }
}

4.删除有序数组中的重复项 II（中等）

题目描述

解题思路

这道题要求我们在有序数组中原地删除重复出现次数超过两次的元素，使每个元素最多保留两次，并返回新的数组长度。

由于数组已经是有序的，我们可以使用双指针法来解决这个问题，类似于之前删除重复元素的题目。但这里的区别在于，我们允许每个元素最多出现两次。

具体步骤如下：

初始化指针：使用 slow 指针来标记不重复元素的位置。使用 fast 指针来遍历数组。
遍历数组：
- 从数组的第三个元素开始（索引 2），因为前两个元素无论如何都要保留。
- 对于每一个 nums[fast]，我们检查它是否大于 nums[slow - 2]。如果是，则说明 nums[fast] 可以保留在数组中（即它出现的次数不会超过两次）。
- 若满足条件，将 nums[fast] 复制到 slow 位置，然后 slow 向前移动。
返回结果：最终，slow 指针的值就是新数组的长度。

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。我们只遍历了一次数组。
空间复杂度：O(1)，我们只用了常数级别的额外空间。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

/**
 * @program: zyfboot-javabasic
 * @description: RemoveDuplicates
 * @author: zhangyanfeng
 * @create: 2024-08-24 20:32
 **/
public class RemoveDuplicates2 {
    public int removeDuplicates(int[] nums) {
        // 如果数组长度小于等于2，则不需要处理，直接返回数组长度
        if (nums.length <= 2) {
            return nums.length;
        }

        // 初始化慢指针指向第二个元素
        int slow = 2;

        // 快指针从第三个元素开始遍历
        for (int fast = 2; fast < nums.length; fast++) {
            // 如果当前元素大于slow-2位置的元素，说明它可以被保留
            if (nums[fast] > nums[slow - 2]) {
                // 将fast指针的值赋给slow指针，并将slow指针向前移动
                nums[slow] = nums[fast];
                slow++;
            }
        }

        // 最终slow的位置就是数组的有效长度
        return slow;
    }
}

5.多数元素（简单）

题目描述

解题思路

可见LeetCode 热题 100 回顾-CSDN博客中第97题。

或数学思维编程练习总结_编程中的数学思维-CSDN博客中第1题。

6.轮转数组（中等）

题目描述

解题思路

可见LeetCode 热题 100 回顾-CSDN博客中第15题。

7.买卖股票的最佳时机（简单）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第77题。

也可见动态规划相关高频笔试汇总_动态规划编程题-CSDN博客中的第18题。

8.买卖股票的最佳时机 II （中等）

题目描述

解题思路

要解决这个问题，我们可以利用贪心算法的思想来实现最优解。具体来说，我们只要在价格上升的每一天都买入并卖出股票，这样可以确保获得最大的利润。假设我们在第 i 天买入股票，并在第 i+1 天卖出，如果 prices[i+1] > prices[i]，那么我们就赚取了 prices[i+1] - prices[i] 的利润。

复杂度分析

时间复杂度：O(n)，其中 n 是数组 prices 的长度。我们只需遍历一次数组即可计算出最大利润。
空间复杂度：O(1)，我们只使用了常数级别的额外空间。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

/**
 * @program: zyfboot-javabasic
 * @description: 买卖股票的最佳时机 II
 * @author: zhangyanfeng
 * @create: 2024-08-25 08:54
 **/
public class MaxProfit {
    public int maxProfit(int[] prices) {
        // 初始化最大利润为0
        int maxProfit = 0;

        // 遍历价格数组，从第二天开始计算
        for (int i = 1; i < prices.length; i++) {
            // 如果今天的价格比昨天的高，计算利润
            if (prices[i] > prices[i - 1]) {
                // 累加利润
                maxProfit += prices[i] - prices[i - 1];
            }
        }

        // 返回计算的最大利润
        return maxProfit;
    }

    // 测试用例
    public static void main(String[] args) {
        MaxProfit solution = new MaxProfit();

        // 示例1
        int[] prices1 = {7, 1, 5, 3, 6, 4};
        System.out.println("最大利润: " + solution.maxProfit(prices1));  // 输出应为7

        // 示例2
        int[] prices2 = {1, 2, 3, 4, 5};
        System.out.println("最大利润: " + solution.maxProfit(prices2));  // 输出应为4

        // 示例3
        int[] prices3 = {7, 6, 4, 3, 1};
        System.out.println("最大利润: " + solution.maxProfit(prices3));  // 输出应为0
    }
}

9.跳跃游戏（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第78题。

10.跳跃游戏 II（中等）

题目描述

具体可见LeetCode 热题 100 回顾-CSDN博客中的第79题。

11.H 指数（中等）

题目描述

解题思路

要计算研究者的 h 指数，我们可以利用排序和线性扫描来解决。h 指数的定义是某位研究者发表的论文中有至少 h 篇论文被引用了至少 h 次。如果 h 有多种可能值，则选择最大的那个 h。解决思路：

排序：首先将论文的引用次数数组 citations 按照引用次数从大到小进行排序。
线性扫描：扫描排序后的数组，并找到最大的 h，使得至少有 h 篇论文的引用次数大于等于 h。

复杂度分析

时间复杂度：排序的时间复杂度为 O(n log n)，其中 n 是数组 citations 的长度。线性扫描的时间复杂度为 O(n)，因此整体时间复杂度为 O(n log n)。
空间复杂度：我们只需要常数级别的额外空间，因此空间复杂度为 O(1)。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

import java.util.Arrays;

/**
 * @program: zyfboot-javabasic
 * @description: H 指数
 * @author: zhangyanfeng
 * @create: 2024-08-25 09:13
 **/
public class HIndex {
    public int hIndex(int[] citations) {
        // 对数组进行从大到小的排序
        Arrays.sort(citations);

        int n = citations.length;

        // 线性扫描排序后的数组，寻找最大的 h
        for (int i = 0; i < n; i++) {
            int h = n - i;
            // 如果 citations[i] >= h，说明至少有 h 篇论文被引用了至少 h 次
            if (citations[i] >= h) {
                return h;
            }
        }

        // 如果未找到合适的 h，返回 0
        return 0;
    }

    // 测试用例
    public static void main(String[] args) {
        HIndex solution = new HIndex();

        // 示例1
        int[] citations1 = {3, 0, 6, 1, 5};
        System.out.println("h指数: " + solution.hIndex(citations1));  // 输出应为3

        // 示例2
        int[] citations2 = {1, 3, 1};
        System.out.println("h指数: " + solution.hIndex(citations2));  // 输出应为1
    }

}

12.O(1) 时间插入、删除和获取随机元素（中等）

题目描述

解题思路

要实现 RandomizedSet 类，我们需要支持插入、删除和随机获取元素的操作，并且所有操作的平均时间复杂度要求为 O(1)。为此，我们可以利用以下两种数据结构：

哈希表（HashMap）：用于存储每个元素的值和它在数组中的索引位置。这样可以在 O(1) 时间内查找元素是否存在并删除元素。
动态数组（ArrayList）：用于保存当前集合中的所有元素。我们可以通过索引随机获取元素，并且在删除操作时，可以通过交换元素来保持 O(1) 时间的删除操作。

解决思路：

插入操作：如果元素不存在于集合中，将其添加到数组的末尾，并将该元素及其对应的索引位置存入哈希表中。如果元素已经存在，则直接返回 false。
删除操作：如果元素存在于集合中，将其与数组的最后一个元素交换位置，然后移除最后一个元素。同时更新哈希表中被交换的元素的位置，并移除待删除元素的哈希表记录。如果元素不存在，则直接返回 false。
随机获取元素：直接从数组中随机选择一个索引并返回该索引对应的元素。

复杂度分析

插入操作：平均时间复杂度为 O(1)，因为哈希表的插入和查找操作都是 O(1)。
删除操作：平均时间复杂度为 O(1)，因为通过交换最后一个元素可以保持删除的 O(1) 操作。
随机获取元素：时间复杂度为 O(1)，因为从数组中随机选择一个元素是 O(1) 操作。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

import java.util.*;

/**
 * @program: zyfboot-javabasic
 * @description: O(1) 时间插入、删除和获取随机元素
 * @author: zhangyanfeng
 * @create: 2024-08-25 09:18
 **/
public class RandomizedSet {
    // 动态数组用于存储集合中的元素
    private List<Integer> nums;
    // 哈希表用于存储每个元素对应在动态数组中的索引
    private Map<Integer, Integer> valToIndex;
    private Random rand;

    // 构造函数，初始化动态数组和哈希表
    public RandomizedSet() {
        nums = new ArrayList<>();
        valToIndex = new HashMap<>();
        rand = new Random();
    }

    // 插入操作
    public boolean insert(int val) {
        // 如果元素已存在，返回false
        if (valToIndex.containsKey(val)) {
            return false;
        }
        // 在数组末尾添加新元素，并在哈希表中记录其索引
        nums.add(val);
        valToIndex.put(val, nums.size() - 1);
        return true;
    }

    // 删除操作
    public boolean remove(int val) {
        // 如果元素不存在，返回false
        if (!valToIndex.containsKey(val)) {
            return false;
        }
        // 获取待删除元素的索引
        int index = valToIndex.get(val);
        // 将待删除元素与数组的最后一个元素交换位置
        int lastElement = nums.get(nums.size() - 1);
        nums.set(index, lastElement);
        valToIndex.put(lastElement, index);
        // 删除数组的最后一个元素，并移除哈希表中的记录
        nums.remove(nums.size() - 1);
        valToIndex.remove(val);
        return true;
    }

    // 随机获取元素操作
    public int getRandom() {
        // 从数组中随机选择一个元素并返回
        return nums.get(rand.nextInt(nums.size()));
    }

    // 测试用例
    public static void main(String[] args) {
        RandomizedSet randomizedSet = new RandomizedSet();

        System.out.println(randomizedSet.insert(1)); // true
        System.out.println(randomizedSet.remove(2)); // false
        System.out.println(randomizedSet.insert(2)); // true
        System.out.println(randomizedSet.getRandom()); // 1 or 2
        System.out.println(randomizedSet.remove(1)); // true
        System.out.println(randomizedSet.insert(2)); // false
        System.out.println(randomizedSet.getRandom()); // 2
    }
}

13.除自身以外数组的乘积（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第16题。

也可见LeetCode 精选 75 回顾-CSDN博客中的第7题。

也可见数组知识及编程练习总结-CSDN博客中的第19题。

14.加油站（中等）

题目描述

解题思路

目标是找到一个出发的加油站，使得从这个加油站出发后，能够顺利绕环路一圈，最终回到这个加油站。如果无法做到，返回 -1。关键点：

如果 gas[i] - cost[i] 的总和小于 0，则无论从哪个加油站出发，汽车都不可能完成一圈，因为汽油总量不够。
如果某个加油站作为起点能够顺利完成一圈，那么从这个加油站之前的任何一个加油站出发都不能完成一圈，因为它们的剩余油量在到达这个加油站之前已经不足了。

解题思路：

遍历两次：一次遍历计算总油量和总消耗量。如果总油量小于总消耗量，则返回 -1。
选择起点：从第一个加油站开始，逐个加油站计算从该站出发后的剩余油量。如果在某个加油站剩余油量为负，则将起点移动到下一个加油站，并重新计算剩余油量。

复杂度分析

时间复杂度：O(n)，只需要遍历数组一次即可完成计算。
空间复杂度：O(1)，仅使用了常数级别的额外空间。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

/**
 * @program: zyfboot-javabasic
 * @description: 加油站
 * @author: zhangyanfeng
 * @create: 2024-08-25 09:44
 **/
public class CanCompleteCircuit {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;  // 总油量
        int totalCost = 0; // 总消耗
        int start = 0;     // 起点
        int tank = 0;      // 当前油箱剩余油量

        // 遍历所有加油站
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            tank += gas[i] - cost[i];

            // 如果当前油量不足以到达下一个加油站
            if (tank < 0) {
                // 将起点设为下一个加油站
                start = i + 1;
                // 重置油箱
                tank = 0;
            }
        }

        // 判断是否可以绕环一圈
        return totalGas >= totalCost ? start : -1;
    }

    public static void main(String[] args) {
        CanCompleteCircuit solution = new CanCompleteCircuit();

        // 测试用例 1
        int[] gas1 = {1, 2, 3, 4, 5};
        int[] cost1 = {3, 4, 5, 1, 2};
        System.out.println(solution.canCompleteCircuit(gas1, cost1)); // 输出: 3

        // 测试用例 2
        int[] gas2 = {2, 3, 4};
        int[] cost2 = {3, 4, 3};
        System.out.println(solution.canCompleteCircuit(gas2, cost2)); // 输出: -1
    }
}

15.发糖果（困难）

题目描述

解题思路

理解这道题的关键在于如何满足所有孩子的评分条件，同时尽量减少分配的糖果数量。

双向扫描法:

左到右扫描: 首先从左到右遍历数组。我们可以假设如果一个孩子的评分高于前一个孩子，那么这个孩子应该比前一个孩子多获得一颗糖果。这样我们可以确保在从左到右的方向上，所有评分更高的孩子都比左边的孩子获得更多糖果。
右到左扫描: 然后从右到左遍历数组。这个步骤与前一步类似，但我们需要确保对于右侧的孩子，如果评分高于左边的孩子，糖果数量也要比左边的多。这个步骤是为了修正左到右扫描时可能未考虑到的情况。

糖果数量的确定:对于每个孩子，最终分配的糖果数量是两次扫描中各自确定的糖果数量的最大值。即，如果在左到右扫描时确定的糖果数量为 left[i]，在右到左扫描时确定的糖果数量为 right[i]，那么最终该孩子获得的糖果数量为 max(left[i], right[i])。

最终结果:将所有孩子的糖果数量累加，得到最少需要的糖果数。

复杂度分析

时间复杂度: O(n)，我们对数组进行了两次扫描。
空间复杂度: O(n)，我们使用了两个额外的数组来保存每个孩子从左到右和从右到左扫描时的糖果数量。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

import java.util.Arrays;

/**
 * @program: zyfboot-javabasic
 * @description: 分发糖果
 * @author: zhangyanfeng
 * @create: 2024-08-25 09:51
 **/
public class Candy {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];

        // 每个孩子至少给一颗糖果
        Arrays.fill(candies, 1);

        // 从左到右遍历，确保评分更高的孩子获得更多的糖果
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // 从右到左遍历，确保评分更高的孩子获得更多的糖果
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        // 计算糖果总数
        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }

        return totalCandies;
    }
}

16.接雨水（困难）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第7题。

也可见栈知识及编程练习总结-CSDN博客中的第6题。

17.罗马数字转整数（简单）

题目描述

解题思路

可见数学思维编程练习总结_编程中的数学思维-CSDN博客中的第10题。

18.整数转罗马数字（中等）

题目描述

解题思路

要将一个整数转换为罗马数字，我们需要按照罗马数字的规则逐步构建字符串。罗马数字是通过添加或减去特定的符号来表示不同的值，步骤：

准备罗马数字符号及其对应的值:建立两个数组，一个存储罗马数字的符号，另一个存储这些符号对应的整数值。数组按从大到小的顺序排列。
逐步匹配:
遍历这些值，检查当前数字 num 是否大于或等于当前的值。如果是，则减去该值，并将对应的罗马符号添加到结果字符串中。如果 num 以 4 或 9 为开头，直接匹配减法形式的罗马符号。
终止条件:当 num 减为 0 时，所有的罗马符号都已经添加完毕。

复杂度分析

时间复杂度: O(1)。虽然我们在遍历不同的罗马符号，但是由于罗马数字有固定的符号个数和最大数值，所以整体的操作次数是有限的。因此时间复杂度为常数级别。
空间复杂度: O(1)。使用了少量的额外空间来存储符号和结果字符串，因此空间复杂度也为常数级别。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

/**
 * @program: zyfboot-javabasic
 * @description: 整数转罗马数字
 * @author: zhangyanfeng
 * @create: 2024-08-25 10:05
 **/
public class IntegerToRoman {
    public String intToRoman(int num) {
        // 罗马数字符号和对应的值
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder roman = new StringBuilder();

        // 遍历所有符号值
        for (int i = 0; i < values.length; i++) {
            // 每次找到最大值，减少num
            while (num >= values[i]) {
                num -= values[i];
                roman.append(symbols[i]); // 添加符号到结果
            }
        }

        return roman.toString();
    }

    public static void main(String[] args) {
        IntegerToRoman converter = new IntegerToRoman();

        // 测试用例
        System.out.println(converter.intToRoman(3749)); // 输出: MMMDCCXLIX
        System.out.println(converter.intToRoman(58));   // 输出: LVIII
        System.out.println(converter.intToRoman(1994)); // 输出: MCMXCIV
    }
}

19.最后一个单词的长度（简单）

题目描述

解题思路

要计算字符串中最后一个单词的长度，可以从字符串末尾开始扫描，找到最后一个单词并计算其长度。考虑到字符串中可能包含前导或尾随空格，我们需要跳过这些空格来定位最后一个单词。

从后向前遍历:
从字符串的末尾开始，跳过所有的尾随空格。一旦找到一个非空格字符，开始计数，直到遇到下一个空格或到达字符串的开头。计数器的值就是最后一个单词的长度。
终止条件:遍历到字符串的开始处时，结束循环。

复杂度分析

时间复杂度: O(n)，其中 n 是字符串的长度。我们只需从字符串末尾向前遍历一次。
空间复杂度: O(1)，只使用了常数级的额外空间。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

/**
 * @program: zyfboot-javabasic
 * @description: 最后一个单词的长度
 * @author: zhangyanfeng
 * @create: 2024-08-25 10:09
 **/
public class LastWordLength {
    public int lengthOfLastWord(String s) {
        int length = 0;
        int index = s.length() - 1;

        // 从后向前跳过空格
        while (index >= 0 && s.charAt(index) == ' ') {
            index--;
        }

        // 计算最后一个单词的长度
        while (index >= 0 && s.charAt(index) != ' ') {
            length++;
            index--;
        }

        return length;
    }

    public static void main(String[] args) {
        LastWordLength solution = new LastWordLength();

        // 测试用例
        System.out.println(solution.lengthOfLastWord("Hello World"));         // 输出: 5
        System.out.println(solution.lengthOfLastWord(" fly me to the moon ")); // 输出: 4
        System.out.println(solution.lengthOfLastWord("luffy is still joyboy")); // 输出: 6
    }
}

20.最长公共前缀（简单）

题目描述

解题思路

要查找字符串数组中的最长公共前缀，可以使用常用且直观的解法，即 纵向扫描法：

从第一个字符开始，依次检查每个字符串在相同位置的字符是否相同。
如果在某个位置的字符不匹配，或者到达了某个字符串的末尾，就停止比较，并返回当前找到的最长公共前缀。
如果全部字符都匹配，则继续检查下一列字符。

复杂度分析

时间复杂度: O(S)，其中 S 是所有字符串中字符数量的总和。在最坏情况下，需要检查每个字符。
空间复杂度: O(1)，只使用了常数级的额外空间。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

/**
 * @program: zyfboot-javabasic
 * @description: 最长公共前缀
 * @author: zhangyanfeng
 * @create: 2024-08-25 10:15
 **/
public class LongestCommonPrefix {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 从第一个字符串的第一个字符开始比较
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                // 如果在当前位置字符不匹配或已到达其他字符串的末尾
                if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }

        // 如果第一个字符串本身是最长公共前缀
        return strs[0];
    }

    public static void main(String[] args) {
        LongestCommonPrefix solution = new LongestCommonPrefix();

        // 测试用例
        System.out.println(solution.longestCommonPrefix(new String[]{"flower", "flow", "flight"})); // 输出: "fl"
        System.out.println(solution.longestCommonPrefix(new String[]{"dog", "racecar", "car"}));    // 输出: ""
    }
}

21.反转字符串中的单词（中等）

题目描述

解题思路

具体可见LeetCode 精选 75 回顾-CSDN博客中的第6题。

类似反转还有字符串高频编程笔试汇总_字符串专题复习-CSDN博客中的第22题。

22.Z 字形变换（中等）

题目描述

解题思路

具体可见字符串高频编程笔试汇总_字符串专题复习-CSDN博客中的第23题。

23.找出字符串中第一个匹配项的下标（简单）

题目描述

解题思路

这个问题可以通过字符串匹配算法来解决。最直接的方法是使用暴力匹配法，从 haystack 的每个字符开始，逐一匹配 needle，直到找到匹配项或遍历完 haystack。暴力匹配法：

从 haystack 的第一个字符开始，检查 needle 是否与 haystack 从当前字符开始的子串匹配。
如果匹配成功，则返回匹配的起始索引。
如果遍历完 haystack 仍未找到匹配项，则返回 -1。

复杂度分析

时间复杂度：O((N-M+1) * M)，其中 N 是 haystack 的长度，M 是 needle 的长度。最坏情况下，需要对每个位置都进行 M 次比较。
空间复杂度：O(1)，只需要常数级的额外空间。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

/**
 * @program: zyfboot-javabasic
 * @description: 找出字符串中第一个匹配项的下标
 * @author: zhangyanfeng
 * @create: 2024-08-25 10:27
 **/
public class StrIndex {
    public int strStr(String haystack, String needle) {
        // 获取 haystack 和 needle 的长度
        int n = haystack.length();
        int m = needle.length();

        // 遍历 haystack 的每个位置，尝试匹配 needle
        for (int i = 0; i <= n - m; i++) {
            // 取出 haystack 中的子串
            String substring = haystack.substring(i, i + m);

            // 检查子串是否与 needle 相等
            if (substring.equals(needle)) {
                return i; // 如果匹配，返回起始位置
            }
        }

        // 如果没有找到匹配，返回 -1
        return -1;
    }
}

24.文本左右对齐（困难）

题目描述

解题思路

贪心分配单词：从单词数组中逐个取出单词，并将它们放置在当前行中，直到当前行无法再放置更多单词（即放置当前单词后总长度超过 maxWidth）。

计算行内空格：
一旦确定了当前行应包含的所有单词，我们需要计算如何在这些单词之间分配空格。对于每行文本，除最后一行外，其它行都需要左右对齐。计算行中单词之间的空格数。平均分配空格，如果有多余的空格，优先分配到靠左的空隙中。
格式化每行：将计算得到的空格插入到单词之间，形成需要的格式。对于最后一行，单词左对齐，剩余的空格填充在行尾。

复杂度分析

时间复杂度：O(n)，其中 n 是单词数组 words 的长度。每个单词只被处理一次，因此整体时间复杂度是线性的。
空间复杂度：O(n)，用于存储结果和处理每行的单词列表。

代码实现

package org.zyf.javabasic.letcode.jd150.stringarray;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: zyfboot-javabasic
 * @description: 文本左右对齐
 * @author: zhangyanfeng
 * @create: 2024-08-25 10:31
 **/
public class FullJustify {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        List<String> currentLine = new ArrayList<>();
        int numOfLetters = 0;

        for (String word : words) {
            // 如果当前行可以容纳这个单词
            if (numOfLetters + word.length() + currentLine.size() <= maxWidth) {
                currentLine.add(word);
                numOfLetters += word.length();
            } else {
                // 如果当前行满了，处理当前行的文本
                result.add(justifyLine(currentLine, numOfLetters, maxWidth, false));
                currentLine = new ArrayList<>();
                currentLine.add(word);
                numOfLetters = word.length();
            }
        }

        // 处理最后一行，左对齐
        result.add(justifyLine(currentLine, numOfLetters, maxWidth, true));

        return result;
    }

    private String justifyLine(List<String> words, int numOfLetters, int maxWidth, boolean isLastLine) {
        // 如果是最后一行或只有一个单词，左对齐
        if (isLastLine || words.size() == 1) {
            StringBuilder sb = new StringBuilder();
            for (String word : words) {
                sb.append(word).append(" ");
            }
            sb.deleteCharAt(sb.length() - 1); // 删除最后一个空格
            while (sb.length() < maxWidth) {
                sb.append(" ");
            }
            return sb.toString();
        }

        // 计算每个空格的数量
        int totalSpaces = maxWidth - numOfLetters;
        int spacesBetweenWords = totalSpaces / (words.size() - 1);
        int extraSpaces = totalSpaces % (words.size() - 1);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words.size(); i++) {
            sb.append(words.get(i));
            if (i < words.size() - 1) {
                // 每个空格的基础数量
                for (int j = 0; j < spacesBetweenWords; j++) {
                    sb.append(" ");
                }
                // 分配多余的空格
                if (extraSpaces > 0) {
                    sb.append(" ");
                    extraSpaces--;
                }
            }
        }
        return sb.toString();
    }
}

二、双指针

25.验证回文串（简单）

题目描述

解题思路

可见字符串高频编程笔试汇总_字符串专题复习-CSDN博客中第6题。

26.判断子序列（简单）

题目描述

解题思路

可见LeetCode 精选 75 回顾-CSDN博客中的第11题。

27.两数之和 II - 输入有序数组（中等）

题目描述

解题思路

如果是无序数组的话，可见数组知识及编程练习总结-CSDN博客中的第1题。

由于数组 numbers 是按非递减顺序排列的，我们可以利用这一点来设计一个高效的解法。具体来说，我们可以使用“双指针”方法来找到满足条件的两个数。这种方法的优势在于其时间复杂度为 O(n)，同时只使用常量级的额外空间。双指针法的步骤

初始化指针：使用两个指针 left 和 right。left 指针从数组的起始位置开始，right 指针从数组的末尾位置开始。
遍历数组：
- 计算 numbers[left] 和 numbers[right] 的和。
- 如果和等于目标值 target，返回这两个指针的位置（加 1，因为题目要求返回的是从 1 开始的下标）。
- 如果和小于 target，说明我们需要更大的数，因此将 left 指针向右移动一步。
- 如果和大于 target，说明我们需要更小的数，因此将 right 指针向左移动一步。
终止条件：当 left 指针不再小于 right 指针时，算法结束。

这种方法利用了数组的有序性，使得每一步都可以排除掉一些不必要的元素，从而保证了时间复杂度为 O(n)。

复杂度分析

时间复杂度：O(n)，其中 n 是数组 numbers 的长度。每个元素最多只被访问一次，因此整体时间复杂度是线性的。
空间复杂度：O(1)，只使用了常量级的额外空间用于存储指针和变量。

代码实现

package org.zyf.javabasic.letcode.jd150.twopoints;

/**
 * @program: zyfboot-javabasic
 * @description: 两数之和 II - 输入有序数组
 * @author: zhangyanfeng
 * @create: 2024-08-25 10:43
 **/
public class TwoSum {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0; // 左指针
        int right = numbers.length - 1; // 右指针

        // 遍历直到两个指针重合
        while (left < right) {
            int sum = numbers[left] + numbers[right]; // 计算当前指针指向的两个数的和

            if (sum == target) {
                // 如果和等于目标值，返回下标（加 1，因为题目要求从 1 开始）
                return new int[] {left + 1, right + 1};
            } else if (sum < target) {
                // 如果和小于目标值，左指针向右移动
                left++;
            } else {
                // 如果和大于目标值，右指针向左移动
                right--;
            }
        }

        // 如果没有找到符合条件的两个数（题目保证有唯一解，这里只是为了编译器完整性）
        return new int[] {-1, -1};
    }
}

28.盛最多水的容器（中等）

题目描述

解题思路

可见LeetCode 精选 75 回顾-CSDN博客中的第12题。

也可见LeetCode 热题 100 回顾-CSDN博客中的第5题。

29.三数之和（中等）

题目描述

解题思路

可见LeetCode 热题 100 回顾-CSDN博客中的第6题。

也可见数组知识及编程练习总结-CSDN博客中的第2题。

三、滑动窗口

30.长度最小的子数组（中等）

题目描述

解题思路

为了找到满足总和大于等于 target 的最小长度子数组，我们可以使用滑动窗口（双指针）的方法：

初始化变量：left 指针表示当前子数组的起始位置。right 指针表示当前子数组的结束位置。currentSum 用于记录当前子数组的总和。minLength 用于记录找到的最小长度，初始值设为无穷大（Integer.MAX_VALUE）。
扩展窗口：使用 right 指针从头到尾遍历数组，同时将当前元素加入 currentSum。
收缩窗口：每次 currentSum 大于等于 target 时，更新 minLength 并将 left 指针向右移动以尝试缩小窗口，同时更新 currentSum。
终止条件：遍历结束后，如果 minLength 仍为无穷大，说明没有找到符合条件的子数组，返回 0。

这种方法的时间复杂度是 O(n)，因为每个元素最多被访问两次（一次被 right 指针访问，一次被 left 指针访问），空间复杂度是 O(1)。

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。每个元素最多被访问两次，因此整体时间复杂度为线性。
空间复杂度：O(1)，只使用了常量级的额外空间用于存储指针和变量。

代码实现

package org.zyf.javabasic.letcode.jd150.window;

/**
 * @program: zyfboot-javabasic
 * @description: 长度最小的子数组
 * @author: zhangyanfeng
 * @create: 2024-08-25 10:58
 **/
public class MinSubArrayLen {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0; // 左指针
        int currentSum = 0; // 当前子数组的总和
        int minLength = Integer.MAX_VALUE; // 记录最小长度

        // 遍历数组
        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right]; // 扩展窗口

            // 收缩窗口，直到 currentSum 小于 target
            while (currentSum >= target) {
                minLength = Math.min(minLength, right - left + 1); // 更新最小长度
                currentSum -= nums[left++]; // 收缩窗口
            }
        }

        // 如果 minLength 未更新，说明没有找到符合条件的子数组
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

31.无重复字符的最长子串（中等）

题目描述

解题思路

可见LeetCode 热题 100 回顾-CSDN博客中的第8题。

可见字符串高频编程笔试汇总_字符串专题复习-CSDN博客中的第18题。

可见散列表相关知识及编程练习总结_散列函数情景题-CSDN博客中的第1题。

32.串联所有单词的子串（困难）

题目描述

解题思路

给定的解法使用了滑动窗口和哈希表来解决寻找字符串中所有串联子串的起始位置的问题：

初始化和基本参数设置：m 是 words 数组中的单词数量。n 是每个单词的长度。ls 是字符串 s 的长度。遍历字符串 s 中的每一个可能的起始位置（从 i = 0 到 i < n），以保证覆盖所有可能的窗口起始位置。
预处理：
对于每个起始位置 i，检查从 i 开始的长度为 m * n 的子串是否是 words 中所有单词的排列。使用 differ 哈希表记录当前窗口的单词及其计数。初始化时，将子串中的每个单词加入 differ 表中。
滑动窗口处理：
将窗口向右滑动，每次滑动一个单词的长度 n。更新 differ 哈希表，加入新的单词并移除旧的单词。检查 differ 是否为空。如果为空，说明当前窗口中的单词完全匹配了 words 中的单词，记录当前的起始位置。

复杂度分析

时间复杂度：
- 遍历每个可能的起始位置 i。由于窗口滑动的步长是 n，所以 i 的最大范围是 n。
- 对于每个起始位置，滑动窗口遍历的次数是 O(ls / n)，其中 ls 是字符串 s 的长度。
- 更新哈希表操作的时间复杂度为 O(m)，其中 m 是 words 中单词的数量。
- 总的时间复杂度为 O(n * (ls / n) * m) = O(ls * m)。
空间复杂度：
- differ 哈希表的大小最多为 m，因为 differ 记录了 words 中的所有单词及其计数。
- 总的空间复杂度为 O(m)。

代码实现

package org.zyf.javabasic.letcode.jd150.window;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @program: zyfboot-javabasic
 * @description: findSubstring
 * @author: zhangyanfeng
 * @create: 2024-08-25 11:05
 **/
public class FindSubstring {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>(); // 结果列表
        int m = words.length; // 单词数量
        int n = words[0].length(); // 每个单词的长度
        int ls = s.length(); // 字符串 s 的长度

        // 遍历所有可能的起始位置
        for (int i = 0; i < n; i++) {
            if (i + m * n > ls) {
                break; // 如果剩余长度不足以容纳所有单词，则结束
            }

            // 记录当前窗口内的单词及其计数
            Map<String, Integer> differ = new HashMap<String, Integer>();
            for (int j = 0; j < m; j++) {
                String word = s.substring(i + j * n, i + (j + 1) * n); // 当前窗口中的单词
                differ.put(word, differ.getOrDefault(word, 0) + 1); // 计数
            }

            // 从 words 中移除所有单词的计数，准备验证
            for (String word : words) {
                differ.put(word, differ.getOrDefault(word, 0) - 1);
                if (differ.get(word) == 0) {
                    differ.remove(word); // 移除计数为零的单词
                }
            }

            // 滑动窗口
            for (int start = i; start < ls - m * n + 1; start += n) {
                if (start != i) {
                    // 更新窗口：添加新单词，移除旧单词
                    String word = s.substring(start + (m - 1) * n, start + m * n);
                    differ.put(word, differ.getOrDefault(word, 0) + 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                    word = s.substring(start - n, start);
                    differ.put(word, differ.getOrDefault(word, 0) - 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                }

                // 检查是否所有单词都匹配
                if (differ.isEmpty()) {
                    res.add(start); // 记录符合条件的起始位置
                }
            }
        }

        return res; // 返回结果
    }
}

33.最小覆盖子串（困难）

题目描述

解题思路

可见LeetCode 热题 100 回顾-CSDN博客中的第12题。

可见字符串高频编程笔试汇总_字符串专题复习-CSDN博客中的第21题。

可见散列表相关知识及编程练习总结_散列函数情景题-CSDN博客中的第3题。

四、矩阵

34.有效的数独（中等）

题目描述

解题思路

具体可见散列表相关知识及编程练习总结_散列函数情景题-CSDN博客中的第2题。

35.螺旋矩阵（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第19题。

36.旋转图像（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第20题。

37.矩阵置零（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第18题。

38.生命游戏（中等）

题目描述

解题思路

链接：https://leetcode.cn/problems/game-of-life/solutions/179750/sheng-ming-you-xi-by-leetcode-solution/

先根据下面的图片理解题目中描述的细胞遵循的生存定律:

LeetCode 面试经典 150 题回顾-LMLPHP

这个问题看起来很简单，但有一个陷阱，如果你直接根据规则更新原始数组，那么就做不到题目中说的同步更新。假设你直接将更新后的细胞状态填入原始数组，那么当前轮次其他细胞状态的更新就会引用到当前轮已更新细胞的状态，但实际上每一轮更新需要依赖上一轮细胞的状态，是不能用这一轮的细胞状态来更新的。

LeetCode 面试经典 150 题回顾-LMLPHP

如上图所示，已更新细胞的状态会影响到周围其他还未更新细胞状态的计算。一个最简单的解决方法就是复制一份原始数组，复制的那一份永远不修改，只作为更新规则的引用。这样原始数组的细胞值就不会被污染了。

LeetCode 面试经典 150 题回顾-LMLPHP

算法

复制一份原始数组；
根据复制数组中邻居细胞的状态来更新 board 中的细胞状态。

复杂度分析

时间复杂度：O(mn)，其中 m 和 n 分别为 board 的行数和列数。
空间复杂度：O(mn)，为复制数组占用的空间。

代码实现

package org.zyf.javabasic.letcode.jd150.window;

/**
 * @program: zyfboot-javabasic
 * @description: gameOfLife
 * @author: zhangyanfeng
 * @create: 2024-08-25 11:50
 **/
public class GameOfLife {
    public void gameOfLife(int[][] board) {
        // 定义邻居位置的偏移量
        int[] neighbors = {0, 1, -1};

        // 获取网格的行数和列数
        int rows = board.length;
        int cols = board[0].length;

        // 创建与原始网格大小相同的复制网格
        int[][] copyBoard = new int[rows][cols];

        // 将原始网格的状态复制到复制网格中
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                copyBoard[row][col] = board[row][col];
            }
        }

        // 遍历每个细胞，更新网格状态
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                // 统计当前细胞的八个邻居中的活细胞数量
                int liveNeighbors = 0;

                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        // 排除自己
                        if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
                            int r = row + neighbors[i];
                            int c = col + neighbors[j];

                            // 确保邻居在网格范围内并且是活细胞
                            if (r >= 0 && r < rows && c >= 0 && c < cols && copyBoard[r][c] == 1) {
                                liveNeighbors++;
                            }
                        }
                    }
                }

                // 根据活邻居数和当前状态更新细胞状态
                if (copyBoard[row][col] == 1) { // 当前细胞是活的
                    if (liveNeighbors < 2 || liveNeighbors > 3) {
                        board[row][col] = 0; // 死亡
                    }
                } else { // 当前细胞是死的
                    if (liveNeighbors == 3) {
                        board[row][col] = 1; // 复活
                    }
                }
            }
        }
    }
}

五、哈希表

39.赎金信（简单）

题目描述

解题思路

要解决这个问题，我们需要判断 ransomNote 是否可以由 magazine 中的字符构成。每个字符在 magazine 中只能使用一次：

统计字符频率：使用两个频率数组或哈希表来统计 magazine 和 ransomNote 中每个字符的出现次数。
检查字符是否足够：对于 ransomNote 中的每个字符，检查在 magazine 中是否有足够的字符来满足需求。

复杂度分析

时间复杂度：统计 magazine 和 ransomNote 中每个字符的频率都需要 O(n) 时间，其中 n 是字符串的长度。因此总时间复杂度为 O(m + n)，其中 m 是 ransomNote 的长度，n 是 magazine 的长度。
空间复杂度：需要两个频率数组或哈希表来存储字符的出现次数。因为字符集有限（26 个小写字母），空间复杂度为 O(1)。

代码实现

package org.zyf.javabasic.letcode.jd150.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: zyfboot-javabasic
 * @description: 赎金信
 * @author: zhangyanfeng
 * @create: 2024-08-25 11:56
 **/
public class CanConstruct {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 使用 HashMap 统计 magazine 中每个字符的频率
        Map<Character, Integer> magazineCount = new HashMap<>();

        // 遍历 magazine 统计每个字符的出现次数
        for (char c : magazine.toCharArray()) {
            magazineCount.put(c, magazineCount.getOrDefault(c, 0) + 1);
        }

        // 遍历 ransomNote 检查是否有足够的字符
        for (char c : ransomNote.toCharArray()) {
            // 如果 magazine 中没有字符 c，或字符 c 的数量不足
            if (!magazineCount.containsKey(c) || magazineCount.get(c) == 0) {
                return false; // 无法构造 ransomNote
            }
            // 使用一个字符 c，减少其在 magazine 中的频率
            magazineCount.put(c, magazineCount.get(c) - 1);
        }

        // 如果遍历完 ransomNote 中的所有字符后，没有问题，则返回 true
        return true;
    }
}

40.同构字符串（简单）

题目描述

解题思路

41.单词规律（简单）

题目描述

解题思路

42.有效的字母异位词（简单）

题目描述

解题思路

具体可见散列表相关知识及编程练习总结_散列函数情景题-CSDN博客中的第5题。

43.字母异位词分组（中等）

题目描述

解题思路

具体可见散列表相关知识及编程练习总结_散列函数情景题-CSDN博客中的第4题。

具体可见LeetCode 热题 100 回顾-CSDN博客中的第2题。

44.两数之和（简单）

题目描述

解题思路

具体可见数组知识及编程练习总结-CSDN博客中的第1题。

具体可见LeetCode 热题 100 回顾-CSDN博客中的第1题。

45.快乐数（简单）

题目描述

解题思路

具体可见数学思维编程练习总结_编程中的数学思维-CSDN博客中的第3题。

也可见散列表相关知识及编程练习总结_散列函数情景题-CSDN博客中的第10题。

46.存在重复元素 II（简单）

题目描述

解题思路

也可见散列表相关知识及编程练习总结_散列函数情景题-CSDN博客中的第12题。

47.最长连续序列（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第3题。

六、区间

48.汇总区间（简单）

题目描述

解题思路

为了找到最小的有序区间范围列表，我们可以使用以下思路：

遍历数组：我们从数组的第一个元素开始，逐个检查元素。
确定区间：对于每个元素，检查它是否与下一个元素连续。如果是，则继续扩展当前区间。如果不是，则结束当前区间并开始新的区间。
处理边界：当我们处理到数组的末尾时，要确保最后一个区间被正确处理。
格式化区间：对于每个区间，根据开始和结束值的关系，格式化为“a->b”或者“a”。

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需遍历一次数组来构建区间。
空间复杂度：O(n)，用于存储区间范围列表的结果。

代码实现

package org.zyf.javabasic.letcode.jd150.ranges;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: zyfboot-javabasic
 * @description: 汇总区间
 * @author: zhangyanfeng
 * @create: 2024-08-25 12:21
 **/
public class FindRanges {
    public List<String> findRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        if (nums.length == 0) {
            return result; // 如果数组为空，返回空列表
        }

        int start = nums[0]; // 区间起始值
        int end = nums[0];   // 区间结束值

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == end + 1) {
                // 如果当前元素与结束值连续，扩展当前区间
                end = nums[i];
            } else {
                // 否则，结束当前区间，添加到结果中，并开始新的区间
                result.add(formatRange(start, end));
                start = nums[i];
                end = nums[i];
            }
        }

        // 处理最后一个区间
        result.add(formatRange(start, end));
        return result;
    }

    private String formatRange(int start, int end) {
        // 格式化区间为字符串
        if (start == end) {
            return String.valueOf(start);
        } else {
            return start + "->" + end;
        }
    }

    public static void main(String[] args) {
        FindRanges sol = new FindRanges();
        int[] nums1 = {0, 1, 2, 4, 5, 7};
        int[] nums2 = {0, 2, 3, 4, 6, 8, 9};

        System.out.println(sol.findRanges(nums1)); // 输出: ["0->2","4->5","7"]
        System.out.println(sol.findRanges(nums2)); // 输出: ["0","2->4","6","8->9"]
    }
}

49.合并区间（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第14题。

具体可见数组知识及编程练习总结-CSDN博客中的第14题。

50.插入区间（中等）

题目描述

解题思路

初始化变量：
result：一个 List<int[]> 用于存储最终的结果。i：用于遍历 intervals 的指针。
处理新区间之前的区间：遍历 intervals，将所有在 newInterval 之前且不与 newInterval 重叠的区间直接添加到 result 中。
合并新区间：对于与 newInterval 重叠的区间，更新 newInterval 的范围，以合并这些重叠区间。更新后的 newInterval 范围将包括所有与之重叠的区间。
处理新区间之后的区间：将所有不与合并后的 newInterval 重叠的区间添加到 result 中。
转换结果格式：将 List<int[]> 转换为 int[][] 并返回。

复杂度分析

时间复杂度：O(n)，其中 n 是 intervals 的长度。我们只需遍历一次 intervals 来完成合并和插入操作。
空间复杂度：O(n)，用于存储结果列表 result。

代码实现

package org.zyf.javabasic.letcode.jd150.ranges;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: zyfboot-javabasic
 * @description: 插入区间
 * @author: zhangyanfeng
 * @create: 2024-08-25 12:28
 **/
public class InsertInterval {
    public List<List<Integer>> insertInterval(List<List<Integer>> intervals, List<Integer> newInterval) {
        List<List<Integer>> result = new ArrayList<>();
        int i = 0;
        int n = intervals.size();

        // 添加所有在 newInterval 之前且不重叠的区间
        while (i < n && intervals.get(i).get(1) < newInterval.get(0)) {
            result.add(intervals.get(i++));
        }

        // 合并所有与 newInterval 重叠的区间
        while (i < n && intervals.get(i).get(0) <= newInterval.get(1)) {
            newInterval.set(0, Math.min(newInterval.get(0), intervals.get(i).get(0)));
            newInterval.set(1, Math.max(newInterval.get(1), intervals.get(i).get(1)));
            i++;
        }
        result.add(newInterval);

        // 添加所有在 newInterval 之后且不重叠的区间
        while (i < n) {
            result.add(intervals.get(i++));
        }

        return result;
    }

    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        // 添加所有在 newInterval 之前且不重叠的区间
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i++]);
        }

        // 合并所有与 newInterval 重叠的区间
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

        // 添加所有在 newInterval 之后且不重叠的区间
        while (i < n) {
            result.add(intervals[i++]);
        }

        // 将结果转换为 int[][] 并返回
        return result.toArray(new int[result.size()][]);
    }

    public static void main(String[] args) {
        InsertInterval sol = new InsertInterval();

        int[][] intervals1 = {{1, 3}, {6, 9}};
        int[] newInterval1 = {2, 5};

        int[][] intervals2 = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
        int[] newInterval2 = {4, 8};

        // 打印输出结果
        printResult(sol.insert(intervals1, newInterval1)); // 输出: [[1, 5], [6, 9]]
        printResult(sol.insert(intervals2, newInterval2)); // 输出: [[1, 2], [3, 10], [12, 16]]
    }

    private static void printResult(int[][] result) {
        for (int[] interval : result) {
            System.out.println("[" + interval[0] + ", " + interval[1] + "]");
        }
    }
}

51.用最少数量的箭引爆气球（中等）

题目描述

解题思路

具体可见LeetCode 精选 75 回顾-CSDN博客中的第73题。

七、栈

52.有效的括号（简单）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第69题。

也可见栈知识及编程练习总结-CSDN博客中的第1题。

53.简化路径（中等）

题目描述

解题思路

可见栈知识及编程练习总结-CSDN博客中的第9题。

54.最小栈（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第70题。

也可见栈知识及编程练习总结-CSDN博客中的第2题。

55.逆波兰表达式求值（中等）

题目描述

解题思路

可见栈知识及编程练习总结-CSDN博客中的第7题。

56.基本计算器（困难）

题目描述

解题思路

可见栈知识及编程练习总结-CSDN博客中的第8题。

八、链表

57.环形链表（简单）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第25题。

也可见链表知识及编程练习总结中第2题。

58.两数相加（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第28题。

也可见链表知识及编程练习总结中第15题。

59.合并两个有序链表（简单）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第27题。

也可见链表知识及编程练习总结中第7题。

60.随机链表的复制（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第32题。

61.反转链表 II（中等）

题目描述

解题思路

可见链表知识及编程练习总结中第20题。

62.K 个一组翻转链表（困难）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第31题。

也可见链表知识及编程练习总结中第10题。

63.删除链表的倒数第 N 个结点（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第29题。

也可见链表知识及编程练习总结中第4题。

64.删除排序链表中的重复元素 II（中等）

题目描述

解题思路

可见链表知识及编程练习总结中第9题。

65.旋转链表（中等）

题目描述

解题思路

可见链表知识及编程练习总结中第11题。

66.分隔链表（中等）

题目描述

解题思路

可见链表知识及编程练习总结中第12题。

67.LRU 缓存（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第35题。

也可见散列表相关知识及编程练习总结_散列函数情景题-CSDN博客中第7题。

加强版可见聚焦新版综合编程能力面试考查汇总_关于编程有什么问题可以提问-CSDN博客中第7题。

九、二叉树

68.二叉树的最大深度（简单）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第37题。

也可见树相关知识及编程练习总结_树编程-CSDN博客中第2题。

69.相同的树（简单）

题目描述

解题思路

要判断两棵二叉树是否相同，我们可以使用递归的方法逐节点进行比较：

基础情况：
- 如果两个节点都为 null，则它们相同，返回 true。
- 如果其中一个节点为 null 而另一个不为 null，则它们不同，返回 false。
- 如果两个节点的值不相同，也返回 false。
递归判断子树：
- 递归比较左子树和右子树是否相同。
- 如果左子树和右子树都相同，则当前子树相同。

复杂度分析

时间复杂度：每个节点在递归时只访问一次，因此时间复杂度为 O(n)，其中 n 是树中的节点数。
空间复杂度：最坏情况下（即树是链状的），递归栈的深度为 O(n)，所以空间复杂度也是 O(n)。

代码实现

package org.zyf.javabasic.letcode.jd150.tree;

import org.zyf.javabasic.letcode.tree.base.TreeNode;

/**
 * @program: zyfboot-javabasic
 * @description: 相同的树
 * @author: zhangyanfeng
 * @create: 2024-08-25 13:40
 **/
public class SameTree {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 如果两个节点都为 null，则两棵树相同
        if (p == null && q == null) {
            return true;
        }
        // 如果其中一个节点为 null 或者两个节点的值不同，则两棵树不相同
        if (p == null || q == null || p.val != q.val) {
            return false;
        }
        // 递归判断左右子树是否相同
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public static void main(String[] args) {
        SameTree sol = new SameTree();

        // 示例 1
        TreeNode p1 = new TreeNode(1);
        p1.left = new TreeNode(2);
        p1.right = new TreeNode(3);
        TreeNode q1 = new TreeNode(1);
        q1.left = new TreeNode(2);
        q1.right = new TreeNode(3);

        // 示例 2
        TreeNode p2 = new TreeNode(1);
        p2.left = new TreeNode(2);
        TreeNode q2 = new TreeNode(1);
        q2.right = new TreeNode(2);

        // 示例 3
        TreeNode p3 = new TreeNode(1);
        p3.left = new TreeNode(2);
        p3.right = new TreeNode(1);
        TreeNode q3 = new TreeNode(1);
        q3.left = new TreeNode(1);
        q3.right = new TreeNode(2);

        System.out.println(sol.isSameTree(p1, q1)); // 输出: true
        System.out.println(sol.isSameTree(p2, q2)); // 输出: false
        System.out.println(sol.isSameTree(p3, q3)); // 输出: false
    }
}

70.翻转二叉树（简单）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第38题。

也可见树相关知识及编程练习总结_树编程-CSDN博客中第12题。

71.对称二叉树（简单）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第39题。

也可见树相关知识及编程练习总结_树编程-CSDN博客中第4题。

72.从前序与中序遍历序列构造二叉树（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第47题。

也可见树相关知识及编程练习总结_树编程-CSDN博客中第16题。

73. 从中序与后序遍历序列构造二叉树（中等）

题目描述

解题思路

要根据中序遍历（inorder）和后序遍历（postorder）构造二叉树，可以利用后序遍历的特性：后序遍历的最后一个元素是树的根节点。

从后序遍历中找到根节点：后序遍历的最后一个元素是当前子树的根节点。
在中序遍历中定位根节点：在中序遍历中找到根节点的位置，这样可以将中序遍历划分为左子树和右子树。
递归构造左右子树：
递归地在左子树的中序和后序遍历中构造左子树。递归地在右子树的中序和后序遍历中构造右子树。
构造并返回根节点：将左右子树连接到根节点上，返回构造的树。

复杂度分析

时间复杂度：构建二叉树的时间复杂度为 O(n)，其中 n 是树中的节点数。每个节点只处理一次。
空间复杂度：由于使用了递归，空间复杂度取决于递归调用的深度，即 O(h)，其中 h 是树的高度。最坏情况下，树是线性的，此时空间复杂度为 O(n)。

代码实现

package org.zyf.javabasic.letcode.jd150.tree;

import org.zyf.javabasic.letcode.tree.base.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: zyfboot-javabasic
 * @description: 从中序与后序遍历序列构造二叉树
 * @author: zhangyanfeng
 * @create: 2024-08-25 13:50
 **/
public class BuildTree {
    private Map<Integer, Integer> inorderIndexMap;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        // 创建一个哈希映射以存储中序遍历中每个值的索引
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
        // 从后序遍历和中序遍历构建二叉树
        return buildTreeHelper(postorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode buildTreeHelper(int[] postorder, int postStart, int postEnd, int inStart, int inEnd) {
        // 如果索引无效，返回 null
        if (postStart > postEnd || inStart > inEnd) {
            return null;
        }
        // 后序遍历的最后一个节点是当前子树的根节点
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置
        int inRootIndex = inorderIndexMap.get(rootVal);
        int leftSubtreeSize = inRootIndex - inStart;

        // 递归构建左子树
        root.left = buildTreeHelper(postorder, postStart, postStart + leftSubtreeSize - 1, inStart, inRootIndex - 1);
        // 递归构建右子树
        root.right = buildTreeHelper(postorder, postStart + leftSubtreeSize, postEnd - 1, inRootIndex + 1, inEnd);

        return root;
    }

    public static void main(String[] args) {
        BuildTree sol = new BuildTree();
        int[] inorder1 = {9, 3, 15, 20, 7};
        int[] postorder1 = {9, 15, 7, 20, 3};

        TreeNode root1 = sol.buildTree(inorder1, postorder1);
        printPreorder(root1); // 输出前序遍历结果验证树的构造
    }

    private static void printPreorder(TreeNode node) {
        if (node != null) {
            System.out.print(node.val + " ");
            printPreorder(node.left);
            printPreorder(node.right);
        }
    }
}

74.填充每个节点的下一个右侧节点指针 II（中等）

题目描述

解题思路

采了逐层遍历二叉树的方法，不使用额外的空间，直接利用二叉树的 next 指针来遍历每一层。通过维护指向每一层最左侧节点的 start 指针，遍历该层节点，并同时建立下一层节点之间的 next 连接。具体步骤如下：

初始化指针：start：指向当前层的最左节点。last：指向当前层中已连接的最后一个节点。nextStart：指向下一层最左节点。
逐层处理：
对当前层的每个节点，分别处理其左子节点和右子节点，建立 next 连接。更新 nextStart，以确保下一层遍历从该层的第一个节点开始。

复杂度分析

时间复杂度：O(n)，其中 n 为二叉树中的节点总数。每个节点仅访问一次。
空间复杂度：O(1)，使用了常量级别的额外空间。

代码实现

package org.zyf.javabasic.letcode.jd150.tree;

/**
 * @program: zyfboot-javabasic
 * @description: 填充每个节点的下一个右侧节点指针 II
 * @author: zhangyanfeng
 * @create: 2024-08-25 13:57
 **/
public class Connect {
    Node last = null;        // 当前层已连接的最后一个节点
    Node nextStart = null;   // 下一层最左侧的起始节点

    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Node start = root;   // 从根节点开始
        while (start != null) {
            last = null;
            nextStart = null;
            for (Node p = start; p != null; p = p.next) {
                if (p.left != null) {
                    handle(p.left);  // 处理左子节点
                }
                if (p.right != null) {
                    handle(p.right); // 处理右子节点
                }
            }
            start = nextStart;  // 转向下一层的最左节点
        }
        return root;
    }

    // 处理每个节点，连接next指针
    public void handle(Node p) {
        if (last != null) {
            last.next = p;   // 将上一个节点的next指向当前节点
        }
        if (nextStart == null) {
            nextStart = p;   // 记录下一层的起始节点
        }
        last = p;  // 更新last为当前节点
    }

    public static void main(String[] args) {
        Connect sol = new Connect();

        // 示例测试
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(7);

        sol.connect(root);
        printLevels(root);
    }

    // 辅助函数：按层打印节点的 next 连接结果
    private static void printLevels(Node root) {
        Node levelStart = root;
        while (levelStart != null) {
            Node current = levelStart;
            while (current != null) {
                System.out.print(current.val + " ");
                current = current.next;
            }
            System.out.println("#");
            levelStart = levelStart.left;
        }
    }

    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }
}

75.二叉树展开为链表（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第46题。

76.路径总和（简单）

题目描述

解题思路

也可见树相关知识及编程练习总结_树编程-CSDN博客中第7题。

要判断二叉树中是否存在一条从根节点到叶子节点的路径，使得路径上所有节点值的和等于给定的 targetSum，可以采用递归或深度优先搜索（DFS）的方式。具体步骤：

递归遍历：从根节点开始，递归遍历每个节点的左右子树，同时将当前节点的值从 targetSum 中减去。
叶子节点判断：当到达叶子节点时，检查剩余的 targetSum 是否等于该叶子节点的值。如果是，则找到了符合条件的路径；否则，继续在左右子树中查找。
边界条件：如果节点为空，则直接返回 false；如果遍历到叶子节点并且 targetSum 恰好等于当前节点值，返回 true。

复杂度分析

时间复杂度：O(n)，其中 n 是树中的节点数。最坏情况下，需要遍历每个节点一次。
空间复杂度：O(h)，其中 h 是树的高度。空间主要消耗在递归调用栈上，最坏情况下（例如完全不平衡树），递归深度等于树的高度。

代码实现

package org.zyf.javabasic.letcode.jd150.tree;

import org.zyf.javabasic.letcode.tree.base.TreeNode;

/**
 * @program: zyfboot-javabasic
 * @description: 路径总和
 * @author: zhangyanfeng
 * @create: 2024-08-25 14:07
 **/
public class HasPathSum {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false; // 如果当前节点为空，直接返回 false
        }

        // 如果当前节点是叶子节点，判断路径和是否等于 targetSum
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }

        // 递归检查左右子树是否存在符合条件的路径
        int remainingSum = targetSum - root.val;
        return hasPathSum(root.left, remainingSum) || hasPathSum(root.right, remainingSum);
    }

    public static void main(String[] args) {
        HasPathSum sol = new HasPathSum();

        // 示例 1 测试
        TreeNode root1 = new TreeNode(5);
        root1.left = new TreeNode(4);
        root1.right = new TreeNode(8);
        root1.left.left = new TreeNode(11);
        root1.left.left.left = new TreeNode(7);
        root1.left.left.right = new TreeNode(2);
        root1.right.left = new TreeNode(13);
        root1.right.right = new TreeNode(4);
        root1.right.right.right = new TreeNode(1);

        System.out.println(sol.hasPathSum(root1, 22)); // 输出: true

        // 示例 2 测试
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(3);

        System.out.println(sol.hasPathSum(root2, 5)); // 输出: false

        // 示例 3 测试
        TreeNode root3 = null;

        System.out.println(sol.hasPathSum(root3, 0)); // 输出: false
    }
}

77.求根节点到叶节点数字之和（中等）

题目描述

解题思路

可见树相关知识及编程练习总结_树编程-CSDN博客中第18题。

78.二叉树中的最大路径和（困难）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第50题。

79.二叉搜索树迭代器（中等）

题目描述

解题思路

二叉搜索树迭代器 (BSTIterator) 的目标是实现按中序遍历（从小到大）逐步返回二叉搜索树中的节点值。由于二叉搜索树（BST）的性质，中序遍历即为有序的节点值排列。

要实现一个高效的迭代器，考虑以下几点：

存储结构：可以使用栈来存储遍历路径上的节点，确保能够按顺序访问。
迭代过程：每次调用 next() 时，从栈中弹出一个节点，并将该节点的右子树的所有左子节点压栈，确保下次访问的是当前节点的后继。
时间复杂度：next() 和 hasNext() 操作的均摊时间复杂度应为 O(1)，因为每个节点仅进栈和出栈一次。
空间复杂度：需要 O(h) 的空间来存储栈，其中 h 是树的高度。

复杂度分析

时间复杂度：
- next(): O(1) 均摊时间复杂度。
- hasNext(): O(1)。
空间复杂度：O(h)，其中 h 是树的高度。

代码实现

package org.zyf.javabasic.letcode.jd150.tree;

import org.zyf.javabasic.letcode.tree.base.TreeNode;

import java.util.Stack;

/**
 * @program: zyfboot-javabasic
 * @description: 二叉搜索树迭代器
 * @author: zhangyanfeng
 * @create: 2024-08-25 14:24
 **/
public class BSTIterator {
    private Stack<TreeNode> stack;

    // 初始化迭代器，压入左侧路径上的所有节点
    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        pushLeftBranch(root);
    }

    // 检查是否有下一个节点
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    // 返回下一个最小的节点值
    public int next() {
        TreeNode node = stack.pop(); // 弹出栈顶节点
        int result = node.val;
        pushLeftBranch(node.right); // 如果有右子树，将右子树的左侧路径压入栈中
        return result;
    }

    // 将从当前节点开始的左侧路径上的所有节点压栈
    private void pushLeftBranch(TreeNode node) {
        while (node != null) {
            stack.push(node); // 压入当前节点
            node = node.left; // 向左移动
        }
    }
}

80.完全二叉树的节点个数（简单）

题目描述

解题思路

完全二叉树的定义是，除了最后一层之外，其他层都是满的。如果我们能够快速计算某个子树的高度，并且通过这种高度来判断该子树是否是完全的，那么我们就可以快速地计算出该子树的节点数量。

计算高度：
左子树的高度leftHeight从根节点沿左子树路径一直走到叶子节点。右子树的高度rightHeight从根节点沿右子树路径一直走到叶子节点。
判断完全性：
如果leftHeight == rightHeight，说明这个树是满的二叉树，高度为h，节点总数为2^h - 1。如果leftHeight != rightHeight，说明这个树的最后一层没有填满，此时我们需要递归地计算左右子树的节点数。
递归：
如果是满的子树，直接返回节点数。否则，递归地对左右子树求解，最终得到整个树的节点总数。

复杂度分析

由于高度计算是O(log n)，而我们每次递归会减少一层，所以整体时间复杂度为O(log n * log n)。

代码实现

package org.zyf.javabasic.letcode.jd150.tree;

import org.zyf.javabasic.letcode.tree.base.TreeNode;

/**
 * @program: zyfboot-javabasic
 * @description: 完全二叉树的节点个数
 * @author: zhangyanfeng
 * @create: 2024-08-25 14:29
 **/
public class CountNodes {
    public int countNodes(TreeNode root) {
        // 如果根节点为空，直接返回0
        if (root == null) {
            return 0;
        }

        // 计算左子树高度
        int leftHeight = getHeight(root.left);
        // 计算右子树高度
        int rightHeight = getHeight(root.right);

        // 如果左子树高度等于右子树高度，说明左子树是满的
        if (leftHeight == rightHeight) {
            // 直接返回左子树节点数 + 右子树递归节点数 + 根节点1
            return (1 << leftHeight) + countNodes(root.right);
        } else {
            // 否则，右子树是满的
            // 直接返回右子树节点数 + 左子树递归节点数 + 根节点1
            return (1 << rightHeight) + countNodes(root.left);
        }
    }

    // 辅助函数，计算树的高度
    private int getHeight(TreeNode root) {
        int height = 0;
        while (root != null) {
            height++;
            root = root.left;
        }
        return height;
    }
}

81.二叉树的最近公共祖先（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第49题。

也可见树相关知识及编程练习总结_树编程-CSDN博客中第5题。

十、二叉树层次遍历

82.二叉树的右视图（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第45题。

也可见LeetCode 精选 75 回顾-CSDN博客中的第39题。

也可见树相关知识及编程练习总结_树编程-CSDN博客中第5题。

83.二叉树的层平均值（简单）

题目描述

解题思路

可见树相关知识及编程练习总结_树编程-CSDN博客中第11题。

84.二叉树的层序遍历（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第41题。

也可见树相关知识及编程练习总结_树编程-CSDN博客中第1题。

85.二叉树的锯齿形层序遍历（中等）

题目描述

解题思路

锯齿形层序遍历（Zigzag Level Order Traversal）是二叉树的广度优先搜索（BFS）的变形。我们可以用一个队列来实现层序遍历，然后通过一个标志位来控制节点的访问顺序是从左到右还是从右到左。具体步骤如下：

使用队列进行层序遍历，将根节点加入队列。
初始化一个布尔变量 leftToRight 表示当前层是否从左往右遍历。
对于每一层，先获取当前队列的大小 levelSize（表示这一层的节点数）。
初始化一个双端队列 Deque<Integer> level 来存储当前层的结果。如果是从左到右遍历，则直接在 level 的尾部添加节点值；如果是从右到左遍历，则在 level 的头部添加节点值。
将当前层的节点值添加到 result 列表中，并切换 leftToRight 的值。
重复上述步骤，直到队列为空。

复杂度分析

时间复杂度: O(n)，其中 n 是二叉树的节点数。我们需要遍历每个节点一次。
空间复杂度: O(n)，最坏情况下队列中需要存储 n/2 个节点。

代码实现

package org.zyf.javabasic.letcode.jd150.tree;

import org.zyf.javabasic.letcode.tree.base.TreeNode;

import java.util.*;

/**
 * @program: zyfboot-javabasic
 * @description: 二叉树的锯齿形层序遍历
 * @author: zhangyanfeng
 * @create: 2024-08-25 14:44
 **/
public class ZigzagLevelOrder {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 定义结果列表
        List<List<Integer>> result = new ArrayList<>();
        // 如果树为空，直接返回空列表
        if (root == null) {
            return result;
        }

        // 初始化队列进行层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 标志位，初始为从左到右
        boolean leftToRight = true;

        while (!queue.isEmpty()) {
            // 当前层的节点数量
            int levelSize = queue.size();
            // 使用双端队列来存储当前层的节点值
            Deque<Integer> level = new LinkedList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (leftToRight) {
                    // 从左到右，将节点值添加到队列的尾部
                    level.offerLast(node.val);
                } else {
                    // 从右到左，将节点值添加到队列的头部
                    level.offerFirst(node.val);
                }
                // 将当前节点的左右子节点加入队列
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 将当前层的结果添加到结果列表
            result.add(new LinkedList<>(level));
            // 切换遍历方向
            leftToRight = !leftToRight;
        }

        return result;
    }
}

十一、二叉搜索树

86.二叉搜索树的最小绝对差（简单）

题目描述

解题思路

二叉搜索树（BST）具有一个重要性质：对于任意节点，其左子树的所有节点值都小于该节点值，右子树的所有节点值都大于该节点值。因此，BST 的中序遍历结果是一个递增的有序序列。

基于此性质，求任意两不同节点值之间的最小差值，可以通过以下步骤完成：

中序遍历：对 BST 进行中序遍历，得到一个有序的节点值列表。
计算最小差值：在有序列表中，任意两个相邻元素的差值是可能的最小差值。遍历这个列表，计算所有相邻元素的差值，并记录其中的最小值。

复杂度分析

时间复杂度: O(n)，其中 n 是树中的节点数。中序遍历需要访问每个节点一次，后续的最小差值计算也是 O(n)。
空间复杂度: O(n)，用于存储中序遍历的节点值列表。在最优的情况下，可以使用 O(h) 的空间，其中 h 是树的高度。

代码实现

package org.zyf.javabasic.letcode.jd150.tree;

import org.zyf.javabasic.letcode.tree.base.TreeNode;

/**
 * @program: zyfboot-javabasic
 * @description: 二叉搜索树的最小绝对差
 * @author: zhangyanfeng
 * @create: 2024-08-25 14:50
 **/
public class MinDiffInBST {
    // 记录上一个节点的值，初始为极小值
    private Integer prev = null;
    // 记录最小差值，初始为最大值
    private int minDiff = Integer.MAX_VALUE;

    public int minDiffInBST(TreeNode root) {
        // 调用中序遍历的辅助函数
        inOrder(root);
        return minDiff;
    }

    private void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        // 中序遍历左子树
        inOrder(node.left);

        // 处理当前节点
        if (prev != null) {
            // 计算当前节点与上一个节点值的差，并更新最小差值
            minDiff = Math.min(minDiff, node.val - prev);
        }
        // 更新上一个节点值
        prev = node.val;

        // 中序遍历右子树
        inOrder(node.right);
    }
}

87.二叉搜索树中第 K 小的元素（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第44题。

88.验证二叉搜索树（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第43题。

十二、图

89.岛屿数量（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第51题。

也可见图论总结与编程练习_编程图论-CSDN博客中的第3题。

90.被围绕的区域（中等）

题目描述

解题思路

要解决这个问题，我们可以使用以下步骤：

标记边缘的 'O': 首先遍历矩阵的边缘（上下左右四条边），对所有边缘的 'O' 进行深度优先搜索（DFS）或广度优先搜索（BFS），将所有能够连接到边缘的 'O' 标记为特殊字符（例如 '#'）。这些标记的 'O' 表示它们不被完全围绕。
替换内部的 'O': 遍历整个矩阵，将所有未被标记的 'O' 替换为 'X'，因为这些 'O' 是被完全围绕的区域。
恢复边缘的 'O': 将之前标记的 '#' 恢复为 'O'，以还原这些区域的原始状态。

复杂度分析

时间复杂度: O(m * n)，其中 m 和 n 分别是矩阵的行数和列数。我们需要遍历矩阵的每个位置多次（标记、替换、恢复），每个位置操作的时间复杂度为 O(1)。
空间复杂度: O(m * n)，主要用于存储矩阵和标记的临时空间。

代码实现

package org.zyf.javabasic.letcode.jd150.graph;

/**
 * @program: zyfboot-javabasic
 * @description: 被围绕的区域
 * @author: zhangyanfeng
 * @create: 2024-08-25 14:58
 **/
public class Solve {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }

        int m = board.length;
        int n = board[0].length;

        // 使用 DFS 标记边缘的 'O'
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                dfs(board, i, n - 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[m - 1][j] == 'O') {
                dfs(board, m - 1, j);
            }
        }

        // 将内部的 'O' 替换为 'X'，恢复边缘的 'O'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void dfs(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
            return;
        }
        // 标记为 '#'
        board[i][j] = '#';
        // 递归四个方向
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }
}

91.克隆图（中等）

题目描述

解题思路

也可见图论总结与编程练习_编程图论-CSDN博客中的第2题。

92.除法求值（中等）

题目描述

解题思路

可见LeetCode 精选 75 回顾-CSDN博客中的第46题。

93.课程表（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第53题。

94.课程表 II（中等）

题目描述

解题思路

这个问题可以转化为 拓扑排序 问题，其中每门课程和其前置课程形成一个有向图，我们需要对这个有向图进行拓扑排序来确定课程的学习顺序。这里使用Kahn算法（基于入度的拓扑排序算法）来实现这一过程，步骤如下：

构建图：使用邻接表来表示图，其中每个节点（课程）指向它的后续课程。同时计算每个节点的入度（即有多少课程依赖于这个课程）。
初始化队列：将所有入度为 0 的节点（课程）加入队列，因为这些课程没有前置课程，可以直接学习。
执行拓扑排序：从队列中取出节点，并将其添加到拓扑排序结果中。对于每个出队的节点，减少其所有邻居节点的入度，并将入度变为 0 的邻居节点加入队列。
检查结果：如果拓扑排序结果中的节点数量等于总节点数量，说明可以完成所有课程，返回排序结果。如果节点数量不等于总节点数量，说明存在环，无法完成所有课程，返回空数组。

复杂度分析

时间复杂度：O(V + E)，其中 V 是图中的节点数（课程数），E 是边数（先修关系）。构建图和计算入度的时间复杂度为 O(V + E)，拓扑排序的时间复杂度也是 O(V + E)。
空间复杂度：O(V + E)，用于存储图的邻接表、入度数组以及队列。

代码实现

package org.zyf.javabasic.letcode.jd150.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: zyfboot-javabasic
 * @description: 课程表 II
 * @author: zhangyanfeng
 * @create: 2024-08-25 17:33
 **/
public class FindOrder {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 初始化图的邻接表和入度数组
        List<Integer>[] graph = new ArrayList[numCourses];
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }

        // 构建图和计算每个节点的入度
        for (int[] pair : prerequisites) {
            int dest = pair[0];
            int src = pair[1];
            graph[src].add(dest);
            inDegree[dest]++;
        }

        // 初始化队列并将所有入度为0的节点入队
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 执行拓扑排序
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);

            for (int neighbor : graph[node]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 如果排序结果的节点数等于总课程数，则返回结果，否则返回空数组
        if (result.size() == numCourses) {
            return result.stream().mapToInt(i -> i).toArray();
        } else {
            return new int[0];
        }
    }
}

十三、图的广度优先搜索

95.蛇梯棋（中等）

题目描述

解题思路

要解决这个问题，我们可以将其建模为一个图的最短路径问题，使用广度优先搜索（BFS）来寻找从起点到终点的最短路径：

构建图表示：将二维矩阵转换为一维的节点编号。处理从每个节点可以跳转到的目标节点，这些目标节点范围在 [curr + 1, min(curr + 6, n^2)] 之间。
处理蛇和梯子：如果目标节点上有蛇或梯子，则移动到目标节点的实际位置，而不是目标节点的编号。
广度优先搜索（BFS）：使用 BFS 从起点节点（编号为 1）开始探索，记录每个节点的最短路径长度。每次从当前节点出发，考虑所有可能的掷骰子结果（最多 6 个节点）。将每个可能的节点入队，继续探索，直到找到目标节点（编号为 n^2）或队列为空。
终止条件：如果到达编号为 n^2 的节点，返回所需的最小移动次数。如果 BFS 结束时仍未找到，返回 -1。

复杂度分析

时间复杂度：O(n^2)，因为每个节点最多入队一次，每次操作都在 O(1) 时间内完成。
空间复杂度：O(n^2)，用于存储 BFS 队列和已访问节点。

代码实现

package org.zyf.javabasic.letcode.jd150.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: zyfboot-javabasic
 * @description: 蛇梯棋
 * @author: zhangyanfeng
 * @create: 2024-08-25 17:38
 **/
public class SnakesAndLadders {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        // 将二维坐标转换为一维坐标的映射
        int[] flatBoard = new int[n * n + 1];
        boolean leftToRight = true; // 矩阵从底行开始处理，方向交替
        int index = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (leftToRight) {
                for (int j = 0; j < n; j++) {
                    flatBoard[index++] = board[i][j];
                }
            } else {
                for (int j = n - 1; j >= 0; j--) {
                    flatBoard[index++] = board[i][j];
                }
            }
            leftToRight = !leftToRight;
        }

        // BFS 初始化
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n * n + 1];
        queue.offer(1); // 从方格1开始
        visited[1] = true;
        int moves = 0;

        // BFS 开始
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                if (curr == n * n) return moves; // 到达终点

                // 遍历所有可能的骰子结果
                for (int dice = 1; dice <= 6; dice++) {
                    int next = curr + dice;
                    if (next > n * n) break; // 超过棋盘范围

                    // 处理蛇或梯子
                    if (flatBoard[next] != -1) {
                        next = flatBoard[next];
                    }

                    if (!visited[next]) {
                        visited[next] = true;
                        queue.offer(next);
                    }
                }
            }
            moves++;
        }

        return -1; // 无法到达终点
    }
}

96.最小基因变化（中等）

题目描述

解题思路

要解决这个问题，我们可以将其建模为一个图的最短路径问题，其中每个基因序列是一个图中的节点，每次变化表示从一个节点到另一个节点的边。由于每次基因变化只允许一个字符的变化，因此图的边是通过改变一个字符来连接的:

建模为图：每个基因序列视为图中的一个节点。从一个基因序列到另一个基因序列的边存在，当且仅当这两个序列只有一个字符的差异。
使用广度优先搜索（BFS）：从 start 基因序列开始，使用 BFS 遍历所有可能的基因变化。使用一个队列来存储当前基因序列及其变化次数。使用一个集合来记录已访问的基因序列，避免重复访问。
终止条件：如果在 BFS 遍历过程中找到 end 基因序列，返回当前的变化次数。如果 BFS 完成后未找到 end 基因序列，返回 -1。

复杂度分析

时间复杂度：O(N * L * 4^L)，其中 N 是基因库的大小，L 是基因序列的长度（在此问题中是 8）。对于每个基因序列，我们需要检查其所有可能的变种（4^L），并在队列中进行 BFS 操作。
空间复杂度：O(N)，用于存储基因库和已访问集合。

代码实现

package org.zyf.javabasic.letcode.jd150.graph;

import java.util.*;

/**
 * @program: zyfboot-javabasic
 * @description: 最小基因变化
 * @author: zhangyanfeng
 * @create: 2024-08-25 17:42
 **/
public class MinMutation {
    public int minMutation(String start, String end, String[] bank) {
        // 将基因库转为集合以便快速查找
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));

        // 如果目标基因序列不在基因库中，则直接返回 -1
        if (!bankSet.contains(end)) {
            return -1;
        }

        // 初始化 BFS 队列，起始基因序列和变化次数为 0
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        int mutations = 0;

        // 进行 BFS
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                // 如果当前基因序列等于目标基因序列，则返回变化次数
                if (curr.equals(end)) {
                    return mutations;
                }

                // 尝试每个可能的变化
                for (int j = 0; j < curr.length(); j++) {
                    char[] chars = curr.toCharArray();
                    for (char c = 'A'; c <= 'Z'; c++) {
                        if (chars[j] == c) continue; // 如果字符相同则跳过
                        chars[j] = c;
                        String next = new String(chars);
                        // 如果变换后的基因序列在基因库中，且未被访问过
                        if (bankSet.contains(next)) {
                            queue.offer(next);
                            bankSet.remove(next); // 标记为已访问
                        }
                    }
                }
            }
            mutations++; // 增加变化次数
        }

        // 如果无法到达目标基因序列，返回 -1
        return -1;
    }
}

97.单词接龙（困难）

题目描述

解题思路

也可见图论总结与编程练习_编程图论-CSDN博客中的第1题。

十四、字典树

98.实现 Trie (前缀树)（中等）

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第54题。

99.添加与搜索单词 - 数据结构设计（中等）

题目描述

解题思路

要实现一个支持添加单词和匹配单词的词典数据结构，我们可以使用Trie（前缀树）：

设计思路

Trie 数据结构：每个节点代表一个字符，节点的子节点表示继续匹配的字符。节点中保存一个布尔值 isEndOfWord 来标记是否有单词在该节点结束。
支持通配符匹配：使用递归函数来处理 . 通配符，尝试匹配所有可能的字符。在递归过程中，当遇到 . 时，需要遍历该节点的所有子节点。

操作细节

添加单词 (addWord)：遍历每个字符，将其插入到 Trie 中。最后一个字符的节点标记为 isEndOfWord。
查找单词 (search)：使用递归方法进行深度优先搜索（DFS）。对于每个字符，检查是否匹配，如果是 .，尝试所有子节点。

复杂度分析

时间复杂度：
- addWord 操作的时间复杂度为 O(L)，其中 L 是单词的长度。
- search 操作的时间复杂度为 O(L * 4^L) 最坏情况下，其中 L 是单词的长度，因为每个 . 可能会展开到最多 4 种情况。
空间复杂度：
- addWord 操作的空间复杂度为 O(L * N)，其中 N 是存储的单词数。
- search 操作的空间复杂度为 O(L) 用于递归调用栈。

代码实现

package org.zyf.javabasic.letcode.jd150.trie;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: zyfboot-javabasic
 * @description: 添加与搜索单词 - 数据结构设计
 * @author: zhangyanfeng
 * @create: 2024-08-25 17:50
 **/
public class WordDictionary {
    private class TrieNode {
        Map<Character, TrieNode> children;
        boolean isEndOfWord;

        TrieNode() {
            children = new HashMap<>();
            isEndOfWord = false;
        }
    }

    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        return searchInTrie(word, 0, root);
    }

    private boolean searchInTrie(String word, int index, TrieNode node) {
        if (index == word.length()) {
            return node.isEndOfWord;
        }

        char c = word.charAt(index);
        if (c == '.') {
            // 对于 '.', 遍历所有子节点
            for (TrieNode child : node.children.values()) {
                if (searchInTrie(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            // 对于普通字符, 只在子节点中查找
            TrieNode child = node.children.get(c);
            if (child == null) {
                return false;
            }
            return searchInTrie(word, index + 1, child);
        }
    }
}

100.单词搜索 II（困难）

题目描述

解题思路

这个问题是经典的单词搜索问题，我们可以通过 Trie（前缀树）结合 DFS（深度优先搜索）来高效解决：

Trie（前缀树）构建：使用 Trie 数据结构存储所有单词，以支持高效的前缀匹配。每个 Trie 节点代表一个字符。将每个单词插入 Trie 中，在单词的最后一个节点处标记该单词。
DFS 搜索：在网格的每个单元格开始进行 DFS 搜索，尝试从当前单元格出发构建单词。通过检查当前单元格的字符是否存在于当前 Trie 节点的子节点中来决定是否继续搜索。使用回溯（将当前单元格的字符恢复为原始字符）来确保每个单元格在搜索过程中只被访问一次。
回溯和标记：在 DFS 搜索过程中，将当前单元格标记为访问过（用特殊字符 '#' 替代原字符），以避免重复使用。搜索完成后，将单元格状态恢复为原始字符。

复杂度分析

时间复杂度：
- 构建 Trie 的时间复杂度为 O(W⋅L))，其中 WWW 是单词的数量，L 是单词的平均长度。
- 在网格上进行 DFS 的时间复杂度为 O(m⋅n⋅4^L)，其中 m 和 n 是网格的行列数，L 是单词的最大长度。每个单元格在 DFS 中最多有 4 个方向进行探索。
空间复杂度：
- Trie 的空间复杂度为 O(W⋅L)。
- DFS 递归栈的空间复杂度为 O(L)，加上网格的访问标记空间 O(m⋅n)。

代码实现

package org.zyf.javabasic.letcode.jd150.trie;

import java.util.*;

/**
 * @program: zyfboot-javabasic
 * @description: 单词搜索 II
 * @author: zhangyanfeng
 * @create: 2024-08-25 17:57
 **/
public class FindWords {
    // 定义四个方向（上下左右）
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();  // 创建 Trie 树
        // 将所有单词插入 Trie 中
        for (String word : words) {
            trie.insert(word);
        }

        Set<String> ans = new HashSet<>();  // 存储结果的集合
        // 遍历网格的每一个单元格，进行 DFS 搜索
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                dfs(board, trie, i, j, ans);
            }
        }

        return new ArrayList<>(ans);  // 返回结果的列表
    }

    // 深度优先搜索函数
    public void dfs(char[][] board, Trie now, int i1, int j1, Set<String> ans) {
        // 如果当前字符不在 Trie 的子节点中，则返回
        if (!now.children.containsKey(board[i1][j1])) {
            return;
        }
        char ch = board[i1][j1];  // 当前字符
        now = now.children.get(ch);  // 移动到子节点

        // 如果当前节点是一个单词的结束点，则将单词添加到结果集中
        if (!"".equals(now.word)) {
            ans.add(now.word);
        }

        // 标记当前单元格为访问过
        board[i1][j1] = '#';

        // 遍历四个方向进行 DFS 搜索
        for (int[] dir : dirs) {
            int i2 = i1 + dir[0], j2 = j1 + dir[1];
            if (i2 >= 0 && i2 < board.length && j2 >= 0 && j2 < board[0].length) {
                dfs(board, now, i2, j2, ans);
            }
        }

        // 恢复单元格状态为原始字符
        board[i1][j1] = ch;
    }

    // Trie（前缀树）实现
    class Trie {
        String word;  // 存储单词
        Map<Character, Trie> children;  // 存储子节点
        boolean isWord;  // 标记是否是单词的结束

        public Trie() {
            this.word = "";
            this.children = new HashMap<>();
        }

        // 将单词插入到 Trie 中
        public void insert(String word) {
            Trie cur = this;
            for (int i = 0; i < word.length(); ++i) {
                char c = word.charAt(i);
                if (!cur.children.containsKey(c)) {
                    cur.children.put(c, new Trie());
                }
                cur = cur.children.get(c);
            }
            cur.word = word;  // 设置单词结束标记
        }
    }
}

十五、回溯

101.电话号码的字母组合（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第57题。

可见LeetCode 精选 75 回顾-CSDN博客中的第57题。

102.组合（中等）

题目描述

解题思路

这个问题要求我们从 [1, n] 范围内的数字中选取 k 个数的所有可能组合。解决这个问题可以使用 回溯法：

选择：从当前数字中选择一个数字加入当前组合。
探索：递归地继续选择下一个数字。
回溯：撤销上一步的选择，并继续尝试其他选择。

具体步骤如下：

初始化：开始时选择从 1 到 n 的数字作为起点。
递归选择：在每一步递归中，从当前数字开始，尝试选择 k 个数字中的下一个数字。
终止条件：当选择的数字数量等于 k 时，保存当前组合。
撤销选择：在回溯时，撤销上一步的选择以尝试其他组合。

复杂度分析

时间复杂度：
- 生成组合的总时间复杂度是 O(C(n, k))，其中 C(n, k) 是组合数，表示从 n 个元素中选择 k 个的组合数。
- 计算组合数 C(n, k) 的公式为 n! / (k! * (n - k)!)。
空间复杂度：
- 递归栈的空间复杂度为 O(k)，因为在最坏情况下，递归深度为 k。
- 存储所有组合的空间复杂度为 O(C(n, k) * k)，因为我们需要存储所有的组合，每个组合的大小为 k。

代码实现

package org.zyf.javabasic.letcode.jd150.blacktracing;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: zyfboot-javabasic
 * @description: 组合
 * @author: zhangyanfeng
 * @create: 2024-08-25 18:04
 **/
public class Combine {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();  // 存储所有组合
        List<Integer> combination = new ArrayList<>();    // 当前组合
        backtrack(result, combination, n, k, 1);  // 从数字1开始递归
        return result;
    }

    // 回溯函数
    private void backtrack(List<List<Integer>> result, List<Integer> combination, int n, int k, int start) {
        // 如果当前组合的大小等于k，添加到结果列表中
        if (combination.size() == k) {
            result.add(new ArrayList<>(combination));  // 添加一份当前组合的副本
            return;
        }

        // 从start开始尝试选择每个数字
        for (int i = start; i <= n; i++) {
            combination.add(i);  // 选择当前数字
            backtrack(result, combination, n, k, i + 1);  // 递归选择下一个数字
            combination.remove(combination.size() - 1);  // 撤销选择，回溯
        }
    }
}

103.全排列（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第55题。

104.组合总和（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第58题。

105.N 皇后 II（困难）

题目描述

解题思路

n 皇后问题的目标是将 n 个皇后放置在一个 n x n 的棋盘上，确保没有任何两个皇后在同一行、同一列或同一对角线上。每个皇后都可以攻击棋盘上与它处于同一行、列或对角线上的其他皇后。

要解决这个问题，我们可以使用 回溯法（Backtracking），这种方法通过逐步构建解，并在发现不满足条件时进行撤销，来逐步寻找所有可能的解。回溯法步骤

选择：逐行放置皇后，并在每一行中尝试放置皇后的位置。
约束：在尝试放置皇后时，确保它不与已放置的皇后冲突。
递归：对每一个合法的位置递归地放置下一个皇后。
回溯：当所有行都尝试完毕，或者发现当前放置导致冲突时，撤销当前选择，回到上一步继续尝试其他选择。

复杂度分析

时间复杂度：在最坏情况下，时间复杂度为 O(N!)，因为对于每一行，可能需要尝试 N 个位置，并且最多有 N! 种放置方案。
空间复杂度：主要包括递归栈的深度，递归深度为 O(N)，以及用于存储解决方案的空间，最多有 O(N!) 种解决方案。

代码实现

package org.zyf.javabasic.letcode.jd150.blacktracing;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: zyfboot-javabasic
 * @description: N 皇后 II
 * @author: zhangyanfeng
 * @create: 2024-08-25 18:11
 **/
public class TotalNQueens {
    public int totalNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>(); // 存储所有解决方案
        backtrack(solutions, new ArrayList<>(), n, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1], 0);
        return solutions.size(); // 返回解决方案的数量
    }

    private void backtrack(List<List<String>> solutions, List<String> board, int n, boolean[] cols, boolean[] diag1, boolean[] diag2, int row) {
        // 递归终止条件：如果所有行都被处理完毕
        if (row == n) {
            solutions.add(new ArrayList<>(board)); // 记录当前有效的解决方案
            return;
        }

        // 尝试在当前行的每一列放置皇后
        for (int col = 0; col < n; col++) {
            int d1 = row - col + (n - 1); // 主要对角线索引
            int d2 = row + col;           // 副对角线索引

            // 检查当前位置是否安全
            if (!cols[col] && !diag1[d1] && !diag2[d2]) {
                char[] rowArray = new char[n];
                for (int i = 0; i < n; i++) {
                    rowArray[i] = '.'; // 初始化当前行
                }
                rowArray[col] = 'Q'; // 放置皇后
                board.add(new String(rowArray)); // 记录当前行的字符串形式

                // 标记当前位置为占用
                cols[col] = true;
                diag1[d1] = true;
                diag2[d2] = true;

                // 递归处理下一行
                backtrack(solutions, board, n, cols, diag1, diag2, row + 1);

                // 撤销当前选择
                board.remove(board.size() - 1);
                cols[col] = false;
                diag1[d1] = false;
                diag2[d2] = false;
            }
        }
    }
}

106.括号生成（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第59题。

107.单词搜索（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第60题。

十六、分治

108.将有序数组转换为二叉搜索树（简单）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第42题。

109.排序链表（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第33题。

110.建立四叉树（中等）

题目描述

解题思路

要将一个 n x n 的矩阵转换为四叉树（QuadTree），四叉树是一种用于表示二维空间的树形结构，其中每个节点代表一个矩形区域。具体到这个问题：

检查当前矩形区域：
如果当前区域内所有的值都相同，则该区域可以直接作为一个叶子节点（isLeaf 为 True），并将值（val）设置为这个区域的值。如果当前区域内的值不同，则需要将其划分为四个子区域，分别递归处理每个子区域。
递归构建四叉树：
将当前矩形区域分成四个子区域：topLeft, topRight, bottomLeft, bottomRight。对每个子区域递归调用构建四叉树的过程。当递归处理完四个子区域后，将它们作为当前节点的四个子节点。

复杂度分析

时间复杂度：最坏情况下，每个节点都需要将整个区域划分为四个子区域。这种情况下，总体复杂度是 O(N^2)，其中 N 是矩阵的边长，因为每个节点的处理和递归需要 O(N^2) 时间。
空间复杂度：递归调用栈的深度最大为 O(log(N))。空间复杂度主要由树的节点数量和递归栈深度决定，总体复杂度是 O(N^2)。

代码实现

package org.zyf.javabasic.letcode.jd150.tree;

/**
 * @program: zyfboot-javabasic
 * @description: 建立四叉树
 * @author: zhangyanfeng
 * @create: 2024-08-25 18:23
 **/
public class BuildQuadTree {
    public Node construct(int[][] grid) {
        return buildQuadTree(grid, 0, 0, grid.length);
    }

    private Node buildQuadTree(int[][] grid, int row, int col, int size) {
        // 创建当前节点
        Node node = new Node();

        // 检查当前区域是否为一个叶子节点
        if (isUniform(grid, row, col, size)) {
            node.isLeaf = true;
            node.val = grid[row][col] == 1;
            return node;
        }

        // 当前区域不是一个叶子节点，分为四个子区域
        node.isLeaf = false;
        int halfSize = size / 2;
        node.topLeft = buildQuadTree(grid, row, col, halfSize);
        node.topRight = buildQuadTree(grid, row, col + halfSize, halfSize);
        node.bottomLeft = buildQuadTree(grid, row + halfSize, col, halfSize);
        node.bottomRight = buildQuadTree(grid, row + halfSize, col + halfSize, halfSize);

        return node;
    }

    private boolean isUniform(int[][] grid, int row, int col, int size) {
        int firstValue = grid[row][col];
        for (int r = row; r < row + size; r++) {
            for (int c = col; c < col + size; c++) {
                if (grid[r][c] != firstValue) {
                    return false;
                }
            }
        }
        return true;
    }

    class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;

        public Node() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }
    }
}

111.合并 K 个升序链表（困难）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第34题。

十七、Kadane 算法

112.最大子数组和（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第13题。

113.环形子数组的最大和

题目描述

解题思路

为了解决环形数组的最大子数组和问题，我们可以通过以下步骤来处理：

非环形数组的最大子数组和：使用 Kadane 算法计算非环形数组的最大子数组和。这是因为 Kadane 算法可以在 O(n)O(n)O(n) 时间复杂度内找到最大和的子数组。
环形数组的最大子数组和：要找到环形数组的最大子数组和，我们可以考虑两种情况：
- 不包括环形部分：这就是普通的最大子数组和，已经在第一步中求出。
- 包括环形部分：可以通过以下步骤计算：计算整个数组的总和 totalSum。使用 Kadane 算法计算数组的最小子数组和 minSum。最大环形子数组和 = totalSum - minSum。这是因为要包括整个数组的环形部分，我们可以从 totalSum 减去数组的最小子数组和得到环形部分的最大和。
特殊情况处理：
如果整个数组只有一个元素，则最大和只能是该元素本身。如果所有元素都是负数，那么环形和不应该考虑，因为环形和会减去最小子数组和，而这是不需要的。

复杂度分析

时间复杂度：O(n)，因为每个步骤（Kadane 算法，计算总和，计算最小子数组和）都需要 O(n) 时间。
空间复杂度：O(1)，只使用了常量级的额外空间。

代码实现

package org.zyf.javabasic.letcode.jd150.kadane;

/**
 * @program: zyfboot-javabasic
 * @description: 环形子数组的最大和
 * @author: zhangyanfeng
 * @create: 2024-08-25 18:29
 **/
public class MaxSubarraySumCircular {
    public int maxSubarraySumCircular(int[] nums) {
        // 计算数组的总和
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        // 求普通最大子数组和
        int maxSum = kadane(nums, true);

        // 求最小子数组和
        int minSum = kadane(nums, false);

        // 最大环形子数组和
        int maxCircularSum = totalSum - minSum;

        // 如果数组中所有元素都为负数，则 maxCircularSum 会是 0，这种情况需要特殊处理
        if (maxCircularSum == 0) {
            return maxSum;
        }

        // 返回最大值
        return Math.max(maxSum, maxCircularSum);
    }

    // Kadane 算法变种，用于计算最大子数组和或最小子数组和
    private int kadane(int[] nums, boolean findMax) {
        int currentSum = nums[0];
        int extremumSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (findMax) {
                currentSum = Math.max(nums[i], currentSum + nums[i]);
                extremumSum = Math.max(extremumSum, currentSum);
            } else {
                currentSum = Math.min(nums[i], currentSum + nums[i]);
                extremumSum = Math.min(extremumSum, currentSum);
            }
        }

        return extremumSum;
    }
}

十八、二分查找

114.搜索插入位置（简单）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第63题。

115.搜索二维矩阵（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第65题。

116.寻找峰值（中等）

题目描述

解题思路

可见图论总结与编程练习_编程图论-CSDN博客中的第55题。

117.搜索旋转排序数组（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第66题。

118.在排序数组中查找元素的第一个和最后一个位置（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第65题。

119.寻找旋转排序数组中的最小值（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第67题。

120.寻找两个正序数组的中位数（困难）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第68题。

十九、堆

121.数组中的第K个最大元素（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第74题。

122.IPO（困难）

题目描述

解题思路

这个问题涉及到选择最多 k 个项目，使得最终资本最大化。由于项目有启动资本限制，我们需要在每个阶段选择当前资本 w 能够支持的、利润最高的项目。这就需要一种策略来动态选择项目。

项目按所需资本排序：首先，我们将所有项目按照所需的资本 capital[i] 进行排序。这样我们可以按顺序考虑可以启动的项目。
优先选择高利润项目：为了在每次选择项目时获得最大的利润，我们可以使用一个最大堆（大根堆）来存储当前资本范围内可启动项目的利润。
迭代选择项目：
初始化时，首先将当前资本 w 能够启动的所有项目的利润放入最大堆中。然后从堆中选出利润最高的项目，更新资本 w，并继续从剩余项目中添加能够启动的项目到堆中，重复 k 次或直到没有更多项目可以选择。

复杂度分析

时间复杂度：项目排序的时间复杂度为 O(nlog⁡n)O(n \log n)O(nlogn)，每次从堆中选取项目并插入新项目的时间复杂度为 O(log⁡n)O(\log n)O(logn)，最多执行 k 次，因此整体时间复杂度为 O(nlog⁡n+klog⁡n)O(n \log n + k \log n)O(nlogn+klogn)。
空间复杂度：由于需要使用堆存储项目的利润，空间复杂度为 O(n)O(n)O(n)。

代码实现

package org.zyf.javabasic.letcode.jd150.heap;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @program: zyfboot-javabasic
 * @description: IPO
 * @author: zhangyanfeng
 * @create: 2024-08-25 18:43
 **/
public class MaximizedCapital {
    // 主方法，用于计算在选择最多 k 个项目后可以获得的最大资本
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        // 项目数
        int n = profits.length;

        // 项目列表（每个项目包括资本需求和利润）
        int[][] projects = new int[n][2];
        for (int i = 0; i < n; i++) {
            projects[i][0] = capital[i];  // 资本需求
            projects[i][1] = profits[i];  // 利润
        }

        // 按资本需求升序排序
        Arrays.sort(projects, Comparator.comparingInt(a -> a[0]));

        // 最大堆，用于存储当前资本 w 能够启动的项目利润
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        int index = 0;  // 用于遍历项目
        // 选择最多 k 个项目
        for (int i = 0; i < k; i++) {
            // 将所有当前资本 w 能启动的项目的利润加入堆中
            while (index < n && projects[index][0] <= w) {
                maxHeap.offer(projects[index][1]);
                index++;
            }

            // 如果堆中有可选项目，选择利润最大的项目
            if (!maxHeap.isEmpty()) {
                w += maxHeap.poll();  // 更新资本
            } else {
                break;  // 如果没有更多可选项目，直接结束
            }
        }

        return w;  // 返回最终的资本
    }

    // 测试代码
    public static void main(String[] args) {
        MaximizedCapital solution = new MaximizedCapital();
        int k = 2, w = 0;
        int[] profits = {1, 2, 3};
        int[] capital = {0, 1, 1};

        int result = solution.findMaximizedCapital(k, w, profits, capital);
        System.out.println(result);  // 输出应为 4
    }
}

123.查找和最小的 K 对数字（中等）

题目描述

解题思路

题目要求在两个有序数组 nums1 和 nums2 中找到和最小的 k 对数对 (u,v)。由于两个数组是有序的，因此可以利用最小堆（优先队列）来高效地找到这些数对。

初始堆构建：将所有可能的数对中的前 k 对数对放入最小堆中。具体来说，可以只考虑 nums1 中前 k 个元素与 nums2 第一个元素的配对 (nums1[i], nums2[0]) 放入堆中，因为这些是可能的最小组合。
堆操作：每次从堆中取出最小的数对 (nums1[i], nums2[j])，然后将其后继组合 (nums1[i], nums2[j+1]) 入堆。这样可以确保找到最小的 k 个数对。
终止条件：堆中取出 k 个元素后停止，或者堆为空时停止。

复杂度分析

时间复杂度：初始堆的构建需要 O(k log k) 时间，而每次堆操作的插入和删除都是 O(log k)。由于我们最多需要进行 k 次这样的操作，所以总时间复杂度为 O(k log k)。
空间复杂度：堆的空间复杂度为 O(k)，因此总的空间复杂度为 O(k)。

代码实现

package org.zyf.javabasic.letcode.jd150.heap;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @program: zyfboot-javabasic
 * @description: 查找和最小的K对数字
 * @author: zhangyanfeng
 * @create: 2024-08-25 18:47
 **/
public class KSmallestPairs {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        // 最小堆，用于存储数对的索引 [i, j]
        PriorityQueue<int[]> pq = new PriorityQueue<>(k, (o1, o2) -> {
            return nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]];
        });

        // 结果列表
        List<List<Integer>> ans = new ArrayList<>();
        int m = nums1.length;
        int n = nums2.length;

        // 初始化堆，放入 nums1 的前 k 个元素与 nums2 第一个元素的组合
        for (int i = 0; i < Math.min(m, k); i++) {
            pq.offer(new int[]{i, 0});
        }

        // 取出最小的 k 个数对
        while (k-- > 0 && !pq.isEmpty()) {
            int[] idxPair = pq.poll();  // 取出最小和的数对索引
            List<Integer> list = new ArrayList<>();
            list.add(nums1[idxPair[0]]);
            list.add(nums2[idxPair[1]]);
            ans.add(list);

            // 若 j + 1 还在数组范围内，继续将 (i, j+1) 放入堆中
            if (idxPair[1] + 1 < n) {
                pq.offer(new int[]{idxPair[0], idxPair[1] + 1});
            }
        }

        return ans;
    }
}

124.数据流的中位数（困难）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第76题。

二十、位运算

125.二进制求和（简单）

题目描述

解题思路

我们要对两个二进制字符串 a 和 b 进行逐位相加，并且考虑进位的问题。由于二进制只有 0 和 1，逻辑相对简单。我们从两个字符串的最低位（末尾）开始逐位相加，如果某一位的和大于等于 2，则产生一个进位。继续处理更高位，直到处理完所有位或者处理完进位。解题步骤:

初始化指针和进位：使用两个指针 i 和 j 分别指向字符串 a 和 b 的末尾。初始化进位 carry 为 0。初始化结果字符串 StringBuilder result。
逐位相加：从 i 和 j 逐位向前遍历，计算当前位的和，并考虑前一次的进位 carry。根据当前位的和，决定是否有新的进位，并将结果的当前位存储到 result 中。
处理剩余的进位：如果遍历完成后仍有进位，则将进位加到结果中。
返回结果：由于 result 是从低位开始构建的，最终需要将其反转后返回。

复杂度分析

时间复杂度：O(max(m, n))，其中 m 和 n 分别是字符串 a 和 b 的长度。我们最多需要遍历较长的字符串。
空间复杂度：O(max(m, n))，用于存储结果字符串的空间。

代码实现

package org.zyf.javabasic.letcode.jd150.binary;

/**
 * @program: zyfboot-javabasic
 * @description: 二进制求和
 * @author: zhangyanfeng
 * @create: 2024-08-25 18:54
 **/
public class AddBinary {
    public String addBinary(String a, String b) {
        // 使用 StringBuilder 来存储结果
        StringBuilder result = new StringBuilder();
        // 初始化指针 i 和 j 分别指向 a 和 b 的末尾
        int i = a.length() - 1;
        int j = b.length() - 1;
        // 初始化进位 carry
        int carry = 0;

        // 遍历 a 和 b
        while (i >= 0 || j >= 0) {
            // 获取当前位的值，如果指针已经超出字符串范围，则认为当前位为 0
            int bitA = (i >= 0) ? a.charAt(i) - '0' : 0;
            int bitB = (j >= 0) ? b.charAt(j) - '0' : 0;
            // 计算当前位的和（包括进位）
            int sum = bitA + bitB + carry;
            // 计算新的进位（如果 sum >= 2 则有进位）
            carry = sum / 2;
            // 将 sum 的余数添加到结果中
            result.append(sum % 2);
            // 指针向前移动
            i--;
            j--;
        }

        // 如果遍历结束后仍有进位，则需要添加到结果中
        if (carry != 0) {
            result.append(carry);
        }

        // 最终需要将结果反转并返回
        return result.reverse().toString();
    }
}

126.颠倒二进制位（简单）

题目描述

解题思路

我们要颠倒一个32位无符号整数的二进制位，这意味着将最左边的位与最右边的位交换，依次向中间靠拢，直到完成整个二进制串的反转。可以使用位运算来完成这个任务。具体步骤如下：

初始化结果：初始化一个变量 result，用于存储最终的反转结果。
逐位反转：
我们将输入整数 n 的每一位取出，并将其加入到 result 的相应位置。具体来说，将 n 右移一位，并将 n 的最低位（取出）加入到 result 的最高位（通过左移操作）。重复这一过程32次。
返回结果：返回 result 即可得到反转后的二进制整数。

复杂度分析

时间复杂度：O(1)。虽然我们需要循环32次，但由于32是常数，因此时间复杂度为O(1)。
空间复杂度：O(1)。仅使用了几个额外的变量来存储中间结果和最终结果，空间复杂度为O(1)。

代码实现

package org.zyf.javabasic.letcode.jd150.binary;

/**
 * @program: zyfboot-javabasic
 * @description: 颠倒二进制位
 * @author: zhangyanfeng
 * @create: 2024-08-25 18:57
 **/
public class ReverseBits {
    // 颠倒32位无符号整数的二进制位
    public int reverseBits(int n) {
        // 初始化结果为0
        int result = 0;

        // 遍历32位
        for (int i = 0; i < 32; i++) {
            // 将result左移1位，为下一个反转位腾出空间
            result <<= 1;
            // 将n的最低位加到result的最低位
            result |= (n & 1);
            // 将n右移1位，处理下一个位
            n >>= 1;
        }

        // 返回反转后的结果
        return result;
    }
}

127.位1的个数（简单）

题目描述

解题思路

可见数学思维编程练习总结_编程中的数学思维-CSDN博客中的第11题。

可见剑指offer所有编程练习总结分析_currentsum -= small++-CSDN博客中的第36题。

128.只出现一次的数字（简单）

题目描述

解题思路

可见LeetCode 精选 75 回顾-CSDN博客中的第68题。

129.只出现一次的数字 II（中等）

题目描述

解题思路

对于一个整数，如果我们考虑它的每一位（0或1），那么对于出现了三次的元素来说，某一位上的1出现的次数必然是3的倍数。而对于仅出现一次的元素来说，其某些位上的1不会是3的倍数。因此，我们可以通过统计数组中每一位上1出现的次数，并对3取模，结果就是仅出现一次的元素在该位上的值。具体步骤

初始化两个变量 ones 和 twos 用于记录位的状态。其中：
ones 表示在当前位出现了1次的数。twos 表示在当前位出现了2次的数。
对数组中的每个数进行如下操作：更新 ones 和 twos 的值，考虑当前位是否被当前数占用。
最终，ones 的值即为仅出现一次的元素。

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。我们仅需遍历数组一次。
空间复杂度：O(1)，只使用了常数个额外变量。

代码实现

package org.zyf.javabasic.letcode.jd150.binary;

/**
 * @program: zyfboot-javabasic
 * @description: 只出现一次的数字 II
 * @author: zhangyanfeng
 * @create: 2024-08-25 19:05
 **/
public class SingleNumber {
    public int singleNumber(int[] nums) {
        // ones记录出现1次的位，twos记录出现2次的位
        int ones = 0, twos = 0;
        for (int num : nums) {
            // 更新ones，twos的值
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        // 返回ones，表示那个只出现一次的数
        return ones;
    }
}

130.数字范围按位与（中等）

题目描述

解题思路

对于给定的区间 [left,right]，要求返回区间内所有数字的按位与的结果。按位与操作的特性决定了，如果区间范围较大，那么结果将会受到范围内的低位影响。我们可以通过找到 left 和 right 的公共前缀，来减少计算的复杂度。

关键观察：如果我们对连续的数字进行按位与操作，那么每次操作可能都会清除低位上的1。最终结果取决于 left 和 right 在高位的公共前缀。
具体做法：将 left 和 right 一直右移，直到它们相等。记录右移的次数 shift，最终将相等的值左移回原位置，即为结果。

具体步骤

初始化 shift 为0，用来记录右移的次数。
不断右移 left 和 right，直到 left == right。
将最终相等的 left 左移 shift 次，即为最终结果。

复杂度分析

时间复杂度：O(log⁡(right))，因为我们在计算过程中将数字右移，最多右移 O(log⁡(right))次。
空间复杂度：O(1)，只使用了常数个额外变量。

代码实现

package org.zyf.javabasic.letcode.jd150.binary;

/**
 * @program: zyfboot-javabasic
 * @description: 数字范围按位与
 * @author: zhangyanfeng
 * @create: 2024-08-25 19:11
 **/
public class RangeBitwiseAnd {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        // 不断右移left和right，直到它们相等
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        // 将相等的left左移回原位置
        return left << shift;
    }
}

二十一、数学

131.回文数（简单）

题目描述

解题思路

具体可见数学思维编程练习总结_编程中的数学思维-CSDN博客中的第6题。

132.加一（简单）

题目描述

解题思路

具体可见数组知识及编程练习总结-CSDN博客中的第8题。

133. 阶乘后的零（中等）

解题思路

具体可见数学思维编程练习总结_编程中的数学思维-CSDN博客中的第20题。

134.x 的平方根（中等）

题目描述

解题思路

具体可见数学思维编程练习总结_编程中的数学思维-CSDN博客中的第22题。

135.Pow(x, n)（中等）

题目描述

解题思路

具体可见数学思维编程练习总结_编程中的数学思维-CSDN博客中的第23题。

136.直线上最多的点数（困难）

题目描述

解题思路

要找出在同一条直线上的最多点数，可以利用斜率的概念。具体思路如下：

固定一个点作为基准点：对于每个点 i，计算它与其他点 j（j ≠ i）之间的斜率。斜率相同的点必然在同一条直线上。
使用哈希表统计斜率：用一个哈希表来记录当前基准点 i 与其他点 j 之间的斜率出现的次数。相同斜率的点数越多，说明这些点与基准点在同一条直线上。
特殊情况处理：
重合点：如果两个点坐标完全相同，需要单独计数。垂直线：当两点的 x 坐标相同，斜率为无穷大，此时用特定值来表示这种情况。
最大点数计算：对于每个基准点，找到斜率最多的那一组点，加上基准点本身以及任何重合的点数，就可以得到以该点为基准的最大点数。最终的结果是所有基准点下的最大值。

复杂度分析

时间复杂度：O(n^2)，其中 n 是点的数量。每个点作为基准点时都要计算与其他 n-1 个点的斜率。
空间复杂度：O(n)，用于存储斜率的哈希表。

代码实现

package org.zyf.javabasic.letcode.jd150.binary;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: zyfboot-javabasic
 * @description: 直线上最多的点数
 * @author: zhangyanfeng
 * @create: 2024-08-25 19:43
 **/
public class MaxPoints {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n < 3) return n;

        int maxPointsOnLine = 1;

        for (int i = 0; i < n; i++) {
            Map<String, Integer> slopeMap = new HashMap<>();
            int duplicate = 0; // 记录与基准点重合的点数
            int maxForCurrentPoint = 0;

            for (int j = i + 1; j < n; j++) {
                int deltaX = points[j][0] - points[i][0];
                int deltaY = points[j][1] - points[i][1];

                if (deltaX == 0 && deltaY == 0) {
                    // 基准点与某点重合
                    duplicate++;
                    continue;
                }

                // 化简分数形式的斜率
                int gcd = gcd(deltaX, deltaY);
                deltaX /= gcd;
                deltaY /= gcd;

                // 确保斜率的唯一性（处理垂直和水平的情况）
                String slope = deltaX + "/" + deltaY;
                slopeMap.put(slope, slopeMap.getOrDefault(slope, 0) + 1);
                maxForCurrentPoint = Math.max(maxForCurrentPoint, slopeMap.get(slope));
            }

            // 计算基于当前基准点的最大点数
            maxPointsOnLine = Math.max(maxPointsOnLine, maxForCurrentPoint + duplicate + 1);
        }

        return maxPointsOnLine;
    }

    // 计算最大公约数
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

二十二、一维动态规划

137.爬楼梯（简单）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第81题。

138.打家劫舍（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第83题。

139.单词拆分（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第86题。

140.零钱兑换（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第85题。

141.最长递增子序列（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第87题。

二十三、多维动态规划

142.三角形最小路径和（中等）

题目描述

解题思路

要解决三角形最小路径和的问题，可以采用动态规划（Dynamic Programming）的方法。该方法能够有效地在三角形结构中计算自顶向下的最小路径和。

自底向上动态规划：
我们可以从三角形的底部开始，逐行向上计算每个元素的最小路径和。对于每个元素 triangle[i][j]，其最小路径和可以通过其下一行的两个相邻元素 triangle[i+1][j] 和 triangle[i+1][j+1] 的最小值来确定。状态转移方程：dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])。
空间优化：
我们可以直接在原三角形数组上进行修改，使得最终顶部元素保存的是从顶到底的最小路径和。这样，空间复杂度可以降到 O(n)，其中 n 是三角形的行数。

复杂度分析

时间复杂度：O(n^2)，其中 n 是三角形的行数。我们需要遍历整个三角形的每个元素一次。
空间复杂度：O(1)，我们直接在原数组上进行操作，不需要额外的空间。

代码实现

package org.zyf.javabasic.letcode.jd150.dynamic;

import java.util.List;

/**
 * @program: zyfboot-javabasic
 * @description: 三角形最小路径和
 * @author: zhangyanfeng
 * @create: 2024-08-25 19:53
 **/
public class MinimumTotal {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();

        // 从倒数第二行开始，自底向上计算最小路径和
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                // 当前元素加上下一行的两个相邻元素的最小值
                triangle.get(i).set(j, triangle.get(i).get(j) +
                        Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
            }
        }

        // 最顶端元素即为最小路径和
        return triangle.get(0).get(0);
    }
}

143.最小路径和（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第92题。

144.不同路径 II（中等）

题目描述

解题思路

要计算从网格的左上角到右下角的所有不同路径数量，考虑网格中可能存在的障碍物，我们可以使用动态规划（Dynamic Programming）来解决这个问题:

动态规划表格：使用一个二维数组 dp，其中 dp[i][j] 表示从 (0,0) 到 (i,j) 的不同路径数量。
初始化：dp[0][0] 初始化为 1，如果起点 (0,0) 处有障碍物，则 dp[0][0] 为 0，因为机器人不能从起点开始。如果网格的第一行或第一列有障碍物，后续的路径数也应该为 0。
状态转移：对于每个位置 (i,j)，如果 obstacleGrid[i][j] 为 0（无障碍物），那么 dp[i][j] 可以由上方 (i-1,j) 或左方 (i,j-1) 位置的路径数得出：dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);如果 obstacleGrid[i][j] 为 1（有障碍物），则 dp[i][j] 为 0。
结果：最终的结果是 dp[m-1][n-1]，即网格右下角的路径数量。

复杂度分析

时间复杂度：O(m * n)，我们需要遍历整个网格。
空间复杂度：O(m * n)，需要额外的二维数组来存储路径数量。

代码实现

package org.zyf.javabasic.letcode.jd150.dynamic;

/**
 * @program: zyfboot-javabasic
 * @description: 不同路径 II
 * @author: zhangyanfeng
 * @create: 2024-08-25 20:00
 **/
public class UniquePathsWithObstacles {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length; // 行数
        int n = obstacleGrid[0].length; // 列数

        // 创建一个二维数组 dp，用于存储从 (0,0) 到 (i,j) 的路径数量
        int[][] dp = new int[m][n];

        // 初始化 dp 数组
        // 如果起点有障碍物，则直接返回 0
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        dp[0][0] = 1; // 起点到起点的路径数为 1

        // 填充第一行
        for (int j = 1; j < n; j++) {
            dp[0][j] = (obstacleGrid[0][j] == 0 && dp[0][j-1] == 1) ? 1 : 0;
        }

        // 填充第一列
        for (int i = 1; i < m; i++) {
            dp[i][0] = (obstacleGrid[i][0] == 0 && dp[i-1][0] == 1) ? 1 : 0;
        }

        // 填充其余的 dp 数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                } else {
                    dp[i][j] = 0; // 如果有障碍物，路径数为 0
                }
            }
        }

        // 返回右下角的路径数量
        return dp[m-1][n-1];
    }
}

145.最长回文子串（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第93题。

146.交错字符串（中等）

题目描述

解题思路

要验证字符串 s3 是否是由 s1 和 s2 交错组成的，可以使用动态规划（Dynamic Programming, DP）来实现。我们将定义一个二维数组 dp 来表示从 s1 和 s2 生成 s3 的可能性。解题思路：

定义状态：使用一个二维布尔数组 dp，其中 dp[i][j] 表示 s3 的前 i + j 个字符是否可以由 s1 的前 i 个字符和 s2 的前 j 个字符交错组成。
初始化：
dp[0][0] = true，因为空字符串可以由两个空字符串交错组成。对于第一行（即 i = 0），dp[0][j] 取决于 s2 是否可以匹配 s3 的前 j 个字符。对于第一列（即 j = 0），dp[i][0] 取决于 s1 是否可以匹配 s3 的前 i 个字符。
状态转移：
对于每个位置 (i, j)，如果 dp[i][j] 为 true，则：如果 j < len(s2) 且 s2[j] 等于 s3[i + j]，则 dp[i][j + 1] 应该为 true。如果 i < len(s1) 且 s1[i] 等于 s3[i + j]，则 dp[i + 1][j] 应该为 true。
结果：最终结果是 dp[len(s1)][len(s2)]，即 s1 和 s2 是否能交错组成 s3。

复杂度分析

时间复杂度：O(m * n)，其中 m 和 n 分别是 s1 和 s2 的长度。需要遍历 dp 数组的每一个位置。
空间复杂度：O(m * n)，需要额外的二维数组 dp 来存储中间结果。

代码实现

package org.zyf.javabasic.letcode.jd150.dynamic;

/**
 * @program: zyfboot-javabasic
 * @description: 交错字符串
 * @author: zhangyanfeng
 * @create: 2024-08-25 20:05
 **/
public class Interleave {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        int l = s3.length();

        // 如果 s1 和 s2 的长度之和不等于 s3 的长度，则不能交错组成 s3
        if (m + n != l) {
            return false;
        }

        // 创建 dp 数组
        boolean[][] dp = new boolean[m + 1][n + 1];

        // 初始化 dp 数组
        dp[0][0] = true;

        // 初始化第一行
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        }

        // 初始化第一列
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }

        // 填充 dp 数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) ||
                        (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }

        // 返回结果
        return dp[m][n];
    }
}

147.编辑距离（中等）

题目描述

解题思路

具体可见LeetCode 热题 100 回顾-CSDN博客中的第95题。

148.买卖股票的最佳时机 III（困难）

题目描述

解题思路

要在数组 prices 中计算最多可以完成两笔交易的最大利润，我们可以使用动态规划来解决这个问题。具体地，我们可以将问题拆分为两个子问题：进行第一次交易和进行第二次交易。

我们定义四个变量：

buy1：第一次购买股票时的最大利润。
sell1：第一次出售股票时的最大利润。
buy2：第二次购买股票时的最大利润。
sell2：第二次出售股票时的最大利润。

动态规划转移方程

LeetCode 面试经典 150 题回顾-LMLPHP

复杂度分析

时间复杂度：O(n)，因为我们只需要遍历一次 prices 数组。
空间复杂度：O(1)，因为我们只使用了常数个额外变量。

代码实现

package org.zyf.javabasic.letcode.jd150.dynamic;

/**
 * @program: zyfboot-javabasic
 * @description: 买卖股票的最佳时机 III
 * @author: zhangyanfeng
 * @create: 2024-08-25 20:11
 **/
public class MaxProfit {
    public int maxProfit(int[] prices) {
        int n = prices.length; // 获取价格数组的长度

        // 初始化动态规划状态变量
        int buy1 = -prices[0], sell1 = 0; // 第一次购买和出售的初始状态
        int buy2 = -prices[0], sell2 = 0; // 第二次购买和出售的初始状态

        // 遍历每一天的价格
        for (int i = 1; i < n; ++i) {
            // 更新第一次购买的最大利润
            buy1 = Math.max(buy1, -prices[i]);
            // 更新第一次出售的最大利润
            sell1 = Math.max(sell1, buy1 + prices[i]);
            // 更新第二次购买的最大利润
            buy2 = Math.max(buy2, sell1 - prices[i]);
            // 更新第二次出售的最大利润
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }

        // 返回最多完成两笔交易的最大利润
        return sell2;
    }
}

149.买卖股票的最佳时机 IV（困难）

题目描述

解题思路

对于这个问题，我们可以使用动态规划来求解。主要思路是构建一个二维动态规划表，其中 dp[t][d] 表示在第 d 天完成 t 次交易的最大利润。

动态规划状态定义

dp[t][d]：在第 d 天完成 t 次交易的最大利润。
dp[t][d] 需要利用前一天的状态和当天的价格来更新。

动态规划转移方程

LeetCode 面试经典 150 题回顾-LMLPHP

复杂度分析

时间复杂度：O(k * n^2)，其中 n 是价格数组的长度。因为我们在每次交易中需要遍历所有之前的价格，导致时间复杂度为 O(n^2)，而总共要处理 k 次交易。
空间复杂度：O(k * n)，因为我们需要一个 k x n 的 DP 表。

代码实现

package org.zyf.javabasic.letcode.jd150.dynamic;

/**
 * @program: zyfboot-javabasic
 * @description: 买卖股票的最佳时机 IV
 * @author: zhangyanfeng
 * @create: 2024-08-25 20:14
 **/
public class MaxProfit2 {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;

        // 如果交易次数 k 大于等于天数的一半，意味着可以进行无限次交易
        if (k >= n / 2) {
            int maxProfit = 0;
            for (int i = 1; i < n; ++i) {
                if (prices[i] > prices[i - 1]) {
                    maxProfit += prices[i] - prices[i - 1];
                }
            }
            return maxProfit;
        }

        // dp[t][d] 表示第 d 天完成 t 次交易的最大利润
        int[][] dp = new int[k + 1][n];

        // 遍历每次交易
        for (int t = 1; t <= k; ++t) {
            // 在第 t 次交易时，初始化最优利润
            int maxDiff = -prices[0];

            // 遍历每一天
            for (int d = 1; d < n; ++d) {
                // 更新 dp[t][d]，考虑不进行交易和进行交易两种情况
                dp[t][d] = Math.max(dp[t][d - 1], prices[d] + maxDiff);
                // 更新 maxDiff，为下一天的交易准备
                maxDiff = Math.max(maxDiff, dp[t - 1][d] - prices[d]);
            }
        }

        // 返回最多完成 k 次交易的最大利润
        return dp[k][n - 1];
    }
}

150.最大正方形（中等）

题目描述

解题思路

LeetCode 面试经典 150 题回顾-LMLPHP

复杂度分析

时间复杂度：O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要遍历每一个矩阵位置一次。
空间复杂度：O(m * n)，需要额外的空间来存储 dp 表。

代码实现

package org.zyf.javabasic.letcode.jd150.dynamic;

/**
 * @program: zyfboot-javabasic
 * @description: 最大正方形
 * @author: zhangyanfeng
 * @create: 2024-08-25 20:18
 **/
public class MaximalSquare {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) return 0;
        int n = matrix[0].length;

        // dp[i][j] 表示以 matrix[i][j] 为右下角的最大正方形的边长
        int[][] dp = new int[m][n];
        int maxSide = 0; // 记录最大正方形的边长

        // 遍历矩阵
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 只有 matrix[i][j] 为 '1' 时才有可能形成正方形
                if (matrix[i][j] == '1') {
                    // 如果在第一行或第一列，dp[i][j] 只能为 1
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        // 更新 dp[i][j] 的值
                        dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    }
                    // 更新最大边长
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }

        // 返回最大正方形的面积
        return maxSide * maxSide;
    }
}

张彦峰ZYF