十五周算法训练营—贪心算法

跳跃游戏

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

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

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

// 该问题其实可以进行修改，请问通过题目中的跳跃规则，最多能跳多远？如果能够越过最后一格，返回true，否则返回false。

// 该问题就转换为了最值问题

// 直接用贪心算法
function canJump(nums) {
    let farthest = 0;

    for (let i = 0; i < nums.length - 1; i++) {
        // 不断计算能够跳到的最远的距离
        farthest = Math.max(farthest, i + nums[i]);
        // 可能碰到了0，卡住跳不动了
        if (farthest <= i) {
            return false;
        }
    }

    return farthest >= nums.length - 1;
}

// 既然是最值问题，可以用动态规划进行求解
// 1. 状态和选择
// 状态：从第i个位置能否跳转到最后
// 选择：跳几步
// 2. dp数组含义
// dp[i]表示能否通过第i个位置跳转到最后位置
// 3. 状态转移逻辑
// 若要求解dp[i]，则可以通过看i + [0……nums[i]]中是否有可到达最后一个下标的
// 4. base case
// dp[n - 1] = true
function canJump1(nums) {
    const n = nums.length;
    const dp = (new Array(n)).fill(false);

    // base case
    dp[n - 1] = true;

    // 从后向前开始遍历
    for (let i = n - 2; i >= 0; i--) {
        for (let j = 0; j <= nums[i]; j++) {
            if (dp[i + j]) {
                dp[i] = dp[i + j];
                break;
            }
        }
    }

    console.log(dp);

    return dp[0];
}

const nums = [2, 3, 1, 1, 4];
console.log(canJump1(nums));

加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2] 输出: 3 解释: 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油 开往 4 号加油站，此时油箱有 4 – 1 + 5 = 8 升汽油 开往 0 号加油站，此时油箱有 8 – 2 + 1 = 7 升汽油 开往 1 号加油站，此时油箱有 7 – 3 + 2 = 6 升汽油 开往 2 号加油站，此时油箱有 6 – 4 + 3 = 5 升汽油 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。因此，3 可为起始索引。

// 该问题用贪婪算法解决我理解不了，但是图像解法可以理解

// 汽车进入站点i可以加gas[i]的油，离开站点会损耗cost[i]的油，那么可以把站点和与其相连的路看做一个整体，将gas[i] - cost[i]作为经过站点i的油量变化值
// 这样题目描述的场景就被抽象成一个环形数组，数组中的第i个元素就是gas[i] - cost[i]
// 有了这个环形数组，就需要判断这个环形数组中是否能够找到一个起点start，使得从这个起点开始的累加和一直大于等于0
function canCompleteCircuit(gas, cost) {
    let sum = 0;
    let minSum = 0;
    let start = 0;

    for (let i = 0; i < gas.length; i++) {
        sum += (gas[i] - cost[i]);

        if (sum < minSum) {
            minSum = sum;
            start = i + 1;
        }
    }

    if (sum < 0) {
        return -1;
    }

    return start;
}

合并区间

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

示例 1：

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

function merge(intervals) {
    if (intervals.length <= 0) {
        return [];
    }
    // 首先将区间按照起点的升序进行排序
    intervals.sort((interval1, interval2) => {
        return interval1[0] - interval2[0];
    });

    let result = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const [start, end] = intervals[i];

        // 当开始节点在区间内时，更新结果
        if (start <= result[result.length - 1][1]) {
            result[result.length - 1][1] = Math.max(end, result[result.length - 1][1]);
            continue;
        } else {
            // 在开始节点不在区间内时，插入新的结果
            result.push(intervals[i]);
        }
    }

    return result;
}

const intervals = [[1,3],[2,6],[8,10],[15,18]];
console.log(merge(intervals));

会议室

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。

示例 1：

输入：intervals = [[0,30],[5,10],[15,20]] 输出：false

// 该问题用线性扫描方法进行解决
// 首先，对区间进行投影，就相当于对每个区间的起点和终点分别进行排序
// 扫描线从左向右前进，遇到红点就对计数器加1，遇到绿点就对计数器减1，计数器的最大值就是答案

function minMeetingRooms(meetings) {
    const n = meetings.length;

    const begins = new Array(n);
    const ends = new Array(n);

    for (let i = 0; i < n; i++) {
        begins = meetings[i][0];
        ends = meetings[i][1];
    }

    // 对内容进行排序
    begins.sort((begin1, begin2) => begin1 - begin2);
    ends.sort((end1, end2) => end1 - end2);

    let count = 0;
    let result = 0;
    let i = 0;
    let j = 0;

    // 双指针进行遍历
    while (i < n && j < n) {
        if (begins[i] > ends[j]) {
            count--;
            j++;
        } else {
            count++;
            i++;
        }

        // 记录扫描过程中的最大值
        result = Math.max(result, count);
    }

    return result;
}

无重叠区间

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

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。

// 该问题是一个区间调度问题
// 首先将区间集合按照end进行升序排序
// 选择结束最早的end值，然后将其重叠的全部删除掉
// 重复进行，直到没有重叠区域
// 这样就可以得到最多有几个互不相交的区间，则就是移除权健的最小数，使剩余区间互不重叠

// 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
// 把所有与 x 区间相交的区间从区间集合 intvs 中删除。
// 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。

// 这个其实就是贪心算法，相当于排序后，每次都可以选择出最优解，每一次都是局部最优，最终的结果就是全局最优
function eraseOverlapIntervals(intervals) {
    intervals.sort((interval1, interval2) => {
        return interval1[1] - interval2[1];
    });

    // 至少有一个区间不相交
    let count = 1;
    // 排序后，第一个区间就是x
    let end = intervals[0][1];

    for (let i = 1; i < intervals.length; i++) {
        const presentInterval = intervals[i];

        if (presentInterval[0] >= end) {
            count++;
            end = presentInterval[1];
        }
    }

    return intervals.length - count;
}

// 因为是最值问题，我们也可以考虑动态规划

const intervals = [[1,2],[2,3],[3,4],[1,3]];
console.log(eraseOverlapIntervals(intervals));