代码随想录算法训练营第三十一天| 56. 合并区间 、738.单调递增的数字 。c++转java

56. 合并区间

class Solution {public int[][] merge(int[][] intervals) {//对区间按照右边界排序Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));List<int[]> p = new LinkedList<>();int l = intervals[0][0],r = intervals[0][1];for(int i = 1;i < intervals.length;i++){// 合并区间if(intervals[i][0] <= r){r = Math.max(r,intervals[i][1]);}else{// 添加区间p.add(new int[]{l,r});//定义新的区间的边界l = intervals[i][0];r = intervals[i][1];}}//处理最后一个区间p.add(new int[]{l,r});return p.toArray(new int[p.size()][]);}
}

738.单调递增的数字

思路：只想到了一个暴力，还超时了~，这里的思路很巧妙，大概意思就是找最高位不符合数字递增的地方，然后把后面的位都变成最大值9，此时，我们找最高位就涉及到一个遍历顺序的问题，如果从头开始遍历，比如332，我们找到第二位是不符合条件的，3<2的，所以此时要将3-1，2->9,可是这样遍历得到的是329还是不符合题目要求，所以只能从后面开始遍历。详细解释看这里：代码随想录

class Solution {public int monotoneIncreasingDigits(int n) {// 将n转为char[]String s = String.valueOf(n);char[] ch = s.toCharArray();int start = s.length();for(int i = s.length() - 2; i >= 0;i--){if(ch[i] > ch[i + 1]){ch[i] -= 1;start = i + 1;}}for(int i = start;i < s.length();i++){ch[i] = '9';}return Integer.parseInt(String.valueOf(ch));}}