跳跃游戏- Leetcode
下面是我对LeetCode跳跃游戏的解决方案
给定一个非负整数数组，您最初定位在数组的第一个索引处。数组中的每个元素表示该位置的最大跳转长度。确定是否能够达到最后一个索引。
示例1：
输入：2,3,1,1,4输出: true
这是我的解决方案。对于包含25000个元素的数组，它是正确的，但是超时了LeetCode代码检查器。
有谁能帮我改进这段代码吗？
它的时间复杂度为O(N^2)，空间复杂度为O(N)。我找不到比O(N^2)更快的方法。
def function(nums):
if len(nums) == 1:
return True
output = [0] * len(nums)
last_index = len(nums) - 1
output[0] = 1
for index, number in enumerate(nums):
if output[index] == 0:
continue
if output[index] == 1:
stop_at = min(last_index, index + number)
for i in range(index, stop_at + 1):
output[i] = 1
if output[last_index] == 1:
return True
return False
if __name__ == "__main__":
nums = [3,2,1,0,4]
output = function(nums)
print(output)回答 2
Code Review用户
发布于 2019-07-10 06:15:58
O(n)溶液
你不需要跟踪所有你能到达的地方。您只需要知道您可以达到的最高索引是什么，因为您可以通过选择较短的跳转来达到任何较低的索引。将列表从0扫描到末尾，跟踪最大可达索引。如果您到达的索引大于最大可达索引，则您已经到达一个块，无法到达终点。
例如，对于跳转列表= 3，2，1，4。从指数0开始，我们可以达到0+ 3 = 3，从指数1可以达到1+ 2 = 3，从2可以达到2+1 = 3，从指数3可以达到3，到目前为止最大可达指数是3，所以当我们达到指数4，4>3时，索引4是不可达的，我们不能到达终点。
def canjump(nums):
maximum_reachable_index = 0
for index, max_jump in enumerate(nums):
#print(f"{index}", end=' ')
if index > maximum_reachable_index:
#print(f"> {maximum_reachable_index} and is unreachable.")
return False
#print(f"+ {max_jump} => {index + max_jump} : {maximum_reachable_index} ")
maximum_reachable_index = max(index + max_jump, maximum_reachable_index)
return True取消对打印语句的注释以查看它是如何工作的。
Code Review用户
发布于 2019-07-06 13:04:26
编码风格
您的代码通过PEP8 online检查时没有错误或警告，这很好。
命名
函数名function是非常非描述性的。Leetcode模板使用canJump，但根据Python PEP 8
函数名应该是小写，必要时用下划线分隔单词，以提高可读性。
那将是can_jump。您的output数组存储从初始位置可到达的位置，更好的名称可能是reachable。index是当前位置，number是该位置的跳转宽度。
编码改进
output/reachable数组应该是布尔值的数组，而不是整数。测试
if output[index] == 0:
continue不需要，而且测试
if output[last_index] == 1:
return True只需要在可到达的位置完成。总结到目前为止的建议，我们已经
def can_jump(nums):
if len(nums) == 1:
return True
reachable = [False] * len(nums)
last_pos = len(nums) - 1
reachable[0] = True
for pos, jump_width in enumerate(nums):
if reachable[pos]:
stop_at = min(last_pos, pos + jump_width)
for i in range(pos, stop_at + 1):
reachable[i] = True
if reachable[last_pos]:
return True
return False性能改进
关键的观察是，可到达位置列表总是一个间隔(从位置0到某个最大可达位置)。这个间隔可以用一个整数变量来描述。
last_reachable = 0在遍历数组时对其进行更新。我不会剥夺您对自己编写解决方案的满意程度，因此我只想提一下一般的想法。枚举数组时：
- 如果无法到达当前位置，则返回
False。 - 否则，使用当前值的最大值和从当前位置可到达的最大位置更新
last_reachable。 - 当最终位置确定为可到达时，立即返回
True。
这种方法需要更少的内存(不需要额外的数组)，只需要一个简单的循环而不是嵌套的循环。
https://codereview.stackexchange.com/questions/223612
复制相似问题
腾讯云开发者
