leetcode 45. Jump Game II

﹏ヽ暗。殇╰゛Y 2022-08-21 04:44 22阅读 0赞

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

Note:  
You can assume that you can always reach the last index.

class Solution {
    	bool jump_once(vector<int>& nums, vector<int>&startpos, set<int>&history)
    	{
    		vector<int>newstartpos;
    		for (int i = 0; i < startpos.size(); i++)
    		{
    			if (nums[startpos[i]] >= nums.size() - 1 - startpos[i])
    				return true;
    			for (int j = startpos[i] + 1; j <= startpos[i] + nums[startpos[i]]; j++)
    				if (history.find(j) == history.end())
    				{
    					history.insert(j);
    					newstartpos.push_back(j);
    				}
    		}
    		startpos = newstartpos;
    		return false;
    	}
    public:
    	int jump(vector<int>& nums) {
    		if (nums.size() == 1)
    			return 0;
    		bool f = false;
    		vector<int>startpos;
    		set<int>history;
    		startpos.push_back(0);
    		int k = 0;
    		while (!f)
    		{
    			f = jump_once(nums, startpos,history);
    			k++;
    		}
    		return k;
    	}
    };

超时

class Solution {
    	bool jump_once(vector<int>& nums, vector<int>&startpos, set<int>&history)
    	{
    		vector<int>newstartpos;
    		for (int i = 0; i < startpos.size(); i++)
    		{
    			if (nums[startpos[i]] >= nums.size() - 1 - startpos[i])
    				return true;
    			if (history.find(startpos[i] + nums[startpos[i]]) == history.end())
    			{
    				history.insert(startpos[i] + nums[startpos[i]]);
    				newstartpos.push_back(startpos[i] + nums[startpos[i]]);
    			}
    			int bb = startpos[i] ;
    			while (bb + 1 <= startpos[i] + nums[startpos[i]])
    			{
    				while (bb + 1 <= startpos[i] + nums[startpos[i]] && nums[startpos[i]] >= nums[bb + 1] + bb + 1 - startpos[i])
    					bb++;
    				if (bb + 1 != startpos[i] + nums[startpos[i]] + 1)
    					if (history.find(bb + 1) == history.end())
    					{
    						history.insert(bb + 1);
    						newstartpos.push_back(bb + 1);
    					}
    				bb++;
    			}
    		}
    		startpos = newstartpos;
    		return false;
    	}
    public:
    	int jump(vector<int>& nums) {
    		if (nums.size() == 1)
    			return 0;
    		bool f = false;
    		vector<int>startpos;
    		set<int>history;
    		startpos.push_back(0);
    		int k = 0;
    		while (!f)
    		{
    			f = jump_once(nums, startpos, history);
    			k++;
    		}
    		return k;
    	}
    };

accepted

发表评论取消回复

表情：

评论列表（有 0 条评论，22人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 45. Jump Game II (贪心)

目描述：每个点的数字代表可以从当前节点跳跃最远的节点数，比如 \[ 2, 3, 1, 1, 4 \] 第一个节点跳跃最远位置就是下标为2的第三个元素。求跳到最后一...

蔚落/ 2024年04月18日 11:01/ 0 赞/ 67 阅读

相关图解LeetCode：Jump Game II

在[上一篇文章中][Link 1]我们看到了Jump Game这道算法题，这个题目还有第二问，这就是LeetCode中的第45号题目，Jump Game II，题目还是给定一个

旧城等待，/ 2022年12月31日 03:28/ 0 赞/ 185 阅读

相关 leetcode 45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index

﹏ヽ暗。殇╰゛Y/ 2022年08月21日 04:44/ 0 赞/ 23 阅读

相关 LeetCode45——Jump Game II

LeetCode45——Jump Game II 题意：在一串序列中，每个索引对应的value表示你能跳的最大步数。你在任何索引处可以跳\[1,value\]步，求跳

刺骨的言语ヽ痛彻心扉/ 2022年08月09日 12:41/ 0 赞/ 22 阅读

相关 LeetCode 55/45 Jump Game I/II-----Greedy**

一：[Jump Game][] 题目： Given an array of non-negative integers, you are initially positio

ゝ一世哀愁。/ 2022年08月07日 12:47/ 0 赞/ 33 阅读

相关 LeetCode 45.Jump Game II (跳跃游戏II)

题目描述: 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

约定不等于承诺〃/ 2022年05月11日 04:16/ 0 赞/ 215 阅读

相关 45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index

妖狐艹你老母/ 2022年03月21日 11:10/ 0 赞/ 175 阅读

相关【Leetcode】45. Jump Game II（动态规划）

Given an array of non-negative integers, you are initially positioned at the first index

待我称王封你为后i/ 2022年02月25日 01:57/ 0 赞/ 217 阅读

相关 45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first i

客官°小女子只卖身不卖艺/ 2022年02月16日 19:47/ 0 赞/ 196 阅读

相关 45. Jump Game II

description: Given an array of non-negative integers, you are initially positioned at

╰半橙微兮°/ 2021年11月01日 04:46/ 0 赞/ 268 阅读