贪心算法day05

?435. 无重叠区间??

本题简单一些，估计大家不用想着贪心?，用自己直觉也会有思路。?

代码随想录

力扣题目链接(opens new window)

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

看到题目的第一想法

? ? ? ? 移除区间

? ? ? ? 先排序，使用linkedList，把排序好的存入，遍历看是否重叠，若重叠则移除前一个，从前往后移除

? ? ? ? 且count++,i--

????????[[1,100],[11,22],[1,11],[2,12]] 这个案例没实现

看到代码随想录之后的想法

? ? ? ? ?若重叠，则把两者的右区间更新为两个的最小的右区间，看与下面是否重叠,result++

? ? ? ? ?若不重叠，则往下走

自己实现过程中遇到的困难

? ? ? ? 记住这种操作方式，如果重叠则更新两者的最右边

? ? ? ? 有时候可以倒过来想问题，比如说重叠做什么操作，我们可以先想一下若不重叠我们先做什么操作?

? ? ? ? 这道题若不重叠，则跳过，若重叠，则更新右边界

class Solution {
    //public int eraseOverlapIntervals(int[][] intervals) {
        /*//移除后不重叠
        //找到一个和多个区间重叠的
        //先排序 若右边界<=下一个左边界 则不重叠
        //若前一个右边界>下一个左边界则重叠，移除前一个 
        //第一个值升序排列，第二个值降序
        //[[1,100],[11,22],[1,11],[2,12]] 这个案例没实现
        Arrays.sort(intervals,(a,b)->{
            if(a[0]==b[0]) return b[1]-a[1];
            return a[0]-b[0];
        });
        int remove=0;
        LinkedList<int[]> list = new LinkedList<>();
        for(int[] in:intervals){
            list.add(in);
        }
        for(int i=1;i<list.size();i++){
            //我这种做法，没办法判断两个重叠区间的后续区间是否也重叠
            if(list.get(i-1)[1]>list.get(i)[0]){
                list.remove(i-1);
                i--;
                remove++;
            }
        }
        return remove;
    }*/
    //卡哥做法和上一题一样
    //若inteval[i][1]>inteval[i+1][0] 则count++且把inteval[i+1][1]替换为inteval[i][1]
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->{
            if(a[0]==b[0]) return b[1]-a[1];
            return a[0]-b[0];
        });
        int remove=0;
        for(int i=1;i<intervals.length;i++){        
            if(intervals[i-1][1]>intervals[i][0]){
                intervals[i][1] = Math.min(intervals[i-1][1],intervals[i][1]);
                remove++;
            }
        }
        return remove;
    }
}

763.划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

• 输入：S = "ababcbacadefegdehijhklij"
• 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

看到题目的第一想法

?需要把字符串分割开来

?如何才能按照提议来分片呢？

用map？

? ? ?

看到代码随想录之后的想法

? ? ? ? ?使用一个长度为26的int 数组，遍历一边字符串，存放当前字符的最大下标

? ? ? ? ? 哈希的办法

? ? ? ? ?然后再遍历字符串，同时记录一下当前区间字符对应的最大下标，若当前区间字符对应的最大下标和当前下标相同，代表前面区间的所有字符的最大下标都比当前下标要小，则划分

? ? ? ? 然后指针继续往下走，继续划分

自己实现过程中遇到的困难

? ? ? ?1 没有想到字符对应哈希数组0~25 用于记录最大下标

? ? ? ?2 字符转int 下标，来记录值? int[s.charAt(i)-'0']=i

? ? ? ?3 使用一个left 和right left记录分割字符串的第一个下标，right代表当前区间内元素的最大下标

若right==i 则可以进行分割

????????

class Solution {
    public List<Integer> partitionLabels(String s) {
        //先把第一个元素分完，看区间里包括了哪些元素，一起代替
        //用一个map 来判断 是否包括这个

        //卡哥思路，先用一个数组记录每个元素的最远距离
        //若当前区域内的最远距离==当前遍历到的下标，则证明当前子串里所有的元素，后面都不会出现，则切分一个字串
        //存放每个区间的最大下标
        int[] chars = new int[26];
        for(int i=0;i<s.length();i++){
            chars[s.charAt(i)-'a']=i;
        }
        int left=0;
        //往后遍历,存放当前区间的最大下标
        int right = 0;
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<s.length();i++){
            //遍历这个获取字串
            right=Math.max(right,chars[s.charAt(i)-'a']);
            //若当前字符的下标==当前区间的最大下标
            if(i==right){
                list.add(right-left+1);
                left=right+1;
            }
        }
        return list;

    }
}

?

?56. 合并区间

力扣题目链接(opens new window)

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

• 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
• 输出: [[1,6],[8,10],[15,18]]
• 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例?2:

看到题目的第一想法

? ?先排序，然后把所有的数组放入一个linkedList中

? ?看linkedlist中是否有重叠区间 ，若重叠了则把linkedList中的那个元素移除，同时修改第一个元素

? ?然后再继续

看到代码随想录之后的想法

? ? ? ? list先存放第一个元素

? ? ? ?若不重叠则add，若重叠则把当前list中的最后一个元素右边界修改，再继续往下遍历(右边界不是修改为当前元素的右边界，而是两者中的最大值)

????????

自己实现过程中遇到的困难

? ? ? ? ? ? ? ? list转成int? ? list.toArray(new int[list.size()][])

? ? ? ? ? ? ? ? 先考虑不重叠的再考虑重叠的，倒过来想一下，如果一开始想重叠的就会比较繁琐

class Solution {
    /*public int[][] merge(int[][] intervals) {
        //如果重叠，则把第一个的第二个元素换成第二个的第二个元素，删除第二个元素
        Arrays.sort(intervals,(a,b)->{
            return a[0]-b[0];
        });
        LinkedList<int[]> list = new LinkedList<>();
        for(int[] i:intervals){
            list.add(i);
        }
        for(int i=0;i<list.size()-1;i++){
            if(list.get(i)[1]>=list.get(i+1)[0]){
                list.get(i)[1]=Math.max(list.get(i)[1],list.get(i+1)[1]);
                list.remove(i+1);
                i--;
            }
        }
        return list.toArray(new int[list.size()][]);

    }*/
    //卡哥做法不需要删除(时间复杂度比我的提升了70ms)
    public int[][] merge(int[][] intervals) {
        //如果重叠，则把第一个的第二个元素换成第二个的第二个元素，删除第二个元素
        Arrays.sort(intervals,(a,b)->{
            return a[0]-b[0];
        });
        ArrayList<int[]> list = new ArrayList<>();
        //卡哥做法不需要把所有元素放到数组里，只需要放第一个
        list.add(intervals[0]);
        //判断，如果重叠了，则更新上一个，如果没重叠，则加入到数组中
        for(int i=1;i<intervals.length;i++){
            if(list.get(list.size()-1)[1]>=intervals[i][0]){
                //前一个永远在list中，前一个的右边界换成，前后两者右边界的最大值
                list.get(list.size()-1)[1]=Math.max(list.get(list.size()-1)[1],intervals[i][1]);
            }else{
                list.add(intervals[i]);
            }
        }
        return list.toArray(new int[list.size()][]);

    }
}