一、56. 合并区间
题目链接：https://leetcode.cn/problems/merge-intervals/
文章讲解：https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html
视频讲解：https://www.bilibili.com/video/BV1wx4y157nD
1.1 初见思路
- 先按左边界进行排序，然后逐个遍历，进行区间合并
1.2 具体实现
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(a,b)-> Integer.compare(a[0],b[0]));List<int[]> list = new LinkedList<>();int tempL = intervals[0][0];int tempR = intervals[0][1];for(int[] arr:intervals){if(arr[0]<=tempR){//可以合并tempR = Math.max(tempR,arr[1]);}else{//不可以合并了，把区间收集起来，然后更新tempL和tempRlist.add(new int[]{tempL,tempR});tempL=arr[0];tempR=arr[1];}}list.add(new int[]{tempL,tempR});return list.toArray(new int[list.size()][]);}
}
1.3 重难点
- 二维数组排序写法：
Arrays.sort(intervals,(a,b)-> Integer.compare(a[0],b[0])); - 返回结果是二维数组，需要先用List来存，这里的写法都需要注意；
二、 738.单调递增的数字
题目链接：https://leetcode.cn/problems/monotone-increasing-digits/
文章讲解：https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html
视频讲解：https://www.bilibili.com/video/BV1Kv4y1x7tP
2.1 初见思路
- 判断这个数自己是否是单调递增，如果不是，那么就要缩小这个数
- 缩小肯定要从个位数开始考虑，但是仅仅缩小个位数是不可能满足条件的，因为刚都判断了不是单调递增，那么仅仅缩小个位数是，个位数更小了，更不可能，所以个位数肯定是9（从十位借1了，而不是变大哦）；
- 如果有十位，判断十位数减一后是否大于百位数，如果大于，那么就不动了，如果减一后小于百位数，就类似于刚个位数的操作，十位变成9了，百位需要减1，以此类推；
- 综上所述，其实是找下标，下标往后的就都是9，下标值-1；
2.2 具体实现
class Solution {public int monotoneIncreasingDigits(int n) {if(n==0){return 0;}List<Integer> list = new LinkedList<>();while (n != 0) {list.add(n % 10);n = n / 10;}int endIndex = 0;boolean flag = false;for (int i = 0; i < list.size() - 1; i++) {if (list.get(i) < list.get(i + 1)) {flag = true;list.set(i + 1, list.get(i + 1) - 1);endIndex = i;}}if (flag) {for (int i = 0; i <= endIndex; i++) {list.set(i, 9);}}reverseList(list);String res = "";for (int i = 0; i < list.size(); i++) {res += list.get(i) + "";}return Integer.parseInt(res);}private static void reverseList(List<Integer> list) {int leftIndex = 0;int rightIndex = list.size() - 1;while (leftIndex < rightIndex) {// Swap the elements at leftIndex and rightIndexInteger temp = list.get(leftIndex);list.set(leftIndex, list.get(rightIndex));list.set(rightIndex, temp);leftIndex++;rightIndex--;}}
}
上述写法效率太低了，仔细分析分析为什么效率这么低
2.3 重难点
- 怎么把这个int类型的数转成每一位来进行比较呢？
- 换个思路呢，直接用char数组
2.4 改进后的算法
class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] chars = s.toCharArray();int start = s.length();for (int i = s.length() - 2; i >= 0; i--) {if (chars[i] > chars[i + 1]) {chars[i]--;start = i+1;}}for (int i = start; i < s.length(); i++) {chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
}
