代碼隨想錄算法訓(xùn)練營(yíng)day32 | 題目122掌逛、題目55拇颅、題目45
題目一描述
122. 買(mǎi)賣(mài)股票的最佳時(shí)機(jī) II
給你一個(gè)整數(shù)數(shù)組 prices ，其中 prices[i] 表示某支股票第 i 天的價(jià)格。
在每一天，你可以決定是否購(gòu)買(mǎi)和/或出售股票碍舍。你在任何時(shí)候 最多 只能持有 一股 股票。你也可以先購(gòu)買(mǎi)邑雅，然后在 同一天 出售片橡。
返回 你能獲得的 最大 利潤(rùn) 。
示例 1：
輸入：prices = [7,1,5,3,6,4]
輸出：7
解釋?zhuān)涸诘?2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入淮野，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 5 - 1 = 4 捧书。
隨后吹泡，在第 4 天（股票價(jià)格 = 3）的時(shí)候買(mǎi)入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 6 - 3 = 3 经瓷。
總利潤(rùn)為 4 + 3 = 7 爆哑。
示例 2：
輸入：prices = [1,2,3,4,5]
輸出：4
解釋?zhuān)涸诘?1 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 5 - 1 = 4 了嚎。
總利潤(rùn)為 4 。
示例 3：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋?zhuān)涸谶@種情況下, 交易無(wú)法獲得正利潤(rùn)廊营，所以不參與交易可以獲得最大利潤(rùn)歪泳，最大利潤(rùn)為 0 。
提示：
1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4
解題思路
每次只在后一天比前一天高的時(shí)候取差值露筒。
代碼實(shí)現(xiàn)
方法一：
class Solution {
public int maxProfit(int[] prices) {
int sum = 0;
for (int i = 0; i < prices.length; i++) {
if (i > 0 && prices[i] > prices[i - 1]) {
sum += prices[i] - prices[i - 1];
}
}
return sum;
}
}
題目二描述
給你一個(gè)非負(fù)整數(shù)數(shù)組 nums 呐伞，你最初位于數(shù)組的 第一個(gè)下標(biāo) 。數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度慎式。
判斷你是否能夠到達(dá)最后一個(gè)下標(biāo)伶氢，如果可以，返回 true 瘪吏；否則癣防，返回 false 。
示例 1：
輸入：nums = [2,3,1,1,4]
輸出：true
解釋?zhuān)嚎梢韵忍?1 步掌眠，從下標(biāo) 0 到達(dá)下標(biāo) 1, 然后再?gòu)南聵?biāo) 1 跳 3 步到達(dá)最后一個(gè)下標(biāo)蕾盯。
示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋?zhuān)簾o(wú)論怎樣，總會(huì)到達(dá)下標(biāo)為 3 的位置蓝丙。但該下標(biāo)的最大跳躍長(zhǎng)度是 0 级遭， 所以永遠(yuǎn)不可能到達(dá)最后一個(gè)下標(biāo)。
提示：
1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5
解題思路
可以先找到每一處0渺尘，然后往會(huì)倒推挫鸽，看能不能跳過(guò)這個(gè)0.
也可以用貪心，每次計(jì)算在本次能覆蓋到的范圍里鸥跟，新的能覆蓋的最大位置丢郊，最后判斷最大位置是不是數(shù)組最后一位。
代碼實(shí)現(xiàn)
方法一：
class Solution {
public boolean canJump(int[] nums) {
if (nums.length == 1)
return true;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == 0) {
if (check(nums, i - 1) == false)
return false;
}
}
return true;
}
private boolean check(int[] nums, int i) {
int n = 1;
while (i >= 0) {
if (nums[i] > n) {
return true;
}
i--;
n++;
}
return false;
}
}
方法二：
class Solution {
public boolean canJump(int[] nums) {
if (nums.length == 1)
return true;
int maxRes = 0;
for (int i = 0; i < nums.length - 1; i++) {
if(maxRes < i){
return false;
}
maxRes = Math.max(maxRes, nums[i] + i);
}
return maxRes >= nums.length - 1;
}
}
題目三描述
給定一個(gè)長(zhǎng)度為 n 的 0 索引整數(shù)數(shù)組 nums医咨。初始位置為 nums[0]蚂夕。
每個(gè)元素 nums[i] 表示從索引 i 向前跳轉(zhuǎn)的最大長(zhǎng)度。換句話(huà)說(shuō)腋逆，如果你在 nums[i] 處婿牍，你可以跳轉(zhuǎn)到任意 nums[i + j] 處:
0 <= j <= nums[i]
i + j < n
返回到達(dá) nums[n - 1] 的最小跳躍次數(shù)。生成的測(cè)試用例可以到達(dá) nums[n - 1]惩歉。
示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個(gè)位置的最小跳躍數(shù)是 2等脂。
從下標(biāo)為 0 跳到下標(biāo)為 1 的位置俏蛮，跳 1 步，然后跳 3 步到達(dá)數(shù)組的最后一個(gè)位置上遥。
示例 2:
輸入: nums = [2,3,0,1,4]
輸出: 2
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
題目保證可以到達(dá) nums[n-1]
解題思路
每次在可達(dá)范圍內(nèi)找到新的最大的可覆蓋范圍搏屑，在i移動(dòng)到當(dāng)前可達(dá)范圍邊界時(shí)，把可達(dá)范圍更新粉楚，相當(dāng)于把i移動(dòng)到每個(gè)區(qū)間里可達(dá)范圍最大的那個(gè)位置辣恋，跳躍次數(shù)加一。
實(shí)際上不用移動(dòng)i模软，只需要更新范圍即可伟骨。
代碼實(shí)現(xiàn)
方法一：
class Solution {
public int jump(int[] nums) {
if (nums.length == 1) {
return 0;
}
int maxCoverRange = nums[0];
int curCoverRange = nums[0];
int res = 0;
for (int i = 0; i < nums.length; i++) {
// 如果當(dāng)前范圍可以跳到，就直接跳最后一步
if (curCoverRange >= nums.length - 1) {
res++;
return res;
}
// 得到在curCoverRange里的最大范圍
if (maxCoverRange < nums[i] + i) {
maxCoverRange = nums[i] + i;
}
// i走到當(dāng)前范圍的最后燃异，再更新cur為新的maxCoverRange携狭，也相當(dāng)于跳一步到區(qū)間內(nèi)的那個(gè)最大值上。
if (i == curCoverRange) {
res++;
// 這里其實(shí)應(yīng)該把i置于取到maxCoverRange的時(shí)候的下標(biāo)
// 但是其實(shí)不用回俐，因?yàn)閏urRange的后面的都沒(méi)有max那里大逛腿，再算也是重復(fù)計(jì)算〗銎模可以從i繼續(xù)往后遍歷单默。
curCoverRange = maxCoverRange;
}
}
return res;
}
}
