网站建设的建议和意见,深圳网站设计公司的,短视频动画制作,找别人做公司网站第一步做什么给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处:
0 j nums[i] i j n 返回到达 nums[n - 1] 的最…给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:
0 j nums[i] i j n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。 int jump(std::vectorint nums) {int n nums.size();int jumps 0;int reach 0;int nextReach 0;for (int i 0; i n - 1; i) {nextReach std::max(nextReach, i nums[i]);if (i reach) {reach nextReach;jumps;}}return jumps;
}使用贪心算法来解决。jumps 变量用于记录跳跃的次数维护两个变量当前能够到达的最远位置reach和当前步数内能够到达的最远位置nextReach。通过遍历数组并更新这两个变量最终可以得到到达终点的最小跳跃次数。
时间复杂度为 O(n)其中 n 为数组 nums 的长度。由于只需对数组进行一次线性遍历因此时间复杂度为 O(n)。
空间复杂度为 O(1)因为算法只使用了固定数量的额外变量jumps、reach 和 nextReach并不随着输入规模的增大而增加额外的空间消耗因此空间复杂度为 O(1)。
