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

leetcode筆記:Jump Game II

編輯:關於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.

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.)

二. 題目分析

該題的大意是,給定一個數組,每個元素代表從該位置可以往後跳的距離,問從第一個位置跳到最後一個位置至少需要跳多少次。

與 Jump Game 有所不同的是,Jump Game 詢問該數組能否跳到最後一格,這道題要求算出跳的次數。解決的思路依舊是貪心,只需設置一個數組用來記錄跳的路徑即可。

三. 示例代碼

class Solution {
public:
    int jump(int A[], int n) 
    {
        int result = 0; // 當前已跳躍的次數
        int last = 0;   // 上一跳可達到的最遠距離
        int curr = 0;   // 當前一跳可達到的最遠距離
        for (int i = 0; i < n; ++i) 
        {
            // 無法向前繼跳直接返回
            if(i > curr)
                return -1;
            // 需要進行下次跳躍,則更新last和當前已執行的跳數result
            if (i > last) 
            {
                last = curr;
                ++result;
            }
            // 更新當前可跳達的最遠處
            curr = max(curr, i+A[i]);
        }
        return result;
    }
};

四. 小結

類似的解題思路還有BFS,後期可以驗證驗證。

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