56. 合并区间
题目链接:56. 合并区间
文档讲解:代码随想录
状态:无语,这题从右边界排序做不了!
思路:
- 排序:按照区间的起始位置进行排序,这样后面处理时可以顺序合并重叠区间。
- 合并:从第一个区间开始,依次检查每个区间是否与前一个区间重叠。
- 如果重叠,就更新前一个区间的结束位置为当前区间的结束位置的最大值。
- 如果不重叠,就将前一个区间加入结果列表,并更新当前区间为新的待合并区间。
- 收尾:遍历完所有区间后,将最后一个待合并的区间加入结果列表。
题解:
public int[][] merge(int[][] intervals) {if (intervals.length <= 1) {return intervals;}// 按照区间的起始位置进行升序排序Arrays.sort(intervals, (a, b) -> a[0] - b[0]);List<int[]> list = new ArrayList<>();int[] pre = intervals[0];for (int i = 1; i < intervals.length; i++) {int[] cur = intervals[i];// 如果当前区间的起始位置小于等于前一个区间的结束位置,合并区间if (cur[0] <= pre[1]) {pre[1] = Math.max(cur[1], pre[1]); // 更新合并后的结束位置} else {list.add(pre); // 将前一个合并后的区间加入结果列表pre = cur; // 更新为当前区间,准备合并下一个区间}}list.add(pre); // 添加最后一个合并后的区间// 将结果转换为二维数组并返回return list.toArray(new int[list.size()][]);}
738.单调递增的数字
题目链接:738.单调递增的数字
文档讲解:代码随想录
状态:做出来了,但是比较费力。。。
思路:通过从后向前遍历整数的每一位,检查是否需要调整前一位来保持递增性,然后将需要调整的位置后的所有位数设为 ‘9’,最终返回调整后的整数值。
题解:
public int monotoneIncreasingDigits(int n) {char[] chars = String.valueOf(n).toCharArray(); // 将整数 n 转换为字符数组int index = chars.length; // 初始化索引为字符数组的长度for (int i = chars.length - 1; i > 0; i--) { // 从倒数第二位开始向前遍历字符数组if (chars[i - 1] > chars[i]) { // 如果前一位大于当前位chars[i - 1]--; // 将前一位减 1index = i; // 更新索引为当前位置
// 不能使用chars[i] = '9',如100,就会出现90,正确答案是99}}for (int i = index; i < chars.length; i++) { // 从索引位置开始向后遍历字符数组chars[i] = '9'; // 将后面的所有位数设为 9}String s = String.valueOf(chars); // 将字符数组转换为字符串return Integer.parseInt(s); // 将字符串转换为整数并返回}
968.监控二叉树
题目链接:968.监控二叉树
文档讲解:代码随想录
状态:留着二刷