贪心范围覆盖算法总结 | 刷题打卡

掘金团队号上线，助你 Offer 临门！ 点击 查看详情

难度从小到大, 总结了三种方法!!! 参考了力扣加加

范围覆盖

★★45. 跳跃游戏 II

难度中等

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

?贪心算法, 每次从可以到达的范围计算下次能到达的范围,进行遍历!!!

**时间复杂度：$O(n^2)$O(n2)，**因为最坏的情况比如 1 1 1 1 1 1111111，position 会从 55 更新到 00，并且每次更新都会经历一个 for 循环。

空间复杂度：$O(1)$O(1)

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    if(nums.length<=1) return 0;
    let len=nums.length;
    let start=0,curMax=0,count=0;

    while(true){
        //找出当前能跳跃到的最大位置
        count++;
        let tmp=curMax;  //保留这个值,方便start最后赋值
        //★注意这里千万不要写i<=curMax, curMax在变化!!!
        for(let i=start;i<=tmp;i++){
            curMax=Math.max(curMax,i+nums[i]);
        }
        if(curMax>=len-1) break;
        start=(++tmp);  //下一次开始的位置
    }
    return count;
};

?只用一个for循环的精简版

优化

从上面代码观察发现，其实被 while 包含的 for 循环中，i 是从头跑到尾的。

只需要在一次 跳跃 完成时，更新下一次 能跳到最远的距离。

并以此刻作为时机来更新 跳跃 次数。就可以在一次 for 循环中处理。

❗这种方法也有缺陷,不一定都是这样好 详见 link

时间复杂度: O(n):

空间复杂度: O(1)

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    if(nums.length<=1) return 0;
    let len=nums.length;
    //maxPos表示当前i能够到达的最大距离
    //end表示上一轮跳跃能够到达的最大距离
    let maxPos=0,end=0,count=0;

    for(let i=0;i<len;i++){
        maxPos=Math.max(maxPos,i+nums[i]);
        //如果到达了上轮的最大位置处,则要再进行一次跳跃
        //而我们也已经用maxPos记录了上一轮能到达的最大位置
        //并且要保证end不能为最后的位置,因为这里count++表示要进行下次跳跃
        if(i===end&&end!==len-1){
            end=maxPos;
            count++;
        }
    }
    return count;
};

?关键是maxPos记录当前能到达的最大值, 而end记录上一次跳跃能到达的最大值。当到达end时就表示上次跳跃结束， 进行下次跳跃！！！

▼看到评论有说可以直接联想到BFS层序遍历, 便采用了层序遍历: 不过在空间和时间上表现不是太好, 但这和上面是一样的思路

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    if(nums.length<=1) return 0;
    let len=nums.length;
    let jump=[[0,nums[0]]]; //数组中的位置和跳跃距离

    let count=0,preMax=0;  //preMax代表上一层最远的位置
    while(jump.length){
        //取jump中的位置进行一次跳跃
        count++;
        let tmp=[];
        let curMax=preMax;
        for(let i=0;i<jump.length;i++){
            let next=jump[i][0]+jump[i][1];
            curMax=Math.max(curMax,next);
        }
        if(curMax>=len-1) break;
        for(let i=preMax+1;i<=curMax;i++){
            tmp.push([i,nums[i]]);
        }
        jump=tmp;
    }
    return count;
};

★★1024. 视频拼接

难度中等

你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。

视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。

我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

示例 1：

输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
输出：3
解释：
我们选中 [0,2], [8,10], [1,9] 这三个片段。
然后，按下面的方案重制比赛片段：
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在我们手上有 [0,2] + [2,8] + [8,10]，而这些涵盖了整场比赛 [0, 10]。

示例 2：

输入：clips = [[0,1],[1,2]], T = 5
输出：-1
解释：
我们无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。

示例 3：

输入：clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
输出：3
解释： 
我们选取片段 [0,4], [4,7] 和 [6,9] 。

示例 4：

输入：clips = [[0,4],[2,8]], T = 5
输出：2
解释：
注意，你可能录制超过比赛结束时间的视频。

提示：

• 1 <= clips.length <= 100
• 0 <= clips[i][0] <= clips[i][1] <= 100
• 0 <= T <= 100

?思路和跳跃是一样的!!! 遍历的是需要覆盖的范围, 不是片段!!!

1. 根据需要覆盖的区间进行遍历, 记录0~i进行下次跳跃能到达的最远距离maxPos
2. 判断是否有空缺, maxPos=i则表示无法继续, 也就是没办法剪成完整的影片
3. end=i 表示已达上一轮能剪辑到的最长的位置, 需要进行下一个片段的选择

时间复杂度: O(n)

空间复杂度: O(n)

/**
 * @param {number[][]} clips
 * @param {number} T
 * @return {number}
 */
var videoStitching = function(clips, T) {

    //类似于桶排序或者之前网易的幸运数字,我们建立一个为区间长度的数组
    //记录处于位置loc上能到达的最远的地方
    let maxEnd=Array(T).fill(0);  //Math.max中如果有Number()后为NaN会直接返回NaN
    //和之前的跳跃有两个不同 
    //1.跳跃每个位置只有一个最远距离,而这里可能有多个,因此用一个for来取最大
    //2.跳跃必能达到最后,但这里不一定, 所以要考虑
    for(let i in clips){
        maxEnd[clips[i][0]]=Math.max(maxEnd[clips[i][0]],clips[i][1]);
    }

    //end表示当前跳跃能到达的最大位置,因此我们要在这个范围内寻找maxPos的点进行跳跃/剪辑
    //maxEnd(i)是指i位置能到达的最远处, maxPos是i前面所有的能到达的最远处
    let end=0,maxPos=0,count=0; 
    //★这里i不能等于T哦, 如果等于T那么最后会多加一次,因为可以达到T的话不应该在加了
    //★也不用担心万一到不了T,因为会到达T-1,T-1时会进行判断能否继续
    for(let i=0;i<T;i++){
        maxPos=Math.max(maxPos,maxEnd[i]);
        //能到达的最远处等于i表示无法继续向下进行了, 所以无法完成任务
        if(i===maxPos){
            return -1;
        }
        //已经到达了上次跳跃的最大处,需要选择下次跳跃为maxPos的点来进行下次跳跃
        if(end===i){
            count++;
            end=maxPos;
        }
    }
    return count;

};

▼按给定的范围数组遍历

/**
 * @param {number[][]} clips
 * @param {number} T
 * @return {number}
 */
var videoStitching = function(clips, T) {
    clips.sort((a,b)=>a[0]-b[0]);
    let i=0,end=0,maxPos=0,count=0;
    //题有点特殊, T可能为0, 那么一个片段都不需要
    //而下面的while默认必须要有一个片段
    if(T===0) return 0;
    while(i<clips.length){
        while(i<clips.length&&clips[i][0]<=end){
            maxPos=Math.max(maxPos,clips[i][1]);
            i++;
        }
        //此时应该clips[i][0]>end or i>=clips.length

        //前面的while已把上一轮能到达的点都遍历完毕,肯定会进行一次跳跃,因此++
        //不用担心maxPos>T, 因为maxPos>T影响的是下一轮是否jump,而本轮jump是早就确定了的
        count++;
        //maxPos>T表示满足条件不需要跳跃了 || i>=...超出范围了应该终止
        if(maxPos>=T||i>=clips.length) break;
        end=maxPos;
        //下一个片段的起点比当前能达到的最大距离都远,因此会空缺
        //前面判断了i,因此这里的i在范围内
        if(clips[i][0]>maxPos){
            return -1;
        }
    }
    return maxPos<T? -1:count;
};

自己的笨办法....

/**
 * @param {number[][]} clips
 * @param {number} T
 * @return {number}
 */
//题目中并没有说clips[i][0]
var videoStitching = function (clips, T) {
    //其实就是跳跃问题,只不过中间有些点可能没有
    //clips[i][0]为跳跃位置,clips[i][1]为跳跃距离
    clips.sort((a, b) => a[0] - b[0]);
    if (T === 0) return 0;
    if (clips[0][0] !== 0) return -1;
    let end = 0, maxPos = 0, count = 0;
    //这里的for循环实际上是一个已经跳跃了的情况,但不确定跳跃到哪里
    //我们需要根据maxPos来确定最贪婪的跳跃选择
    for (let i = 0; i < clips.length; i++) {
        while (i < clips.length - 1 && clips[i][0] === clips[i + 1][0]) {
            clips[i + 1][1] = Math.max(clips[i][1], clips[i + 1][1]);
            i++;
        }
        //原本是应该在end处更新,但是这里的片段可能没有end位置
        if (clips[i][0] > end) {
            //如果在上一轮的最大位置end前发现可以跳到大于clips[i]的位置
            //那么可以在中间进行依次片段剪辑来弥补
            //▼比如说 [0,2] [1,9] [5,9] 第一个片段只能到达2, 但其可以通过先跳跃到[1,9],
            //再跳跃到[5,9]或者更后面的位置,因此这里增加一次从[0,2]到[1,9]的跳跃
            //❗注意这里并没有增加[1,9]到[5,9]的跳跃!!!
            if (maxPos >= clips[i][0]) {
                count++;
                //处理初始化问题,第一次的跳跃的时候end不能直接为maxPos,此时maxPos还没更新
                end = maxPos;
                //这时是以之前的maxPos的点作为起点开始寻找下一个最大的maxPos点了!
                maxPos = Math.max(maxPos, clips[i][1]);
                //maxPos在之前不可能大于等于T,但是这个时候clips[i][1]却有可能>=T
                //如果这时候不考虑这种情况的话就会使maxPos=>clips[i]=>T变成maxPos=>T
                if (maxPos >= T) count++;
            } else {  //如果maxPos小于clips[i][0],说明无法填补这个空缺
                return -1;
            }
        }
        else if (clips[i][0] === end) {
            //刚好等于end的情况就和之前的跳跃问题一模一样了!!!
            count++;
            //此时必须要做一次跳跃,要在之前的maxPos和当前的位置i选择最大的
            maxPos = Math.max(maxPos, clips[i][1]);
            end = maxPos;
        } else {
            maxPos = Math.max(maxPos, clips[i][1]);
            //T秒的运动过程片段,但是clips[i][0]和clips[i][1]也可能大于T(输入错误的特殊情况)
            if (maxPos >= T) count++;
        }
        if (maxPos >= T) break;

    }
    if (maxPos < T) return -1;
    return count;
};

?反思:为什么自己的写法又臭又长需要考虑各种条件, 而别人的写法干净利落?

​ ▼我觉得主要是我没有抓住重点!!! 这类范围覆盖的题需要的是遍历 范围, 但我却直接想的是去遍历片段(需要考虑很多不容易想到的边界情况)!!! 完全忘记了第一次做跳跃时自己是怎么遍历的...

当然贪心都能转换为dp, dp也是干净利落, 思路如下:

dp[0]=0, 其余初始化为Infinity, dp[i]表示从[0,i]最少需要由多少个片段构成

▼每次遍历所有片段 , 如果i > $clips[j][0]$clips[j][0], 则比较$dp[i]$dp[i]和 $dp[clips[j][0]]+1$dp[clips[j][0]]+1 ,因为到[0, i ]可以由[0, $clips[j][0]$clips[j][0]]和[$clips[j][0]$clips[j][0], i] 组成 , 然后取最小的

★为什么i = $clips[j][0]$clips[j][0]不考虑? 如果等于的话, 直接用dp[i]就可以了, 不需要再跳一次!!! 而且此时的话dp[i]还是Infinity,我们首先需要确保可以从 [0,k] 再来确保能从[k,i]

dp的写法:

时间复杂度: O(n^2^)

空间复杂度: O(n)

/**
 * @param {number[][]} clips
 * @param {number} T
 * @return {number}
 */
var videoStitching = function(clips, T) {
    //题目要求是[0,T)
    //dp[i]表示[0,i)需要的最少片段数,我们会用所有片段去循环遍历
    let dp=Array(T+1).fill(Infinity);
    dp[0]=0;           //初始值为0 也表示[0,0)不需要片段
    for (let i=1;i<=T;i++){
        for (let v of clips){
            // v[0]<i<=v[1]说明可以用该片段
            // 剪辑成[v[0],i)
            if (v[0]<i&&v[1]>=i){
                dp[i]=Math.min(dp[i],dp[v[0]]+1)
            }
        }
    }
    return  dp[T]===Infinity? -1 : dp[T];
};

★★★1326. 灌溉花园的最少水龙头数目

难度困难

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。

花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n] 。

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i - ranges[i], i + ranges[i]] 。

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。

示例 1：

输入：n = 5, ranges = [3,4,1,1,0,0]
输出：1
解释：
点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。

示例 2：

输入：n = 3, ranges = [0,0,0,0]
输出：-1
解释：即使打开所有水龙头，你也无法灌溉整个花园。

提示：

• 1 <= n <= 10^4
• ranges.length == n + 1
• 0 <= ranges[i] <= 100

?还是老套路, 先转换数据和跳跃模式一样

时间复杂度: O(n):

/**
 * @param {number} n
 * @param {number[]} ranges
 * @return {number}
 */
var minTaps = function(n, ranges) {
    //n>=1, ranges.length=n+1
    //我们在意的是范围, 不是水龙头个数, 所以是n
    //maxEnd[i]表示在位置i, 能到达的最远距离
    let maxEnd=Array(n).fill(0);
    for(let i=0;i<ranges.length;i++){
        let low=Math.max(0,i-ranges[i]),
            high=i+ranges[i];
        maxEnd[low]=Math.max(maxEnd[low],high);
    }

    //对覆盖范围循环
    let end=0,maxPos=0,count=0;
    for(let i=0;i<n;i++){
        maxPos=Math.max(maxPos,maxEnd[i]);
        //i<n,如果在循环中maxPos=i表示无法使覆盖范围达到n
        if(maxPos===i) return -1;
        //end=i,表示上次的水龙头覆盖的最大范围已到,需要寻找下一个水龙头
        //也就是已达到上一轮跳跃最大距离,选择maxPos对应的位置
        //为上一轮的跳跃落脚点进行下一次跳跃
        if(end===i){
            end=maxPos;
            count++;
        }
    }
    return count;
};

▼这是自己按照上面那道题直接套的dp, 性能不是太好???

/**
 * @param {number} n
 * @param {number[]} ranges
 * @return {number}
 */
var minTaps = function(n, ranges) {
    //n>=1, ranges.length=n+1
    //dp[i]表示[0,i]需要的水龙头数目
    let dp=Array(n+1).fill(Infinity);
    dp[0]=0;
	//先处理成范围
    for(let i=0;i<ranges.length;i++){
        let low=Math.max(0,i-ranges[i]),
            high=i+ranges[i];
        ranges[i]=[low,high];
    }

    //对覆盖范围循环
    for(let i=1;i<=n;i++){
        for(let v of ranges){
            if(v[0]<i&&v[1]>=i){
                dp[i]=Math.min(dp[i],dp[v[0]]+1);
            }
        }
    }

    return dp[n]===Infinity? -1:dp[n];
};

腾讯笔试:视野争夺

链接：www.nowcoder.com/questionTer… 来源：牛客网

小Q在进行一场竞技游戏,这场游戏的胜负关键就在于能否能争夺一条长度为L的河道,即可以看作是[0,L]的一条数轴。

这款竞技游戏当中有n个可以提供视野的道具−真视守卫,第i个真视守卫能够覆盖区间[xi,yi]。现在小Q想知道至少用几个真视守卫就可以覆盖整段河道。

输入描述:

输入包括n+1行。

第一行包括两个正整数n和L(1<=n<=10^5^,1<=L<=10^9^)

接下来的n行,每行两个正整数xi,yi(0<=xi<=yi<=10^9^),表示第i个真视守卫覆盖的区间。

输出描述:

一个整数，表示最少需要的真视守卫数量, 如果无解, 输出-1。

示例1

输入

4 6
3 6
2 4
0 2
4 7

输出

3

?这道题你>可能会以为又和之前的一样, 但是有坑!!! 注意到了吗? 如果又是按之前的范围覆盖来计算, 那么计算量会达到$10^9$109量级(超时❗), 但如果采用对片段进行遍历的话 只有 $10^5$105 , 因此对片段遍历还是对范围遍历要看情况!!!

const readline=require('readline');
const rl=readline.createInterface({
    input:process.stdin,
    output:process.stdout
})
const arr=[]
let n,l;
rl.on('line',function(line){
    arr.push(line.split(' ').map(Number));
    if(arr.length===1){
        n=Number(arr[0][0]);
        l=Number(arr[0][1]);
    }else if(arr.length===n+1){
        arr.shift();
        arr.sort((a,b)=>a[0]-b[0]);

        let end=0,maxPos=0,count=0,i=0;
        while (i<arr.length){
            //求出在上一轮跳跃范围内最大的maxPos
            //由于已经排好序,end=0初始化时也满足情况
            while (i<arr.length&&arr[i][0]<=end){
                maxPos=Math.max(maxPos,arr[i][1]);
                ++i;
            }
            //跳跃一次
            count++;
            end=maxPos;
            //直接起点大于了当前能跳跃到的最大距离,出现了空缺
            if (i<arr.length&&arr[i][0]>end){
                count=-1; break;
            }
            if (maxPos>=l) break;
        }
        //退出时maxPos未能达到l
        if (maxPos<l){
            count=-1;
        }
        console.log(count);
        
        //next
        arr.length=0;
    }
})

我在了解这个方法后也对1024进行了范围数组遍历的改写 link 1024

?Summary

覆盖有三种方法:

一. 覆盖范围遍历

1. 建立一个长度为覆盖范围长度的数组maxEnd, 对片段数组进行遍历, 记录位于位置i能到达的最远距离$maxEnd[i]$maxEnd[i] , 初始化为0
2. 对覆盖范围进行遍历, 更新maxPos为$[0,i]$[0,i]中能跳跃到的最远节点
3. end=i 表示已经到达了上次跳跃的最大处,需要选择下次跳跃为maxPos的点来进行下次跳跃

二.片段数组遍历

1. 先将片段数组进行排序
2. 使用一个while把当前轮的都遍历完并更新maxPos
3. end=maxPos进行相关更新并对退出条件进行判断

三.动态规划

dp[i]表示[0,i)需要的最少片段数,我们会用所有片段去循环遍历