十五周算法訓(xùn)練營(yíng)—貪心算法
跳躍游戲
給定一個(gè)非負(fù)整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個(gè)下標(biāo) 。
數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。
判斷你是否能夠到達(dá)最后一個(gè)下標(biāo)。
示例 1：
輸入：nums = [2,3,1,1,4] 輸出：true 解釋：可以先跳 1 步，從下標(biāo) 0 到達(dá)下標(biāo) 1, 然后再?gòu)南聵?biāo) 1 跳 3 步到達(dá)最后一個(gè)下標(biāo)。
// 該問題其實(shí)可以進(jìn)行修改，請(qǐng)問通過題目中的跳躍規(guī)則，最多能跳多遠(yuǎn)？如果能夠越過最后一格，返回true，否則返回false。
// 該問題就轉(zhuǎn)換為了最值問題
// 直接用貪心算法
function canJump(nums) {
let farthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
// 不斷計(jì)算能夠跳到的最遠(yuǎn)的距離
farthest = Math.max(farthest, i + nums[i]);
// 可能碰到了0，卡住跳不動(dòng)了
if (farthest <= i) {
return false;
}
}
return farthest >= nums.length - 1;
}
// 既然是最值問題，可以用動(dòng)態(tài)規(guī)劃進(jìn)行求解
// 1. 狀態(tài)和選擇
// 狀態(tài)：從第i個(gè)位置能否跳轉(zhuǎn)到最后
// 選擇：跳幾步
// 2. dp數(shù)組含義
// dp[i]表示能否通過第i個(gè)位置跳轉(zhuǎn)到最后位置
// 3. 狀態(tài)轉(zhuǎn)移邏輯
// 若要求解dp[i]，則可以通過看i + [0……nums[i]]中是否有可到達(dá)最后一個(gè)下標(biāo)的
// 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));加油站
在一條環(huán)路上有 n 個(gè)加油站，其中第 i 個(gè)加油站有汽油 gas[i] 升。
你有一輛油箱容量無限的的汽車，從第 i 個(gè)加油站開往第 i+1 個(gè)加油站需要消耗汽油 cost[i] 升。你從其中的一個(gè)加油站出發(fā)，開始時(shí)油箱為空。
給定兩個(gè)整數(shù)數(shù)組 gas 和 cost ，如果你可以繞環(huán)路行駛一周，則返回出發(fā)時(shí)加油站的編號(hào)，否則返回 -1 。如果存在解，則 保證 它是 唯一 的。
示例 1:
輸入: gas = [1,2,3,4,5], cost = [3,4,5,1,2] 輸出: 3 解釋: 從 3 號(hào)加油站(索引為 3 處)出發(fā)，可獲得 4 升汽油。此時(shí)油箱有 = 0 + 4 = 4 升汽油 開往 4 號(hào)加油站，此時(shí)油箱有 4 - 1 + 5 = 8 升汽油 開往 0 號(hào)加油站，此時(shí)油箱有 8 - 2 + 1 = 7 升汽油 開往 1 號(hào)加油站，此時(shí)油箱有 7 - 3 + 2 = 6 升汽油 開往 2 號(hào)加油站，此時(shí)油箱有 6 - 4 + 3 = 5 升汽油 開往 3 號(hào)加油站，你需要消耗 5 升汽油，正好足夠你返回到 3 號(hào)加油站。因此，3 可為起始索引。
// 該問題用貪婪算法解決我理解不了，但是圖像解法可以理解
// 汽車進(jìn)入站點(diǎn)i可以加gas[i]的油，離開站點(diǎn)會(huì)損耗cost[i]的油，那么可以把站點(diǎn)和與其相連的路看做一個(gè)整體，將gas[i] - cost[i]作為經(jīng)過站點(diǎn)i的油量變化值
// 這樣題目描述的場(chǎng)景就被抽象成一個(gè)環(huán)形數(shù)組，數(shù)組中的第i個(gè)元素就是gas[i] - cost[i]
// 有了這個(gè)環(huán)形數(shù)組，就需要判斷這個(gè)環(huán)形數(shù)組中是否能夠找到一個(gè)起點(diǎn)start，使得從這個(gè)起點(diǎn)開始的累加和一直大于等于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;
}合并區(qū)間
以數(shù)組 intervals 表示若干個(gè)區(qū)間的集合，其中單個(gè)區(qū)間為 intervals[i] = [starti, endi] 。請(qǐng)你合并所有重疊的區(qū)間，并返回 一個(gè)不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間 。
示例 1：
輸入：intervals = [[1,3],[2,6],[8,10],[15,18]] 輸出：[[1,6],[8,10],[15,18]] 解釋：區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
function merge(intervals) {
if (intervals.length <= 0) {
return [];
}
// 首先將區(qū)間按照起點(diǎn)的升序進(jìn)行排序
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];
// 當(dāng)開始節(jié)點(diǎn)在區(qū)間內(nèi)時(shí)，更新結(jié)果
if (start <= result[result.length - 1][1]) {
result[result.length - 1][1] = Math.max(end, result[result.length - 1][1]);
continue;
} else {
// 在開始節(jié)點(diǎn)不在區(qū)間內(nèi)時(shí)，插入新的結(jié)果
result.push(intervals[i]);
}
}
return result;
}
const intervals = [[1,3],[2,6],[8,10],[15,18]];
console.log(merge(intervals));會(huì)議室
給定一個(gè)會(huì)議時(shí)間安排的數(shù)組 intervals ，每個(gè)會(huì)議時(shí)間都會(huì)包括開始和結(jié)束的時(shí)間 intervals[i] = [starti, endi] ，請(qǐng)你判斷一個(gè)人是否能夠參加這里面的全部會(huì)議。
示例 1：
輸入：intervals = [[0,30],[5,10],[15,20]] 輸出：false
// 該問題用線性掃描方法進(jìn)行解決
// 首先，對(duì)區(qū)間進(jìn)行投影，就相當(dāng)于對(duì)每個(gè)區(qū)間的起點(diǎn)和終點(diǎn)分別進(jìn)行排序
// 掃描線從左向右前進(jìn)，遇到紅點(diǎn)就對(duì)計(jì)數(shù)器加1，遇到綠點(diǎn)就對(duì)計(jì)數(shù)器減1，計(jì)數(shù)器的最大值就是答案
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];
}
// 對(duì)內(nèi)容進(jìn)行排序
begins.sort((begin1, begin2) => begin1 - begin2);
ends.sort((end1, end2) => end1 - end2);
let count = 0;
let result = 0;
let i = 0;
let j = 0;
// 雙指針進(jìn)行遍歷
while (i < n && j < n) {
if (begins[i] > ends[j]) {
count--;
j++;
} else {
count++;
i++;
}
// 記錄掃描過程中的最大值
result = Math.max(result, count);
}
return result;
}無重疊區(qū)間
給定一個(gè)區(qū)間的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊 。
示例 1:
輸入: intervals = [[1,2],[2,3],[3,4],[1,3]] 輸出: 1 解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊。
// 該問題是一個(gè)區(qū)間調(diào)度問題
// 首先將區(qū)間集合按照end進(jìn)行升序排序
// 選擇結(jié)束最早的end值，然后將其重疊的全部刪除掉
// 重復(fù)進(jìn)行，直到?jīng)]有重疊區(qū)域
// 這樣就可以得到最多有幾個(gè)互不相交的區(qū)間，則就是移除權(quán)健的最小數(shù)，使剩余區(qū)間互不重疊
// 從區(qū)間集合 intvs 中選擇一個(gè)區(qū)間 x，這個(gè) x 是在當(dāng)前所有區(qū)間中結(jié)束最早的（end 最小）。
// 把所有與 x 區(qū)間相交的區(qū)間從區(qū)間集合 intvs 中刪除。
// 重復(fù)步驟 1 和 2，直到 intvs 為空為止。之前選出的那些 x 就是最大不相交子集。
// 這個(gè)其實(shí)就是貪心算法，相當(dāng)于排序后，每次都可以選擇出最優(yōu)解，每一次都是局部最優(yōu)，最終的結(jié)果就是全局最優(yōu)
function eraseOverlapIntervals(intervals) {
intervals.sort((interval1, interval2) => {
return interval1[1] - interval2[1];
});
// 至少有一個(gè)區(qū)間不相交
let count = 1;
// 排序后，第一個(gè)區(qū)間就是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;
}
// 因?yàn)槭亲钪祮栴}，我們也可以考慮動(dòng)態(tài)規(guī)劃
const intervals = [[1,2],[2,3],[3,4],[1,3]];
console.log(eraseOverlapIntervals(intervals));
