徐州网站app开发,东莞做网站软件,我想给网站网站做代理,凡客官网登录代码随想录刷题day31丨56. 合并区间#xff0c;738.单调递增的数字#xff0c;总结
1.题目
1.1合并区间 题目链接#xff1a;56. 合并区间 - 力扣#xff08;LeetCode#xff09; 视频讲解#xff1a;贪心算法#xff0c;合并区间有细节#xff01;LeetCode#x…代码随想录刷题day31丨56. 合并区间738.单调递增的数字总结
1.题目
1.1合并区间 题目链接56. 合并区间 - 力扣LeetCode 视频讲解贪心算法合并区间有细节LeetCode56.合并区间_哔哩哔哩_bilibili 文档讲解https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html 解题思路贪心 判断区间重贴后要进行区间合并。先排序让所有的相邻区间尽可能的重叠在一起按左边界按照左边界从小到大排序之后如果 intervals[i][0] intervals[i - 1][1] 即intervals[i]的左边界 intervals[i - 1]的右边界则一定有重叠。本题相邻区间也算重贴所以是知道如何判断重复之后剩下的就是合并了如何去模拟合并区间呢 其实就是用合并区间后左边界和右边界作为一个新的区间加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。 代码 //时间复杂度: O(nlogn)
//空间复杂度: O(logn)
class Solution {public int[][] merge(int[][] intervals) {//按照左边界排序Arrays.sort(intervals,(a,b) - Integer.compare(a[0],b[0]));Listint[] result new LinkedList();// 第一个区间就可以放进结果集里后面如果重叠在result上直接合并result.add(intervals[0]);for(int i 1;i intervals.length;i){if(intervals[i][0] result.getLast()[1]){result.getLast()[1] Math.max(intervals[i][1],result.getLast()[1]);}else{result.add(intervals[i]);}}return result.toArray(new int[result.size()][]);}
}总结 本质其实还是判断重叠区间问题。
1.2单调递增的数字 题目链接738. 单调递增的数字 - 力扣LeetCode 视频讲解贪心算法思路不难想但代码不好写LeetCode:738.单调自增的数字_哔哩哔哩_bilibili 文档讲解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 解题思路贪心 从后往前遍历一旦出现chars[i - 1] chars[i]的情况非单调递增首先想让chars[i - 1]减一chars[i]赋值9 代码 class Solution {public int monotoneIncreasingDigits(int n) {String s String.valueOf(n);char[] chars s.toCharArray();// flag用来标记赋值9从哪里开始// 设置为这个默认值为了防止第二个for循环在flag没有被赋值的情况下执行int flag chars.length;for(int i chars.length - 1;i 0;i--){if(chars[i - 1] chars[i]){chars[i - 1]--;flag i;}}for(int i flag;i chars.length;i){chars[i] 9;}return Integer.parseInt(String.valueOf(chars));}
}总结 最后代码实现的时候也需要一些技巧例如用一个flag来标记从哪里开始赋值9。
2.贪心总结 贪心的本质是选择每一阶段的局部最优从而达到全局最优。 贪心没套路就刷题而言如果感觉好像局部最优可以推出全局最优然后想不到反例那就试一试贪心吧 for循环适合模拟从头到尾的遍历而while循环适合模拟环形遍历
