跳跃游戏
给定一个非负整数数组 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));
