1 題目

給定一個非負整數數組，你最初位于數組的第一個位置。

數組中的每個元素代表你在該位置可以跳躍的最大長度。

你的目標是使用最少的跳躍次數到達數組的最后一個位置。

假設你總是可以到達數組的最后一個位置。

2 解法

2.1 從終點遍歷的方法(時間復雜度)

計算出從后到前的所有格子到終點的最少步:

int jump(vector<int>& nums) {int nums_size = nums.size();if (nums_size <= 2) {return nums_size - 1;}vector<int> min_step_to_final(nums_size, 0);min_step_to_final[nums_size - 1] = 0;min_step_to_final[nums_size - 2] = nums[nums_size - 2] ? 1 : -1;for (int i = nums_size - 3; i >= 0; i --) {if (nums[i] >= nums_size - 1 - i)min_step_to_final[i] = 1;else {if (nums[i] == 0)min_step_to_final[i] = -1;else {int step_index = 1;int next_step = -1;while (step_index <= nums[i]) {if (min_step_to_final[i + step_index] != -1) {if (next_step == -1)next_step = min_step_to_final[i + step_index];elsenext_step = min(next_step, min_step_to_final[i + step_index]);}step_index ++;}if (next_step != -1)min_step_to_final[i] = next_step + 1;elsemin_step_to_final[i] = -1;}}}return min_step_to_final[0];}

2.2 總是尋找當前能到達的最遠位置(貪心)(時間復雜度)

維護兩個位置, 第一個是當前這步最遠能到達的位置, 第一個是下一步最遠能到達的位置, 遍歷數組, 當索引值到達了當前這一步能到達的最遠位置, 總步數加一, 當前步數最遠到達位置賦值為下一步最遠到達位置, 下一步最遠到達位置清零:

int jump(vector<int>& nums) {int nums_size = nums.size();if (nums_size < 3)return nums_size - 1;int steps = 1;int current_step_max_pos = nums[0];int next_step_max_pos = 0;int index = 1;while (current_step_max_pos < nums_size - 1) {next_step_max_pos = max(next_step_max_pos, index + nums[index]);index ++;if (index > current_step_max_pos) {steps ++;current_step_max_pos = next_step_max_pos;next_step_max_pos = 0;}}return steps;}

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的leetcode45 --- jump的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。