代码随想录算法训练营第三十四天丨贪心算法part05

本文主要是介绍代码随想录算法训练营第三十四天丨贪心算法part05，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

435. 无重叠区间

思路

为了让区间尽可能的重叠，我按照左边界排序，从左向右记录重叠区间的个数。最后直接返回记录的重叠区间的个数就行了。

本题其实和昨天做的 ‘用最少数量的箭引爆气球’ 的思路整体是一样的，忘记思路可用看昨天的题目笔记

代码如下：

class Solution {public int eraseOverlapIntervals(int[][] intervals) {if(intervals.length==0){return 0;}//对数组根据start进行排序Arrays.sort(intervals,(a,b) ->{if (a[0]==b[0])return a[1] - b[1];return a[0] - b[0];});int count = 0;//统计需要移除的数量for (int i = 1; i < intervals.length; i++) {//如果当前元素和前一元素有重复区间if (intervals[i][0] < intervals[i-1][1]){count++;intervals[i][1] = Math.min(intervals[i][1],intervals[i-1][1]);}}return count;}
}

763.划分字母区间

思路

题目要求同一字母最多出现在一个片段中，那么如何把同一个字母的都圈在同一个区间里呢？

之前从来没碰过这种类型的题目，有点难度。

在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

可以分为如下两步：

统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

如图：

763.划分字母区间

明白原理之后，代码如下：

class Solution {public List<Integer> partitionLabels(String s) {//统计单个字母最远出现下标int[] index = new int[26];for (int i = 0; i < s.length(); i++) {index[s.charAt(i) - 'a'] = i;}int left = 0;int right = 0;LinkedList<Integer> list = new LinkedList<>();for (int i = 0; i < s.length(); i++) {right = Math.max(right,index[s.charAt(i)-'a']);if (i==right){list.add(right-left+1);left = i+1;}}return list;}
}

56. 合并区间

思路

这题我的解题思路与卡哥略有不同，卡哥是额外定义一个数组来进行区间的合并的。而我是使用原来的数组，但是我遍历到第 i 个元素的时候，与第 i-1 个元素进行比较，如果有重叠区间，我直接在当前第 i 个元素上进行合并，但没有重叠区间时，直接添加上一个重叠区间到数组中。

代码如下：

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));LinkedList<int[]> list = new LinkedList<>();for (int i = 1; i < intervals.length; i++) {//当前元素与上个元素有重叠if (intervals[i][0] <= intervals[i-1][1]){intervals[i][0] = intervals[i-1][0];intervals[i][1] = Math.max(intervals[i][1],intervals[i-1][1]);}else {list.add(intervals[i-1]);}}//此时还差最后一个元素未处理，直接加入// 因为如果最后一个元素与前一元素有重叠区域，那么就会更新最后一个元素list.add(intervals[intervals.length-1]);int[][] res = new int[list.size()][];for (int i = 0; i < list.size(); i++) {res[i] = list.get(i);}return res;}
}

对比之下来说，卡哥的时间复杂度比我低的多，还是得多学习。