https://leetcode.com/problems/jump-game-ii/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
|
class Solution { public: int jump(vector<int>& nums) { int n=nums.size(); int step=0;//记录步数 int left=0; int right=0;//记录左右可达范围 if(n==1) return 0; while(left<=right) { step++; int old_right=right; //在左右边界中找下一个最大边界 for(int i=left;i<=old_right;i++) { int new_right=i+nums[i];//记录当前可到达最大边界 if(new_right>=n-1) { //k可到达,返回步数 return step; } if(new_right>right) { //更新当前可到达最大右边界值 right=new_right; } } //左边界更新到原来的右边界右边 left=old_right+1; } } };
|
近期评论