代码随想录算法第三十一天| LeetCode56合并区间、LeetCode738单调递增的数字

LeetCode 56 合并区间

题目链接：56.合并区间

文档讲解：代码随想录

视频讲解：合并区间

思路与感想：一开始觉得删除区间增加新的区间有点复杂，后面想到了写二叉树的时候有result二维数组和path一维数组，我就想到了别在原地操作不就完了，然后也照着当时写二叉树那样写了这俩数组。整体思路还是挺简单的，有了昨天的经验，这次我就按照了左边界排序，然后遇到重复区间我就更新右区间为二者最大值，但麻烦就麻烦在这个区间处理操作，我没有像后面看视频讲解时卡哥那样把前面那个区间整个放进去，而是先放第一个区间的左边界，然后后面再根据情况添加右边界啥的，搞得很是麻烦，而且很容易考虑漏掉，这也反映了我思维不缜密的坏习惯。后面提交了两次多添了两个测试案例才过了，有种东补西补，但也没花多少时间，整体做下来也就十几分钟，不过还是感觉这样是弊大于利的。卡哥的思路就比较精简了，是先把整个区间填进去，如果有问题呢，就左边界右边界各自取新的之后，然后把res上一个区间删了填新的进去，如果当前区间跟前面没冲突呢就直接把这个区间加进去，至于符不符合要求那就让后面的区间检验，这种延时处理学习了！

收获：1.延时处理；2.区间整体添加

class Solution { public int[][] merge(int[][] intervals) { if (intervals.length == 1) { return intervals; } List<List<Integer>> result = new ArrayList<List<Integer>>(); List<Integer> path = new ArrayList<>(); Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0])); path.add(intervals[0][0]); for(int i = 1; i < intervals.length; i++) { if (intervals[i][0] <= intervals[i - 1][1]) { intervals[i][1] = Math.max(intervals[i][1],intervals[i - 1][1]); if (path.size() > 1) { path.removeLast(); } path.add(intervals[i][1]); } else { if (path.size() == 1) { path.add(intervals[i - 1][1]); } result.add(new ArrayList(path)); path.clear(); path.add(intervals[i][0]); path.add(intervals[i][1]); } if (i == intervals.length - 1) { result.add(new ArrayList(path)); } } int[][] res = new int[result.size()][]; for (int i = 0; i < result.size(); i++) { List<Integer> inner = result.get(i); int[] temp = new int[inner.size()]; for (int j = 0; j < inner.size(); j++) { temp[j] = inner.get(j); } res[i] = temp; } return res; } }

// 精简版 class Solution { public int[][] merge(int[][] intervals) { List<int[]> res = new ArrayList<>(); Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0])); // 按照左边界排序 res.add(intervals[0]); // 先把第一个区间加进去，交给后面的区间判断 for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] <= res.getLast()[1]) { // 如果说当前区间左边界小于等于res里面最后一个区间的右边界，说明发生了重叠 int left = res.getLast()[0]; // 取出左边界，注意我们已经按照左边界升序排序了，所有res最后一个区间的左边界一定小于当前区间的左边界 int right = Math.max(intervals[i][1],res.getLast()[1]); // 右边界因为没有排序处理，这里要取二者最大值 res.removeLast(); // 把res最后一个区间去掉 res.add(new int[]{left,right}); // 添入新的区间 } else { res.add(intervals[i]); // 当前区间跟前面没啥冲突就先加进来，留给后面区间检验 } } return res.toArray(new int[res.size()][]); } }

LeetCode 738 单调递增的数字

题目链接：738.单调递增的数字

文档讲解：代码随想录

视频讲解：单调递增的数字

思路与感想：一开始想着就是暴力解法外层for循环遍历这个n数值，内层for循环遍历这个数字每一位，但一想这样肯定超时，因为n的最大范围太大了。后面想着用一个for循环高度，但是在处理数字的每一位的时候又犯了难，想着不会要用取余一个个搞吧那挺麻烦的。当时已经大体思路已经确定了从后往前遍历，如果前面的数字大于当前遍历的数字那就把当前数字置为9，前面的数字减一，后面知道这样直接置为9是不行的。看卡哥视频讲解后发现卡哥用字符数组突然恍然大悟，这样不论是遍历数字每一位还是说修改每一位上的数字都轻松多了，然后只需要说用个下标flag记录需要开始变成9的位置就行了。

收获：1.String的valueOf和parseInt方法；2.需要对数字每一位进行处理时可以考虑把数字转为char数组

// 贪心算法 class Solution { public int monotoneIncreasingDigits(int n) { String s = String.valueOf(n); // 转成字符数组容易后续更新每个位置的值 char[] chars = s.toCharArray(); int flag = chars.length; // 记录开始变成9的下标位置 for (int i = chars.length - 1; i > 0; i--) { // 从后往前遍历 if (chars[i - 1] > chars[i]) { // 如果前面的数字大于当前遍历的数字 chars[i - 1]--; // 前面数字自减 flag = i; // flag更新为当前下标 } } for (int i = flag; i < chars.length; i++) { // 自flag起让后面的数字都变成9 chars[i] = '9'; } return Integer.parseInt(String.valueOf(chars)); } }

贪心结束了，花了三个小时搞定，老实说经历了二叉树和回溯章节后，逐渐习惯有模板和套路做题，但是贪心却让我回归刚刷算法时那种思维乱跳的时候了，不过我却明显感觉这种思维乱跳没有当初那样盲目了，而是能够渐渐形成自己的思路并付诸代码实现。也算是一种大进步了。加油，下一站就是动态规划了，再往后是单调栈、图论，时间也已经快过半了，自己也慢慢抵达这场旅途的终点。不错！行百里者半九十，坚持是一种天赋，但切忌自我高潮，保持虚心学习的态度在计算机领域是极其重要的！