資訊專欄INFORMATION COLUMN
摘要：數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個位置。示例輸入輸出解釋跳到最后一個位置的最小跳躍數(shù)是。不過可惜的是復(fù)雜度過大，為，用例不通過。也只訪問一次，時間復(fù)雜度為。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定一個非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個位置。
數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。
你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個位置。
示例:
輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數(shù)是 2。
從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳 1 步，然后跳 3 步到達(dá)數(shù)組的最后一個位置。
解答：
和第55題一樣，首先試一下動態(tài)規(guī)劃dp[i]代表到坐標(biāo)為i的節(jié)點(diǎn)所用的最短步驟。
那么dp[0] = 0，dp[i] = min(dp[i-k]+1) , k >= 0 并且 k <= i-1,并且nums[k]+k >= i。
不過可惜的是復(fù)雜度過大，為O(N2)，用例不通過。
換一種思路，這個和第55題一樣，這是個貪心問題，用一個max變量記錄當(dāng)前能夠到達(dá)的最遠(yuǎn)節(jié)點(diǎn)。那么初始時
max = nums[0]，對于i=1...nums.length-1，如果nums[i]+i > max（即該節(jié)點(diǎn)能夠到達(dá)比max更遠(yuǎn)的節(jié)點(diǎn)）
就更新max，并且把dp[max+1]...dp[nums[i]+i]更新為dp[i]+1否則跳過。這樣一來，每一個節(jié)點(diǎn)只計算一次。
也只訪問一次，時間復(fù)雜度為O(N)。
java ac代碼：
class Solution {
public int jump(int[] nums) {
int[]dp = new int[nums.length];
//用這個最大值代替優(yōu)先隊列，因?yàn)樾Ч且粯拥? //用優(yōu)先隊列保存已經(jīng)求出的最大下標(biāo)也可以，但是
//每次都是從小到大求，所以每次求出更新max即可
//保持是最大的，不需要使用優(yōu)先隊列。
int max = nums[0];
for(int i = 1;i < nums.length && i <= nums[0];i++)
{
dp[i] = 1;
}
for(int i = 1;i < nums.length;i++)
{
for(int k = max+1;k < nums.length&&k<=i+nums[i];k++)
{
dp[k] = dp[i]+1;
max = k;
}
}
return dp[nums.length-1];
}
}
動態(tài)規(guī)劃超時代碼：
class Solution {
public int jump(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = 0;
for(int i = 1;i < nums.length;i++)
{
int temp = Integer.MAX_VALUE;
for(int k = i-1;k >= 0;k--)
if(nums[k] >= i-k)
temp = Math.min(temp,dp[k]);
dp[i] = temp+1;
}
return dp[nums.length-1];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/73752.html
摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖，寫出一個函數(shù)找到所有的最小高度樹并返回他們的根節(jié)點(diǎn)。因此使用一個數(shù)組代表每個節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述： 對于一個具有樹特征的無向圖，我們可選擇任何一個節(jié)點(diǎn)作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號的車神? ?個人主頁：應(yīng)無所住而生...
摘要：更新之前說感覺優(yōu)秀答案的最后三行可以用尾遞歸優(yōu)化不知道尾遞歸的小伙伴可以點(diǎn)這里，仔細(xì)想了一下，并不能。尾遞歸的實(shí)現(xiàn)，往往需要改寫遞歸函數(shù)，確保最后一步只調(diào)用自身。 上周日就想寫vue.nextTick的源碼分析，可是總是不知道從哪兒下手，今天有時間，先把leetcode第二題補(bǔ)了，感覺這道題還挺簡單的 一、題目 兩數(shù)相加： 給出兩個 非空 的鏈表用來表示兩個非負(fù)的整數(shù)。其中，它們各自...
摘要：對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結(jié)束坐標(biāo)?？梢陨涑龅墓臄?shù)量沒有限制。弓箭一旦被射出之后，可以無限地前進(jìn)。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。解答這是一道區(qū)間覆蓋問題，不太好說清楚，利用模板即可。 題目地址：https://leetcode-cn.com/probl...題目描述：在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方...
閱讀 936·2023-04-25 23:40
閱讀 3715·2021-11-22 15:22
閱讀 3556·2021-10-09 09:44
閱讀 3408·2021-09-23 11:52
閱讀 1266·2021-09-22 15:43
閱讀 794·2021-09-10 10:51
閱讀 2214·2021-09-06 15:02
閱讀 3208·2021-09-06 15:02
