代码随想录Day30 贪心05 LeetCode T435无重叠区间 T763划分字母区间 T56 合并区间

LeetCode T435 无重叠区间

题目链接:435. 无重叠区间 - 力扣（LeetCode）

题目思路:

这题思路和昨天的打气球类似,我们需要按照左区间或者右区间进行排序,然后哦判断第i个区间的左端点和第i-1个区间的右端点的大小关系,,如果大于等于,那么就无需操作,一旦小于了,那么就发生了重叠,相应的我们更新左端点为两者之间的较小值,并且要对定义的count进行++,这样就统计了重叠的个数,也就是我们要删除的个数.总体思路类似于昨天

题目代码:

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a,b)-> {return Integer.compare(a[0],b[0]);});int count = 0;for(int i = 1;i < intervals.length;i++){if(intervals[i][0] < intervals[i-1][1]){intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);count++;}}return count;}
}

LeetCode T763 划分字母区间

题目链接:763. 划分字母区间 - 力扣（LeetCode）

题目思路:

首先我们明确题意,这题的要求是对字符串中的第一个字母开始,再找到第一个字母的过程,途中遇见的字母必须全部包含在内,最后分割后的字符串,每个字母都只出现在这个子串中,有人不理解这道题的题目

这里举个例子

开头是a,这里我们就要找到下一个a,但是找寻的途中遇见了b,这里所有的b也必须包含在内了,以此类推.我们的思路是对每个字母进行映射,每次更新字母最后出现的位置,然后遍历数组,看到达那个位置的途中有没有遇见更大的位置,有则更新,当我遍历的位置等于我目前的最大位置时,将目前为止减去开始位置的大小加入到结果数组中.

题目代码:

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> result = new ArrayList<>();int[] edge = new int[26];char[] chars = s.toCharArray();for(int i = 0;i<chars.length;i++){edge[chars[i] - 'a'] = i;}int index = 0;int lastedge = -1;for(int i = 0;i<chars.length;i++){index = Math.max(edge[chars[i] - 'a'],index);if(index == i){result.add(i-lastedge);lastedge = i;}}return result;}
}

LeetCode T56 合并区间

题目链接:56. 合并区间 - 力扣（LeetCode）

题目思路:

我们这里使用和之前一样的策略来解决问题,这里首先按照左区间进行排序一次,我们进行一次for循环,定义一个start来标记区间的起始位置,一个bound来标记结束位置,我们尽心判断,如果区间的左区间大于上一个的右区间,这里就没有重复的,我们就进行添加,添加完更新左右区间,否则就直接更新右区间为原来bound和现在的最大值,以包含覆盖这一整个区间,最后结束之后再添加最后一个区间,因为这里比较了少了一次,所以要额外加一个元素.最后以二维数组形式返回即可.

题目代码:

class Solution {public int[][] merge(int[][] intervals) {List<int[]> result = new ArrayList<>();Arrays.sort(intervals,(a,b)->{return a[0] - b[0];    });int start = intervals[0][0];int bound = intervals[0][1];for(int i = 0;i<intervals.length;i++){if(intervals[i][0]>bound){result.add(new int[]{start,bound});start = intervals[i][0];bound = intervals[i][1];}else{bound = Math.max(bound,intervals[i][1]);}}result.add(new int[]{start,bound});return result.toArray(new int[result.size()][]);}
}