未分類

Jump Game

Array, Go, Greedy, LeetCode

Jump Game

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.

Determine if you are able to reach the last index.

For example:

1
2
3
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
提示 解題應用
Array Array/Slice
Greedy 規律觀查

Default:

1
2
3
func canJump(nums []int) bool {
}

解答思路:

一開始還以為陣列中的每個元素代表是一定要跳到該格的位置，而且在考慮往前或往後的情況下勢必要用遞回來處理，但再仔細看題目之後才發現是代表能跳躍的最大距離，並且觀查範例之後更進一步的發現到能不能跳到最後一格的位置最主要跟元素值為0有關係，只要前面任一個能跳躍的距離超過元素值為0的位置，表示便能繼續往下跳只達終點，所以只要一邊遍歷陣列一邊找出能跳躍到達的最大位置，遇到元素值為0的時候便判斷目前能到的最大位置是否超過0的位置，如果沒辦法超過就回傳false直到全數陣列遍歷結束才回傳true。

程式碼解說:

因為要一邊遍歷陣列一邊找出能跳躍到達的最大位置，所以一開始便直接遍歷整個陣列，如果碰上元素值為0的情況，便要檢查目前能到的最大位置是否超過0的位置，唯獨如果元素值為0的位置剛好就已經在陣列的最後一格便不需判斷(因為已經到達我們要的目標位置了!)，如果能到的最大位置沒辦法超過0的位置就直接回傳false，否則便繼續往下遍歷並且判斷每一次能跳躍到達的位置是否比目前能到達的最大位置大，如果是就將該位置取代最大位置，直到全數陣列遍歷結束(表示順利到達陣列最後一格的位置)才回傳true

1
2
3
4
5
6
7
8
9
10
var max int
for i, v := range nums {
	if v == 0 && i != len(nums)-1 && i >= max {
		return false
	}
	if i+v > max {
		max = i + v
	}
}
return true

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
func canJump(nums []int) bool {
	var max int
	for i, v := range nums {
		if v == 0 && i != len(nums)-1 && i >= max {
			return false
		}
		if i+v > max {
			max = i + v
		}
	}
	return true
}

總結:

一陣列中每個元素代表能跳躍的最大距離，要判斷是否最後能跳到陣列最後一格的位置，仔細觀查會發現到能不能跳到最後一格的位置最主要跟元素值為0有關係，只要前面任一個能跳躍的距離超過元素值為0的位置，表示便能繼續往下跳只達終點，所以只要一邊遍歷陣列一邊找出能跳躍到達的最大位置，遇到元素值為0的時候便判斷目前能到的最大位置是否超過0的位置，如果沒辦法超過就回傳false直到全數陣列遍歷結束才回傳true。

分享到