lulaalu

字数

470 字

阅读时间

3 分钟

题意

给数组，初始在0号位置，可以跳 $n u m s [0]$ 步，最少多少次跳到最后

$1 \leq n u m s . l e n g t h \leq 10^{4}$
$0 \leq n u m s [i] \leq 1000$

解法1

暴力，复杂度是 $v a l u e s \times l e n g t h$ ， $1 e 7$ 不会超时

CPP

int t[N];
int jump(vector<int> &nums)
{
	int n = nums.size();
	for (int i = 0; i < n; i++)
		t[i] = 1e9;
	t[0] = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = min(i + 1, n - 1); j <= min(n - 1, i + nums[i]); j++)
		{
			t[j] = min(t[i] + 1, t[j]);
		}
	}
	return t[n - 1];
}

解法2

以 $[2, 3, 1, 2, 4, 2, 3]$ 为例，当前在0位置，一步可以跳到 $3, 1$ ,两步最远可以是先跳到3，再跳到4，下标是0->1->4,

那么如果贪心的考虑每次跳两步最远的区域，那么第三步可选的区域就更大，

举例来说，第一步如果选跳到下标1，那么第二步可以选择的区域是下标 $[0, 1, 2, 3, 4]$

如果第一步选择跳到下标2，那么第二步可以选择的区域是于下标 $[0, 1, 2]$

重点：两步能到达的区域大小不同，第三步能到达的区域大小一定也不同

所以选择能使下下步有更多选择的下一步

所以代码实现时遍历一遍nums，不过要动态维护一个边界end

比如说刚开始这个边界就是2，因为最远能跳到下标2

接下来遍历1到2，发现现在能到达的最远下标maxPos是4

在遍历到end时，step++，并且将end=maxPos

再继续从原本的end+1遍历到新的end

CPP

int jump(vector<int> &nums)
{
	int n = nums.size();
	int maxPos = 0, end = 0, step = 0;
	for (int i = 0; i < n - 1; i++)
	{
		maxPos = max(maxPos, i + nums[i]);
		if (i == end)
		{
			end = maxPos;
			step++;
		}
	}
	return step;
}

贡献者

lulaalu

文件历史

最后编辑于 22 天前查看完整历史

题意 ​

解法1 ​

解法2 ​

贡献者 ​

文件历史 ​

题意

解法1

解法2

贡献者

文件历史