代码随想录day32

122.买卖股票的最佳时机 II

● 力扣题目链接
● 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
● 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
● 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路

● 价格有一个价格数组，前后两天的价格差构成利润数组，我们把利润数组中所有大于零的元素加和即可

代码

class Solution {public int maxProfit(int[] prices) {if (prices.length == 1) return 0;int profit = 0;int[] pro = new int[prices.length - 1];for (int i = 0; i < pro.length; i++) {pro[i] = prices[i + 1] - prices[i];if (pro[i] > 0) profit += pro[i];}return profit;}
}

55. 跳跃游戏

思路

● 遍历覆盖范围，在此期间不断更新覆盖范围，一旦覆盖了末尾，就返回true

代码

class Solution {public boolean canJump(int[] nums) {int cover = 0;for (int i = 0; i <= cover; i++) {cover = Math.max(cover, i + nums[i]);if (cover >= nums.length - 1) return true;}return false;}
}

45.跳跃游戏 II

● 力扣题目链接
● 给定一个非负整数数组，你最初位于数组的第一个位置。
● 数组中的每个元素代表你在该位置可以跳跃的最大长度。
● 你的目标是使用最少的跳跃次数到达数组的最后一个位置。

思路

● 记录当前位置和下一步最大位置

代码

class Solution {public int jump(int[] nums) {int count = 0;int curDistance = 0;int nextDistance = 0;for (int i = 0; i < nums.length; i++) {nextDistance = Math.max(nextDistance, nums[i] + i);if (nextDistance >= nums.length - 1) {count++;break;}if (i == curDistance) {curDistance = nextDistance;count++;}}return count;}
}