网站的横幅怎么做的济南网站建设费用

网站的横幅怎么做的,济南网站建设费用,广州白云区,seo优化顾问给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。示例 1#xff1a;输入你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标如果可以返回true否则返回false。示例 1输入nums [2,3,1,1,4]输出true解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2输入nums [3,2,1,0,4]输出false解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。提示1 nums.length 0 nums[i] 解题思路本题采用贪心算法通过维护【当前能到达的最远下标】来判断是否能到达终点时间复杂度为 O (n)仅遍历数组一次空间复杂度为 O (1)仅用常数额外空间初始化max_reach为 0表示初始时能到达的最远下标是 0遍历数组的每个下标i若当前下标i超过了max_reach说明无法到达该位置直接返回false更新max_reach为【当前max_reach】与【i nums[i]当前位置能跳到的最远下标】的较大值若max_reach已覆盖最后一个下标n-1直接返回true提前终止提升效率遍历结束后仅当数组长度为 1 时触发返回true。Python代码from typing import List class Solution: def canJump(self, nums: List[int]) - bool: 判断是否能从数组第一个位置跳到最后一个位置 :param nums: 整数数组nums[i] 表示在第 i 个位置可以跳跃的最大长度 :return: 能否到达最后一个位置布尔值 # 边界情况1数组为空直接返回False题目中nums通常非空仅做鲁棒性处理 if not nums: return False # 边界情况2数组只有1个元素已经在最后位置直接返回True if len(nums) 1: return True max_reach 0 # 记录当前能到达的最远下标 n len(nums) # 遍历数组无需遍历到最后一个元素因为只要能到达倒数第二个的最远覆盖最后一个即可 for i in range(n - 1): # 若当前下标超过了最远可达范围说明无法到达该位置更无法到终点 if i max_reach: return False # 更新最远可达范围当前位置能跳到的最远位置 当前下标 最大跳跃长度 max_reach max(max_reach, i nums[i]) # 提前终止若最远可达范围已覆盖最后一个下标直接返回True if max_reach n - 1: return True # 遍历结束后仍未覆盖最后一个下标返回False return False # ------------------- 测试用例 ------------------- if __name__ __main__: solution Solution() # 测试用例1正常可到达 nums1 [2, 3, 1, 1, 4] print(f测试用例1 [{nums1}]{true if solution.canJump(nums1) else false}) # 测试用例2无法到达卡在下标3 nums2 [3, 2, 1, 0, 4] print(f测试用例2 [{nums2}]{true if solution.canJump(nums2) else false}) # 测试用例3边界情况数组长度为1 nums3 [0] print(f测试用例3 [{nums3}]{true if solution.canJump(nums3) else false}) # 测试用例4边界情况第一个元素直接覆盖最后一个 nums4 [5, 1, 0, 0, 0] print(f测试用例4 [{nums4}]{true if solution.canJump(nums4) else false}) # 测试用例5全0数组长度1 nums5 [0, 0, 0] print(f测试用例5 [{nums5}]{true if solution.canJump(nums5) else false})LeetCode提交代码class Solution: from typing import List def canJump(self, nums: List[int]) - bool: max_reach 0 # 记录当前能到达的最远下标 n len(nums) for i in range(n): # 若当前下标超过了最远可达范围说明无法到达 if i max_reach: return False # 更新最远可达范围当前位置最大跳跃长度 max_reach max(max_reach, i nums[i]) # 若最远可达范围已覆盖最后一个下标直接返回true if max_reach n - 1: return True # 遍历完成后仅当数组长度为1时会走到这里 return True程序运行截图展示总结本文探讨了跳跃游戏问题的贪心算法解法。给定非负整数数组nums初始位于第一个下标每个元素表示可跳跃的最大长度。算法通过维护当前能到达的最远下标max_reach来判断是否能到达终点遍历数组时若当前下标超过max_reach则返回false否则更新max_reach为当前位置能跳到的最大距离。当max_reach覆盖终点时提前返回true。该方法时间复杂度O(n)空间复杂度O(1)高效解决了该问题。