跳转游戏2 leetcode:同时循环不终止
跳转游戏2 leetcode:同时循环不终止
提问于 2022-11-15 21:19:03
给您一个长度为n的整数num的0索引数组，您最初定位在num。
每个元素numsi表示从索引i向前跳的最大长度。换句话说，如果您在numsi，您可以跳到任意numsi +j，其中：
0 <= j <= numsi和i+j
示例1：
输入:num= 2,3, 1，1,4输出: 2解释:到达最后一个索引的最小跳数是2，从索引0跳1步，然后跳到最后一个索引。示例2：
投入: nums = 2,3,0,1,4产出:2
我的解决方案：
class Solution:
def jump(self, nums: List[int]) -> int:
j = len(nums)-1
res = []
while j >= 0:
cursor = j
valid_j = j # this variable will hold the best value of j to be set
while cursor >= 0:
if nums[cursor] + cursor >= j:
valid_j = cursor
cursor-=1
res.append(valid_j)
j = valid_j
return len(res)
why循环中的任何一个都不会终止，我也无法找出原因。时间限制超过错误。请帮助解释错误。
谢谢!
回答 1
Stack Overflow用户
发布于 2022-11-15 22:20:46
您的while条件是错误的。这将永远是真的，因为j永远不会变成负面的。
在您的算法中，j的含义是必须从早期索引跳到的索引。但是绝不能跳到索引0，因为我们已经从那里开始实现了这个指数。
要解决这个问题，应该将while条件更改为j > 0。
应该指出的是，这不是一个非常有效的解决方案，因为cursor反复读取列表中相同的值，使该算法的时间复杂度最差，为O(2)。
使用前向循环可以不使用嵌套循环来解决这个问题。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/74452297
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号