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 维护相邻两个整数的被覆盖区间数量变化量

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

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