#LeetCode:45. Jump Game II

灆洢 2019-04-11 21:58:06

在每段可以到的最遠距離之中,找出下一段可以到的最遠距離,找完後進入下一段循環這個過程到結尾即可。

C++(12ms)

/*******************************************************/
/* LeetCode 45. Jump Game II                           */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2019/04/11                                 */
/*******************************************************/
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
  int jump(vector<int>& nums) {
    int furthest = 0;
    int step = 0;
    for(int i = 0 ; i < nums.size() && furthest < nums.size() - 1 ; ){
      int currentFurthest = 0;
      while(i <= furthest){
        currentFurthest = max(i + nums[i], currentFurthest);
        ++i;
      }
      furthest = currentFurthest;
      ++step;
    }

    return step;
  }
};

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料