前端积累

# 45 题跳跃游戏 2

# 题目链接

# 难度：中等

# 思路分析：

贪心

# 想

# 一

# 想

# 再

# 看

# 答

# 案

# 想

# 一

# 想

# 再

# 看

# 答

# 案

# 代码：

贪心

var jump = function(nums) {
	let step = 0
	let jumpMax = 0 // 预计最远距离
	let last_canJumpMax = 0 // 上次可跳的最远距离
	for (let i = 0; i < nums.length - 1; i++) {
		const nowMax = nums[i] + i // 当前最远距离
		jumpMax = Math.max(jumpMax, nowMax) // 下一步最远距离
		// 上次跳跃后 下一步的最远距离 需要再跳
		if (last_canJumpMax === i) {
			last_canJumpMax = jumpMax // 最远距离更新
			step++ // 步数更新
		}
		// 最远距离超过终点
		if (last_canJumpMax >= len - 1) {
			break
		}
	}
	return step
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

递归

function jump(nums) {
	let num = nums[0] // 初始能跳的步数
	if (nums.length === 1) return 0
	let total = 0 // 总共跳几次
	let everOne = [num] // 每次经过的地方
	function jumpOne(newNums, oneNum) {
		let maxNum = 0 // 最远能跳多远
		let maxIndex = oneNum // 预设最大值
		if (oneNum + 1 >= newNums.length) {
			// 步数已经足够到达最后一个位置
			maxIndex = newNums.length - 1
		} else {
			// 每个点都跳一遍
			for (let i = 1; i <= oneNum; i++) {
				// 当前已跳步数大于 之前缓存的最大步数 更新最远距离
				if (i + newNums[i] >= maxNum) {
					maxNum = newNums[i] + i // 最远能跳多远
					maxIndex = i // 最远跳的目标位置
				}
			}
		}
		total++ // 当前跳跃次数
		everOne.push(newNums[maxIndex]) // 每次到达的位置
		if (maxIndex !== newNums.length - 1) {
			newNums.splice(0, maxIndex) // 清除已跳的元素
			jumpOne(newNums, newNums[0])
		}
	}
	jumpOne(nums, num)
	return total
}
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

# 鼓励我一下：

觉得还不错的话，给我的项目点个star吧

# 点个Star支持我一下~

← 867 题转置矩阵 →