当前位置：首页 > news >正文

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

news 2025/7/26 8:58:49

LeetCode.56 合并区间

题目链接合并区间

题解

class Solution {public int[][] merge(int[][] intervals) {List<int[]> 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()][]);}
}

解题思路

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

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

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

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

这种方法的时间复杂度是 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<Integer> list = new ArrayList<>();while (n > 0) {list.add(n % 10);n /= 10;}// 转换为数组并反转，变为从高位到低位存储int[] arr = new int[list.size()];for (int i = 0; i < list.size(); i++) {arr[list.size() - 1 - i] = list.get(i);}int flag = arr.length; // 标记需要设为9的起始位置// 从高位向低位检查for (int i = arr.length - 2; i >= 0; i--) {if (arr[i] > arr[i + 1]) {arr[i]--; // 当前位减1flag = i + 1; // 标记后面的位置都要设为9}}// 将flag位置及之后的所有位设为9for (int i = flag; i < arr.length; i++) {arr[i] = 9;}// 重新组合成数字int res = 0;for (int num : arr) {res = res * 10 + num;}return res;}
}

解题思路

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

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

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

特殊情况处理：如果输入数字小于 10，直接返回该数字（单个数字本身就是单调递增的）
数字拆分与重组：
- 将数字按位拆分，先从低位到高位存储到列表
- 转换为数组并反转，变为从高位到低位存储，便于后续处理
寻找调整位置：
- 使用 flag 标记需要设为 9 的起始位置，初始值为数组长度
- 从高位向低位检查（实际是从数组的倒数第二位向前遍历）
- 当发现当前位大于后一位时，说明违反了单调递增规则：
  - 将当前位减 1
  - 更新 flag 为当前位置的后一位（标记从这里开始后面的数字都要设为 9）
设置为 9：将 flag 位置及之后的所有位都设为 9，这是为了保证得到的数字是最大可能的
重组数字：将处理后的数组重新组合成整数并返回