刷题记录——跳跃游戏

第一道题地址:
leetcode-jump-1
第二道题地址:
leetcode-jump-2

题目一

image.png

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def canJump(self, nums: List[int]) -> bool:
long = len(nums)
if long == 1: # 数组中只有一个数的时候,默认True
return True

max_jump = 0 # 跳跃最远的距离
for i in range(long):
temp = i + nums[i]
if temp > max_jump: # 该点跳跃距离,更新最远距离
max_jump = temp
if (nums[i] == 0) & (i == max_jump) & (i < long - 1): # 中途停止更新下一条的条件
return False

return True # 其他情况都可以为真

结果:内存beat 8.31%
image.png

题目二

image.png

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def jump(self, nums: List[int]) -> int:

long = len(nums)
jump, max_jump, end = 0, 0, 0
for i in range(long - 1):
if max_jump >= i:
# 更新值
max_jump = max(max_jump, i + nums[i])
# 跳
if i == end:
jump += 1
end = max_jump
return jump

这道题最开始想得太复杂,想每一步怎么跳,跳到哪里,更新那些值。看了题解之后,才知道其实不用这么麻烦,只用判断i的落点,如果和上一次跳完更新的end值相等,可以再一次跳。


----本文结束啦感谢您阅读----

欢迎关注我的其它发布渠道