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

作者：前端点线面 2023-07-03 08:01:54开发 前端 今天是周算十五周算法训练营的第十四周，主要讲贪心算法专题。法训

跳跃游戏

给定一个非负整数数组 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] = truefunction 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，使得从这个起点开始的累加和一直大于等于0function 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));

责任编辑：姜华 来源： 前端点线面 算法贪心算法

(责任编辑：百科)