网站集约化建设需求,自媒体平台注册方法,公司网页制作培训试题,高企达建设有限公司网站JAVA代码编写
122. 买卖股票的最佳时机 II
给你一个整数数组 prices #xff0c;其中 prices[i] 表示某支股票第 i 天的价格。
在每一天#xff0c;你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买#xff0c;然后在 同一天 出售…JAVA代码编写
122. 买卖股票的最佳时机 II
给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1
输入prices [7,1,5,3,6,4]
输出7
解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4 。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3 。总利润为 4 3 7 。示例 2
输入prices [1,2,3,4,5]
输出4
解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4 。总利润为 4 。示例 3
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 交易无法获得正利润所以不参与交易可以获得最大利润最大利润为 0 。提示
1 prices.length 3 * 1040 prices[i] 104
教程https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html
方法一贪心
思路每一天只能进行买和卖但是只有先买才能卖。最多只能持有一股股票。贪心算法只收集每天的正利润。
class Solution {public int maxProfit(int[] prices) {int profit0;for(int i 0; i prices.length-1; i){int v prices[i1]-prices[i];if(v0){profit v;}}return profit;}
}55. 跳跃游戏 给你一个非负整数数组 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
教程https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html
方法一贪心
思路贪心算法局部最优解每次取最大跳跃步数取最大覆盖范围整体最优解最后得到整体最大覆盖范围看是否能到终点。
class Solution {public boolean canJump(int[] nums) {if (nums.length 1) {return true;}//覆盖范围, 初始覆盖范围应该是0因为下面的迭代是从下标0开始的int coverRange 0;//在覆盖范围内更新最大的覆盖范围for (int i 0; i coverRange; i) {coverRange Math.max(coverRange, i nums[i]);if (coverRange nums.length - 1) {return true;}}return false;}
}45. 跳跃游戏 II
给定一个长度为 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]。
示例 1:
输入: nums [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。示例 2:
输入: nums [2,3,0,1,4]
输出: 2提示:
1 nums.length 1040 nums[i] 1000题目保证可以到达 nums[n-1]
教程https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html
方法一贪心
思路其精髓在于控制移动下标 i 只移动到 nums.size() - 2 的位置所以移动下标只要遇到当前覆盖最远距离的下标直接步数加一不用考虑别的了。
class Solution {public int jump(int[] nums) {int result 0;// 当前覆盖的最远距离下标int end 0;// 下一步覆盖的最远距离下标int temp 0;for (int i 0; i end end nums.length - 1; i) {temp Math.max(temp, i nums[i]);// 可达位置的改变次数就是跳跃次数if (i end) {end temp;result;}}return result;}public static void main(String[] args) {Solution solution new Solution();solution.jump(new int[] {2,3,1,1,4});}
}