Leetcode 55. Jump Game
13 Jul 2024leetcode medium array leetcode-top-interview Leetcode Top Interview 150 的其中一題
題目描述
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
範例
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Constraints:
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 10^5
解法
專注於我們目前能到達的最遠 index 。從前面哪個 index 到這個最遠的index並不重要。
從 index 0 開始遍歷 nums，使用 canArrive 變數來記錄我們能到達的最遠 index。如果 i + nums[i] > canArrive，這表示我們可以到達更遠的 index，更新canArrive的值。如果 i < canArrive，這表示我們無法抵達剩餘的index，返回 false。
func maximumGain(s string, x int, y int) int {
remove := func(str string, removestr string, val int) int {
count := 0
stack := make([]byte, 0)
for i:=0; i<len(str); i++ {
stack = append(stack, str[i])
l := len(stack)
if l >= 2 && stack[l-1]==removestr[1] && stack[l-2]==removestr[0] {
count += val
stack = stack[:l-2]
}
}
s = string(stack)
return count
}
if x > y {
return remove(s, "ab", x) + remove(s, "ba", y)
} else {
return remove(s, "ba", y) + remove(s, "ab", x)
}
return 0
}
Time complexity : O(n) Space complexity : O(1)