代码随想录算法训练营第三十一天

LeetCode.56 合并区间

题目链接 合并区间

题解

class Solution { public int[][] merge(int[][] intervals) { List res = new LinkedList(); Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0])); for(int i = 1;i<intervals.length;i++){ if(intervals[i][0] <= intervals[i-1][1]){ intervals[i][0] = intervals[i-1][0]; intervals[i][1] = Math.max(intervals[i-1][1],intervals[i][1]); }else { res.add(intervals[i-1]); } } res.add(intervals[intervals.length - 1]); return res.toArray(new int[res.size()][]); }}

解题思路

这段代码实现了区间合并的功能，用于将重叠的区间合并为一个连续的区间。让我为你解释它的工作原理：

问题描述：给定一个区间的集合，合并所有重叠的区间，并返回合并后的区间集合。

代码采用了排序与贪心结合的策略，具体实现步骤如下：

1. 首先对所有区间按照起始点（start）进行排序
2. 创建一个列表res用于存储合并后的区间
3. 遍历排序后的区间：
   • 如果当前区间的起始点小于等于前一个区间的结束点，说明两个区间重叠
     • 将当前区间的起始点更新为前一个区间的起始点
     • 将当前区间的结束点更新为两个区间结束点的最大值（合并操作）
   • 如果不重叠，则将前一个区间加入结果列表
4. 循环结束后，将最后一个区间加入结果列表
5. 将列表转换为数组并返回

这种方法的时间复杂度是 O (n log n)，主要来自排序操作；空间复杂度是 O (n)，用于存储结果。

例如，对于输入[[1,3],[2,6],[8,10],[15,18]]，代码会将其合并为[[1,6],[8,10],[15,18]]。

这个算法的关键在于：通过排序确保区间按起始点有序，然后通过一次遍历完成合并操作，每次遇到重叠区间就进行合并，不重叠则保存前一个区间。

LeetCode.738 单调递增的数字

题目链接 单调递增的数字

题解

class Solution { public int monotoneIncreasingDigits(int n) { // 处理特殊情况 if (n < 10) { return n; } // 将数字按位拆分，存储到列表（从低位到高位） List list = new ArrayList(); while (n > 0) { list.add(n % 10); n /= 10; } // 转换为数组并反转，变为从高位到低位存储 int[] arr = new int[list.size()]; for (int i = 0; i = 0; i--) { if (arr[i] > arr[i + 1]) { arr[i]--; // 当前位减1 flag = i + 1; // 标记后面的位置都要设为9 } } // 将flag位置及之后的所有位设为9 for (int i = flag; i < arr.length; i++) { arr[i] = 9; } // 重新组合成数字 int res = 0; for (int num : arr) { res = res * 10 + num; } return res; }}

解题思路

这段代码实现了 \"单调递增的数字\" 问题的解决方案，其目标是找到小于或等于给定整数 n 的最大单调递增整数（即每一位数字都大于或等于前一位数字）。

让我为你解释它的工作原理：

代码的核心思路是通过调整数字的每一位来确保其单调递增特性，具体步骤如下：

1. 特殊情况处理：如果输入数字小于 10，直接返回该数字（单个数字本身就是单调递增的）

2. 数字拆分与重组：

   • 将数字按位拆分，先从低位到高位存储到列表
   • 转换为数组并反转，变为从高位到低位存储，便于后续处理

3. 寻找调整位置：

   • 使用 flag 标记需要设为 9 的起始位置，初始值为数组长度
   • 从高位向低位检查（实际是从数组的倒数第二位向前遍历）
   • 当发现当前位大于后一位时，说明违反了单调递增规则：
     • 将当前位减 1
     • 更新 flag 为当前位置的后一位（标记从这里开始后面的数字都要设为 9）

4. 设置为 9：将 flag 位置及之后的所有位都设为 9，这是为了保证得到的数字是最大可能的

5. 重组数字：将处理后的数组重新组合成整数并返回

例如，对于输入 332：

• 拆分后得到数组 [3, 3, 2]
• 检查发现 3 > 2（索引 1 和 2），将索引 1 的 3 减 1 变为 2，设置 flag = 2
• 将 flag 位置及之后设为 9，得到 [3, 2, 9]
• 但继续检查发现 3 > 2（索引 0 和 1），将索引 0 的 3 减 1 变为 2，设置 flag = 1
• 最终数组变为 [2, 9, 9]，组合得到结果 299

这种方法的时间复杂度是 O (d)，其中 d 是数字的位数；空间复杂度也是 O (d)，用于存储拆分后的数字。

LeetCode.968.监控二叉树

该题目了解大概思路 还没解决