摘要
- 今天的題目的共同點(diǎn)是從左到右遍歷數(shù)組中的元素，記錄會(huì)影響局部最優(yōu)的那個(gè)元素的信息嚼隘，從而影響到下一步的選擇诽里。
- 和動(dòng)態(tài)規(guī)劃比起來，不需要記錄每個(gè)元素的信息飞蛹，只需要記錄會(huì)影響下一步的元素的信息即可谤狡。
LeetCode122 買賣股票的最佳時(shí)機(jī)
- 每一步：根據(jù)
prices[i - 1]和prices[i]的大小關(guān)系，決定第i - 1天是否買入股票并在第i天出售桩皿。 - 局部最優(yōu)：
prices[i - 1] < prices[i]豌汇，在第i天賣出股票有利潤幢炸。 - 全局最優(yōu)：得到的利潤最大泄隔。
完整題解代碼如下
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
if (prices.size() < 2) return profit;
for (int i = 1; i < prices.size(); i++) {
if (prices[i - 1] >= prices[i]) continue;
else profit += prices[i] - prices[i - 1];
}
return profit;
}
};
LeetCode55 跳躍游戲
將每個(gè)點(diǎn)（即數(shù)組的每個(gè)元素）擴(kuò)展成對應(yīng)可以跳躍到的區(qū)間，都是向右跳宛徊，所以再對可以跳躍到的點(diǎn)做擴(kuò)展成可以跳躍到的區(qū)間的操作佛嬉。
直到區(qū)間包括數(shù)組最后一位或者展開所有點(diǎn)都不能使區(qū)間包含數(shù)組最后一位。
這題的貪心選擇策略闸天，簡單來說就是根據(jù)當(dāng)前能跳躍到的范圍從左到右暖呕，求每個(gè)位置能跳躍到的范圍，并根據(jù)當(dāng)前位置的范圍來更新能跳躍到的范圍苞氮。當(dāng)能跳躍到的范圍已經(jīng)包含最后一個(gè)下標(biāo)時(shí)湾揽，
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover = 0;
for (int i = 0; i <= cover; i++) {
cover = max(i + nums[i], cover);
if (cover >= nums.size() - 1) return true;
}
return false;
}
};
LeetCode45 跳躍游戲II
- 和上一題的思路類似，也是將每個(gè)點(diǎn)展開成一個(gè)可以跳躍到的區(qū)間笼吟。
- 和上一題不同的是库物，這題需要統(tǒng)計(jì)跳躍的步數(shù)，所以不能每到一個(gè)位置都更新可以跳躍的到的區(qū)間贷帮。為了區(qū)分每一步跳躍戚揭，應(yīng)該保存當(dāng)前可以跳躍到的區(qū)間和下一步可以跳躍到的區(qū)間。實(shí)際上就記錄了每一步跳躍能到達(dá)的區(qū)間撵枢。
- 以
[2, 2, 1, 1, 4]為例
- 第一步民晒，當(dāng)
i = 0時(shí)，計(jì)算出這一步可以跳躍到的區(qū)間為[0, 2]锄禽，所以當(dāng)i在[0, 2]中移動(dòng)時(shí)潜必，都只算一步。并且沃但，當(dāng)i在[0, 2]中移動(dòng)時(shí)刮便，要根據(jù)每個(gè)位置記錄下一步能到的最遠(yuǎn)距離。下一步的最遠(yuǎn)距離由i = 1或i = 2時(shí)取到绽慈，都是最遠(yuǎn)到i = 3恨旱。 - 第二步辈毯，當(dāng)
i = 2時(shí)，已經(jīng)到達(dá)了第一步最遠(yuǎn)能跳到的位置搜贤，要再往下跳的話谆沃，需要多跳一步，并更新可以跳躍到的區(qū)間為[2, 3]仪芒，下一步能到的最遠(yuǎn)位置是i = 4唁影。 - 第三步， 當(dāng)
i = 3掂名，到達(dá)了第二步能最遠(yuǎn)能跳到的位置据沈，要再往下跳，第三步能到達(dá)的最遠(yuǎn)位置是i = 4饺蔑。到達(dá)數(shù)組最后一位
題解代碼如下
class Solution {
public:
int jump(vector<int>& nums) {
int step = 0;
int curCover = 0;
int nextCover = 0;
// 要注意循環(huán)終止的條件锌介，到達(dá)數(shù)組最后一位就不用再跳了，所以i最大是nums.size()-2
// 如果i < nums.size()猾警，會(huì)多算一步孔祸，多算的一步就是在數(shù)組最后一位再往后跳
for (int i = 0; i < nums.size() - 1; i++) {
nextCover = max(i + nums[i], nextCover);
if (i >= curCover) {
curCover = nextCover;
step++;
}
}
return step;
}
};
