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

leetcode || 55、Jump Game

編輯:C++入門知識

leetcode || 55、Jump Game


problem:

 

 

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.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

 

Hide Tags Array Greedy 題意:從起點跳躍,每次跳躍的最大步數為該位置的數組值,判斷能否最後跳到最後一個位置

 

thinking:

(1)剛開始想到DFS,對每一個到達的結點作深搜,但是由於邊界條件較少,時間復雜度會急劇膨脹,不太可行

(2)另外一種方法是采用貪心策略,之前一道Jump Game 題目,求步數的也是采用貪心。思路是,采用A[base+step]+step的加權方式來衡量每一次選擇的優劣,判斷當跳到第一個0處,能否到達或者超過數組最後一個數字。

這裡假設成立的是:每次跳躍選擇往最遠處跳躍,如果最後能夠跳到數組最後一位或者最後一位之後,那麼一定存在一種跳躍方式正好跳到最後一位上

這個假設很容易證明是成立的,因為最後一步跳躍可以選擇0~step之間的任意一步

code:

 

class Solution {
public:
    bool canJump(int A[], int n) {
        if(n==1)
            return true;
        int index=0;
        int _max=0;
        while(index=n-1)
                return true;
            if(A[index]==0 )
            {
                if(_max=tmp)
                    {
                        tmp=A[index+i]+i;
                        flag=i;
                    }
            }
           index+=flag;
           _max=A[index]+index;
        }
        
    }
};


 

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