【先跳过监控二叉树】
56.合并区间
题目
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start<sub>i</sub>, end<sub>i</sub>] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 10<sup>4</sup>intervals[i].length == 20 <= start<sub>i</sub> <= end<sub>i</sub> <= 10<sup>4</sup>
思路
- 这个题目是合并所有区间
- Carl思路
- 升序排序左边界
- 初始化
- for
- if重叠
- 左边界不变
- 更新最远右边界
- 移除旧区间，为了将重叠的区间合成一个新区间
- 添加新的区间
- else 直接加区间
- if重叠
- 代码
class Solution { public int[][] merge(int[][] intervals) { List<int[]> res=new LinkedList<>(); Arrays.sort(intervals,(o1,o2)->Integer.compare(o1[0],o2[0]));//排序左边界，升序 res.add(intervals[0]);//初始化 for(int i=1;i<intervals.length;i++){ if(intervals[i][0]<=res.getLast()[1]){ int start=res.getLast()[0];//左边界不变 int end=Math.max(intervals[i][1],res.getLast()[1]); res.removeLast();//将两个重叠区间合并成一个新的，首先要移除旧区间 res.add(new int[]{start,end});//添加新的区间 } else{ res.add(intervals[i]);//直接加区间 } } return res.toArray(new int[res.size()][]); //大小为3的二维数组 } }
总结
- 为了避免冲突，新建一个数组负责合并和增加数组
- LinkedList转换为int二维数组，return res.toArray(new int[res.size()][]); //大小为3的二维数组
738.单调递增的数字
题目
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 10 输出: 9
示例 2:
输入: n = 1234 输出: 1234
示例 3:
输入: n = 332 输出: 299
提示:
0 <= n <= 10<sup>9</sup>
思路
- 我的思路
当数组中的最后一个元素<=前一个元素时，将前一个元素赋值为数组中的最后一个元素。
- 思路
- 前一位-1，后一位是范围中最大的值
- 从后往前遍历，不能从前往后遍历
- 伪代码
- 转换整数为字符，用于修改字符
- 遍历for循环，标记需要变换为9的起点
- 变换为9
- 转换字符为整数
- 代码
class Solution { public int monotoneIncreasingDigits(int n) { String s=String.valueOf(n);//数字变字符串 char[] chars=s.toCharArray();//字符串变字符数组，为了修改字符 int flag=s.length(); for(int i=s.length()-2;i>=0;i--){//i-1到0 if(chars[i]>chars[i+1]){ chars[i]--; flag=i+1;//标记变换为9的起点 } } for(int i=flag;i<s.length();i++){ chars[i]='9'; } return Integer.parseInt(String.valueOf(chars)); //String.valueOf(chars)字符→字符串；Integer.parseInt()字符串→整数 } }
总结
- flag为什么要进行初始赋值flag=0？因为输入可能本身已经满足条件了，不进入flag循环中。
- 为什么遇到i-1的值>i的值，要用flag记录下来，而不是直接赋值？
- 反例：1000，走到前面两位10时，如果直接赋值，结果为0900，但是正确输出时999