跳跃游戏II的Python程序
跳跃游戏II的Python程序
提问于 2019-05-23 14:15:15
这是一个Leetcode问题：
给定一个非负整数数组，您最初定位在数组的第一个索引处。数组中的每个元素表示该位置的最大跳转长度。您的目标是达到最小跳数中的最后一个索引。注意：您可以假设始终可以达到最后一个索引。
以下是我对这个问题的第一个解决方案：
def jump(nums):
n = len(nums)
curr_far = min(nums[0], n - 1)
next_far = 0
step = 0
for i in range(n):
if i <= curr_far:
if next_far < i + nums[i]:
next_far = min(i + nums[i], n - 1)
if i == curr_far and curr_far != 0:
curr_far = next_far
step += 1
return step
nums = #Enter a list.
print(jump(nums))以下是输入/输出的示例：
nums = [2,3,1,1,4]
>>> 2达到最后一个索引的最小跳数是2。
从索引0跳转1步到1，然后跳到最后一个索引。
以下是我对这个问题的第二个解决方案：
class Solution:
def __init__(self, nums):
self.nums = nums
def jump(self, nums):
if not nums or len(nums) == 1:
return 0
curr = 0
count = 0
while(curr < len(nums)):
maxReach = -1
index = 0
for i in range(1, nums[curr] + 1):
if curr + i >= len(nums) - 1:
return count + 1
else:
if nums[curr + i] + i > maxReach:
maxReach = nums[curr + i] + i
index = curr + i
curr = index
count += 1
nums = #Enter a list.
game = Solution(nums)
print(game.jump(nums))输入/输出-与上述相同。
因此，我想对这两个程序的效率进行代码审查。
任何帮助都将不胜感激。
回答 2
Code Review用户
回答已采纳
发布于 2019-05-23 21:02:20
改进第一个解决方案
我更喜欢第一个解决方案，因为我发现它更容易理解它是如何工作的，而且它更短。
可能会简单一点。条件if i <= curr_far:是不必要的，可以安全地丢弃。
我的窍门是使用enumerate，而不是迭代一系列索引，如下所示：
for index, value in enumerate(nums):这样，您就可以直接使用nums[index]，而不是循环体中的value。
另一个代码气味是在循环的每一次迭代中执行的条件if i == curr_far and curr_far != 0，即使curr_far != 0只在第一次迭代中为false，否则总是正确的。
我不喜欢大多数可变的名字..。
- 而不是
step，我会发现jumps更自然 - 而不是
curr_far和next_far，我会发现reach和next_reach更直观
总之，我会这样写：
class Solution(object):
def jump(self, nums):
end = len(nums) - 1
if not end:
return 0
reach = 0
next_reach = 0
jumps = 0
for pos, value in enumerate(nums):
if next_reach < pos + value:
next_reach = pos + value
if next_reach >= end:
return jumps + 1
if pos == reach:
reach = next_reach
jumps += 1问题与第二个解决方案
- 看起来比第一个更复杂，我认为这是不必要的。
__init__方法是完全不必要的- 在
while(curr < len(nums)):中，外部括号是不必要的 - Python中变量命名方式的约定是
snake_case，而不是camelCase。
Code Review用户
发布于 2019-05-24 10:28:41
这个问题有一个递归的解决方案。你想要一个递归算法
- 如果输入数组的长度为
0，则返回1。 - 否则，为从
1到nums[0]的大小跳转创建一个新的输入数组，计算新输入数组的跳转，添加1，并返回最小值。
在Python中，这将是：
def jump(nums):
if len(nums)<=1:
return 0
else:
return min(1+jump(nums[m:]) for m in range(1,min(len(nums),nums[0]+1)))页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/220838
复制相关文章
相似问题
腾讯云开发者
