做网站和微信小程序,电子商务网站建设与管理的背景,wordpress注册界面,wordpress用户登录后#x1f3c6;作者简介#xff0c;普修罗双战士#xff0c;一直追求不断学习和成长#xff0c;在技术的道路上持续探索和实践。 #x1f3c6;多年互联网行业从业经验#xff0c;历任核心研发工程师#xff0c;项目技术负责人。 #x1f389;欢迎 #x1f44d;点赞✍评论… 作者简介普修罗双战士一直追求不断学习和成长在技术的道路上持续探索和实践。 多年互联网行业从业经验历任核心研发工程师项目技术负责人。 欢迎 点赞✍评论⭐收藏 算法领域知识
链接专栏分发糖果算法专栏买卖股票的最佳时机算法专栏跳跃游戏算法专栏 经典算法题 之 买卖股票的最佳时机 题目如下
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 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 1040 nums[i] 105 解答这道题可以使用 贪心算法 进行解决。 为了判断是否能够到达最后一个下标我们可以使用贪心算法的思想来实现。贪心算法的基本思想是每一步都选择当前能够跳跃最远的位置。
具体实现逻辑如下
初始化一个变量 maxPosition 为 0表示当前能够跳跃的最远位置。遍历数组 nums对于当前位置 i判断是否超过了当前能够跳跃的最远位置 maxPosition如果超过了则说明无法到达最后一个下标返回 false。更新 maxPosition 为当前位置 i 和当前位置能够跳跃的最大长度之和中的较大值。如果最后 maxPosition 大于等于数组的最后一个下标即 nums.length - 1则说明能够到达最后一个下标返回 true否则返回 false。
以下是用Java代码实现的示例
public class Solution {public boolean canJump(int[] nums) {int maxPosition 0;for (int i 0; i nums.length; i) {if (i maxPosition) {return false;}maxPosition Math.max(maxPosition, i nums[i]);}return maxPosition nums.length - 1;}
}public class Main {public static void main(String[] args) {Solution solution new Solution();int[] nums {2, 3, 1, 1, 4};boolean result solution.canJump(nums);System.out.println(result); // 输出 trueint[] nums2 {3, 2, 1, 0, 4};boolean result2 solution.canJump(nums2);System.out.println(result2); // 输出 false}
}在上面的代码中我们首先定义了一个 Solution 类其中包含了 canJump 方法用于判断是否能够到达最后一个下标。然后在 Main 类的 main 方法中我们创建了一个 Solution 对象并对示例数组 nums 和 nums2 分别调用 canJump 方法并打印出结果。
执行过程如下
首先将 nums 传入 canJump 方法中。在 canJump 方法中初始化 maxPosition 为 0。进入循环此时 i 为 0判断是否超过了 maxPosition因为初始时 maxPosition 为 0所以不超过。更新 maxPosition 为 0 和 i nums[i] 的较大值即 0 和 2所以 maxPosition 更新为 2。继续下一轮循环此时 i 为 1判断是否超过了 maxPosition因为此时 i 为 1而 maxPosition 为 2所以不超过。更新 maxPosition 为 2 和 i nums[i] 的较大值即 2 和 1 3所以 maxPosition 更新为 4。继续下一轮循环此时 i 为 2判断是否超过了 maxPosition因为此时 i 为 2而 maxPosition 为 4所以不超过。更新 maxPosition 为 4 和 i nums[i] 的较大值即 4 和 2 1所以 maxPosition 仍然为 4。继续下一轮循环此时 i 为 3判断是否超过了 maxPosition因为此时 i 为 3而 maxPosition 为 4所以不超过。更新 maxPosition 为 4 和 i nums[i] 的较大值即 4 和 3 1所以 maxPosition 仍然为 4。继续下一轮循环此时 i 为 4判断是否超过了 maxPosition因为此时 i 为 4而 maxPosition 为 4所以不超过。更新 maxPosition 为 4 和 i nums[i] 的较大值即 4 和 4 4所以 maxPosition 更新为 8。循环结束因为 maxPosition 大于等于数组的最后一个下标即 4所以返回 true。
对于示例数组 nums2执行过程类似只是在第四步时 maxPosition 更新为 3此时无法到达最后一个下标因此返回 false。
通过这个示例题目你可以练习使用贪心算法来解决实际问题并且可以加深对Java代码实现的掌握。希望这个例子能够帮助你更好地理解算法和数据结构的基本原理和应用。 关注作者普修罗双战士给你不一样的技术体验一起在技术领域扶摇直上九万里共筑坚如磐石的权。 欢迎 点赞✍评论⭐收藏
