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

LeetCode 56 合并区间题目链接56.合并区间文档讲解代码随想录视频讲解合并区间思路与感想一开始觉得删除区间增加新的区间有点复杂后面想到了写二叉树的时候有result二维数组和path一维数组我就想到了别在原地操作不就完了然后也照着当时写二叉树那样写了这俩数组。整体思路还是挺简单的有了昨天的经验这次我就按照了左边界排序然后遇到重复区间我就更新右区间为二者最大值但麻烦就麻烦在这个区间处理操作我没有像后面看视频讲解时卡哥那样把前面那个区间整个放进去而是先放第一个区间的左边界然后后面再根据情况添加右边界啥的搞得很是麻烦而且很容易考虑漏掉这也反映了我思维不缜密的坏习惯。后面提交了两次多添了两个测试案例才过了有种东补西补但也没花多少时间整体做下来也就十几分钟不过还是感觉这样是弊大于利的。卡哥的思路就比较精简了是先把整个区间填进去如果有问题呢就左边界右边界各自取新的之后然后把res上一个区间删了填新的进去如果当前区间跟前面没冲突呢就直接把这个区间加进去至于符不符合要求那就让后面的区间检验这种延时处理学习了收获1.延时处理2.区间整体添加class Solution { public int[][] merge(int[][] intervals) { if (intervals.length 1) { return intervals; } ListListInteger result new ArrayListListInteger(); ListInteger 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) { ListInteger 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) { Listint[] 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)); } }贪心结束了花了三个小时搞定老实说经历了二叉树和回溯章节后逐渐习惯有模板和套路做题但是贪心却让我回归刚刷算法时那种思维乱跳的时候了不过我却明显感觉这种思维乱跳没有当初那样盲目了而是能够渐渐形成自己的思路并付诸代码实现。也算是一种大进步了。加油下一站就是动态规划了再往后是单调栈、图论时间也已经快过半了自己也慢慢抵达这场旅途的终点。不错行百里者半九十坚持是一种天赋但切忌自我高潮保持虚心学习的态度在计算机领域是极其重要的