程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode] Jump Game II

[LeetCode] Jump Game II

編輯:C++入門知識

[LeetCode] Jump Game II


Jump Game II

 

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

解題思路:

最值問題,第一想到的就是動態規劃。用d[i]記錄從0到i最小的步數,則d[i]=min(d[k]+1),其中k是所有能夠到達i的下標。最開始,我用一個vector數組記錄所有能夠到達自身的下標,代碼如下:

 

class Solution {
public:
    int jump(vector& nums) {
        int len = nums.size();
        if(len<2){
            return 0;
        }
        int d[len];
        d[0] = 0;
        vector pre[len];
        for(int i=1; i<=nums[0] && i時間復雜度為O(n*n),空間復雜度為O(n*n)。超時錯誤。

 

後經過改進,不需要記錄前驅節點,代碼如下,空間復雜度變為O(n),但時間復雜度仍為O(n*n),產生超時錯誤。

 

class Solution {
public:
    int jump(vector& nums) {
        int len = nums.size();
        if(len<2){
            return 0;
        }
        int d[len];
        for(int i=1; i水中的<。)#)))≦給我們一個非常好的解法:http://fisherlei.blogspot.com/2012/12/leetcode-jump-ii.html,采用貪心算法,記錄第k步最多能夠走,且對第k+1步有影響的范圍[Left, Right],每走一步,left變成right+1,right變成[left, right]區間內走一步最遠的下標。這裡與上述方法的根本區別就是left=right+1,而非left=left+1,這樣能夠減少很多計算。因為[left+1,
 right]已經在[left, right]時已經計算過了。

 

 

class Solution {
public:
    int jump(vector& nums) {
        int len = nums.size();
        int left = 0;
        int right = 0;
        int count = 0;
        while(right=len - 1){
                    break;
                }
            }
            left = right + 1;
            right=mostRight;
            if(right

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved