龙泉市建设局网站,深圳条幅制作,wordpress admin_menu,做一个网站的总结Day28122.买卖股票的最佳时机II力扣题目链接给定一个数组#xff0c;它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易#xff08;多次买卖一支股票#xff09;。注意#xff1a;你不能同时参与多笔交易…Day28122.买卖股票的最佳时机II力扣题目链接给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。思路对[7,1,5,3,6,4]举例分析第二天买入第三天卖出第四天买入第五天卖出这样利润最高为7利润是什么最终利润是可以分解的假如第0天买入第3天卖出那么利润为prices[3] - prices[0]。相当于(prices[3] - prices[2]) (prices[2] - prices[1]) (prices[1] - prices[0])。思路是这样的我们可以设置一个新数组profit用来标记原数组相邻两个元素的差profit [-6 4 -2 3 -2]元素为正数的地方这两个时间点间持有股票有收益可以在区间两侧把股票卖出因此最大利润其实就是profit数组正数元素的和如果没有正数元素说明一直在跌利润就是0其实我们需要收集每天的正利润就可以收集正利润的区间就是股票买卖的区间而我们只需要关注最终利润不需要记录区间。那么只收集正利润就是贪心所贪的地方局部最优收集每天的正利润全局最优求得最大利润。时间复杂度O(n)空间复杂度代码class Solution {public int maxProfit(int[] prices) {int[] profit new int[prices.length - 1];//新建一个profit数组int res 0;for (int i 0; i profit.length; i) {profit[i] prices[i 1] - prices[i];//计算profit数组每个元素值if (profit[i] 0) res profit[i];//如果大于零就加到res中}return res;}
}
//优化不需要设置新数组
class Solution {public int maxProfit(int[] prices) {int res 0;for (int i 0; i prices.length - 1; i) {res Math.max(0,prices[i 1] - prices[i]);}return res;}
}55. 跳跃游戏力扣题目链接给定一个非负整数数组你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。思路我们想看能不能到达最后一个位置其实就是考虑一个覆盖度能不能覆盖到最后一个元素如果可以覆盖到不用管怎么跳的肯定能跳到问题转化为跳跃覆盖范围究竟可不可以覆盖到终点所以我们遍历数组注意不是全部遍历完因为你全部遍历完了更新的时候一定能走到最后一个元素我们只遍历0到coverRange这一部分每遍历一个元素对coverRange进行更新一旦发现能走到最后一个元素位置就退出循环因为如果不退出的话coverRange变大数组会越界如果循环结束了还没有返回那说明走不到最后一个元素的位置返回false即可贪心算法局部最优解每次取最大跳跃步数取最大覆盖范围整体最优解最后得到整体最大覆盖范围看是否能到终点。时间复杂度O(n)空间复杂度O(1)这个题注意不能全力跳因为可能会错失使得覆盖范围变大的一些元素代码class Solution {public boolean canJump(int[] nums) {int coverRange 0;//最开始只能覆盖0位置元素for (int i 0; i coverRange; i) {//只遍历到coverRangecoverRange Math.max(coverRange,nums[i] i);//每次对能覆盖的范围进行更新if (coverRange nums.length - 1) return true;//如果某次发现能走到最后一个位置了就赶紧返回防止下标越界}return false;//循环结束还没有返回说明走不到最后一个位置返回false}
}45.跳跃游戏II力扣题目链接给定一个非负整数数组你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。思路我们要找到能跳到终点位置的最小次数使用curCover来记录这一步能覆盖的最大范围使用nextCover来记录下一步能覆盖的最大范围遍历数组每遍历一个元素都对nextCover进行更新如果遍历到这一步能覆盖的最大范围了就是curCover了那就要看看有没有到达终点如果到达了就直接break返回res如果到达这一步最大覆盖范围但还没有到达终点那这一步肯定跳不到了就进行更新给它加加油再继续遍历代码class Solution {public int jump(int[] nums) {int curCover 0;int nextCover 0;int res 0;for (int i 0; i nums.length; i){nextCover Math.max(nextCover,nums[i] i);//不断进行遍历更新下一步能覆盖的范围if (i curCover){//走到了这一步覆盖范围的终点if (i nums.length - 1) break;//如果到了末尾就breakres;//没有到步数加一curCover nextCover;//更新curCover看下一步能不能到}}return res;}
}
