LeetCode —— 覆盖问题

1893. 检查是否区域内所有整数都被覆盖

图片说明
图片说明

思路一:先排序,后检查

class Solution {
    public boolean isCovered(int[][] ranges, int left, int right) {
        //1.先按照数组第一个数升序排序
        Arrays.sort(ranges , (a,b) -> (a[0] - b[0]));
        int i = 0;
        //2.找到左端点所在数组,更新左端点为数组第二个数
        while( i < ranges.length ){
            int l = ranges[i][0];
            int r = ranges[i][1];
            if(left >= l && left <= r){
                left = r + 1;
            }
            i++;
        }
        //3.判断【更新后的左端点】是否超过【右端点】
        return left > right;
    }
}

思路二:差分数组+前缀和

1.对判断区域range内所有整数计算覆盖的区间数量

2.用差分数组 \textit{diff}diff 维护相邻两个整数的被覆盖区间数量变化量

全部评论

相关推荐

不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
认真搞学习:这么良心的老板真少见
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务