代码随想录算法训练营第三十五天| 435. 无重叠区间、 763.划分字母区间、56. 合并区间

435

题目:

给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 

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

思路:

先按起始位置升序排列,然后判断是否有重合,如果重合就count+1,然后判断哪个区间的end更大,两个区间肯定要删除一个,end更大的容易和后续重合故删。

详情:代码随想录 (programmercarl.com)

代码:

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->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])
                continue;
            else{
                count++;
                if(intervals[i-1][1]<=intervals[i][1]) //i的终止位置大,更容易影响后续故删
                {
                    intervals[i][0]=intervals[i-1][0];
                    intervals[i][1]=intervals[i-1][1];
                }
                else{//i-1的终止位置大,更容易影响后续故删
                    intervals[i-1][0]=intervals[i][0];
                    intervals[i-1][1]=intervals[i][1];                   
                }
            }
        }
        return count;
    }
}

763

题目:

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。

注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

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

思路:

使用for循环,在其中判断当前对应的字符在字符串最后一次出现下标,在这个下标之前的所有字符都要计算lastindexof,当i==index则是一个分段。

详情:代码随想录 (programmercarl.com)

代码:

class Solution {
    public List<Integer> partitionLabels(String s) {
        List <Integer> len =new ArrayList<Integer>(); 
        int index =-1;//片段的end
        int flag=0;//辅助标识片段start
        int start=-1;
        for(int i=0;i<s.length();i++)
        {
            if(flag==0) 
            {
               start=i;
               flag=1;
            }
            String str =Character.toString(s.charAt(i));
            int last =s.lastIndexOf(str);
            if(last > index)
                index = last;
            if(i==index)    
            {
                int temp =index-start+1;
                len.add(temp);
                flag =0;
                start=-1;
                index =-1;
            }
        }
        return len;
    }
}

56

题目:

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

题目链接:56. 合并区间 - 力扣(LeetCode)

思路:

先判断前者和后者是否有交集,有的话将合并的结果存在后者,然后另开一个动态数组存储结果,只需要存合并后的区间和不相交的区间。

详情:代码随想录 (programmercarl.com)

代码:

class Solution {
    public int[][] merge(int[][] intervals) {
        int index = intervals.length - 1;//为了处理24行的边界情况
        if(index==0) return intervals;//只有一个区间
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));//按start升序排序
        for (int i = 1; i < index + 1; i++) { //有交集则将i-1和i的区间合并存储到i里
            if (intervals[i][0] > intervals[i - 1][1])
                continue;
            else {
                intervals[i][0] = Math.min(intervals[i - 1][0],intervals[i][0]);
                intervals[i][1] = Math.max(intervals[i-1][1],intervals[i][1]);
            }
        }
        LinkedList<int[]> que = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < index; i++) { //判断前者是否是后者子区间,如果是则继续,如果不是则保存
            if (intervals[i][0] >= intervals[i + 1][0] && intervals[i][1] <= intervals[i + 1][1])
                continue;
            else {
                que.add(intervals[i]);
                count++;
            }
        }
        //边界情况
        if (intervals[index - 1][0] >= intervals[index][0] && intervals[index - 1][1] <= intervals[index][1]) {
            que.add(intervals[index]);
            count++;
        } else {
            que.add(intervals[index]);
            count = count + 1;
        }
        return que.toArray(new int[count][]);
    }
}

上一篇:盲盒小程序开发常见问题有哪些?


下一篇:Linux双网卡默认路由优先级设置不正确,导致网络不通问题定位-问题描述