Joyce' Blog
0%

jump-game-ii

发表于

题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

题解

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int jump(vector<int>& nums) {
	//贪心算法
	if (nums.size() == 1)return 0;
	int reach = 0, nextreach = nums[0], steps = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		int t = nums[i] + i;
		if (t > nextreach)nextreach = t;//尽量走得远
		if (nextreach >= nums.size() - 1) return steps+1;
		if (i == reach)
		{
			reach = nextreach;//可跳
			steps++;
		}
	}
	return steps;
}

图的广度优先遍历可以找到某节点到所有节点最少步数，图的深度优先遍历可以找到无环图的拓扑结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int jump(vector<int>& nums) {
	//bfs
	int steps = 0;
	int start = 0, end = 0;
	int max;
	while (end < nums.size() - 1)
	{
		max = end;
		for (int i = start; i <= end; i++)
		{
			int t = i + nums[i];
			if (max < t) max = t;
		}
		start = end + 1;//往前走一步
		end = max;
		steps++;
	}
	return steps;
}

为什么大家的代码这么简洁。

我是渣渣。