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

leetcode筆記:Jump Game

編輯:關於C++

一. 題目描述

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.

二. 題目分析

該題的大意是,給定一個數組,從第一個元素開始,元素的值表示能夠往後跳的最大距離,問按照這種規則,該數組是否能跳到最後一個元素。

解題的基本思路是貪心算法。當然,使用動態規劃也是完全可以解決的,也貼出網上一種動規代碼。

三. 示例代碼

// greedy algorithm
class Solution {
public:
    bool canJump(int A[], int n) {
        if(n == 0 || n == 1){
            return true;
        }
        int maxStep = A[0];
        for(int index = 1 ; index < n ; ++index)
        {
            if(maxStep == 0) return false;
            --maxStep; 
            if(maxStep < A[index])
                maxStep = A[index];
            if(maxStep + index >= n - 1) // 滿足條件
                return true;
        }
    }
};
// DP algorithm
class Solution {
public:
    bool canJump(int A[], int n) 
    {
        vector f(n, 0);
        f[0] = 0;
        for (int i = 1; i < n; i++) 
        {
            f[i] = max(f[i - 1], A[i - 1]) - 1;
            if (f[i] < 0) return false;
        }
        return f[n - 1] >= 0;
    }
};

四. 小結

該題的思路是,使maxStep一直保持最大的能移動步數。

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