ftp备份网站,家在深圳龙岗,中国建设购物网站,网站建设汇报材料56. 合并区间 本题也是重叠区间问题#xff0c;如果昨天三道都吸收的话#xff0c;本题就容易理解了。 代码随想录 class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a,b) - Integer.compare(a[0], b[0]));Listint[] result … 56. 合并区间 本题也是重叠区间问题如果昨天三道都吸收的话本题就容易理解了。 代码随想录 class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a,b) - Integer.compare(a[0], b[0]));Listint[] result new ArrayList();for(int i 1; i intervals.length; i){if(intervals[i][0] intervals[i-1][1]){intervals[i][0] Math.min(intervals[i][0], intervals[i-1][0]);intervals[i][1] Math.max(intervals[i][1], intervals[i-1][1]);}else{result.add(new int[]{intervals[i-1][0], intervals[i-1][1]}); }}result.add(new int[]{intervals[intervals.length-1][0], intervals[intervals.length-1][1]}); return result.toArray(new int[0][]);}
} 总结 1.本题的套路还是判断重叠区间问题。和射气球是一样的套路只是判断条件和判断后的更新操作有所不同。 2.还是一样的套路我们先对左边界进行排序让所有的相邻区间尽可能的重叠在一起。如果intervals[i][0] intervals[i-1][1]说明当前段的边界和上一个边界有重叠然后对当前边界进行跟新需要更新当前边界的左边取最小值然后更新当前边界的右边取最大值。如果判断没有重叠就把上一段区间加入到集合里面。注意for循环之后其实最后一段区间是没有加入到集合里面的我们需要在for循环之后单独把最后一段区间加入到集合里面。最后把集合result.toArray(new int[0][])转为二维数组。 738.单调递增的数字 代码随想录 class Solution {public int monotoneIncreasingDigits(int n) {//一开始不知道怎么处理整数的每一位其实转为字符串或者字符数组处理就可以了String num String.valueOf(n);char[] chars num.toCharArray();int flag chars.length;for(int i chars.length - 1; i 0; i--){if(chars[i] chars[i-1]){chars[i-1]--;flag i;}}for(int i flag; i chars.length; i){chars[i] 9;}return Integer.parseInt(new String(chars));}
} 总结 1.这道题只需要想明白我们要遵循的处理逻辑就可以。就是如果碰到前一位的数字比当前位高那我们就把前一位数字减1当前数字应该变成9。想明白这个就好做了。然后还有一个难点就是应该前序遍历还是后序遍历这种情况可以自己模拟一下对于这道题应该是后序遍历因为后序遍历可以利用到前一次处理的结果。最后一个难点就是我们不应该是直接把当前数字变成9而是设置一个flag让flag后面的数字全变成9这是为了防止1000这种情况如果不使用flag就是900而不是999。还有flag的初始不能为0因为如果碰到1234这种就不需要处理flag所以我们应该初始为 int flag chars.length; 2.一开始不知道怎么处理整数的每一位其实转为字符串或者字符数组处理就可以了后面再通过Integer.parseInt()转为int类型。然后基本数据类型是没有toString方法的。 3.这道题关键是想到个例怎么处理还要考虑遍历顺序只有从后向前遍历才能重复利用上次比较的结果。最后想到使用flag来标记从哪里开始赋值9。 968.监控二叉树 可跳过 本题是贪心和二叉树的一个结合比较难一刷大家就跳过吧。 代码随想录 总结 总结 可以看看贪心算法的总结贪心本来就没啥规律能写出个总结篇真的不容易了。 代码随想录
