广州专业网站建设性价比高,wordpress自动生成缩略图,wordpress经常打不开,wordpress 代码 工具122.买卖股票的最佳时机II 本题中理解利润拆分是关键点#xff01; 不要整块的去看#xff0c;而是把整体利润拆为每天的利润。假如第 0 天买入#xff0c;第 3 天卖出#xff0c;那么利润为#xff1a;prices[3] - prices[0]。
相当于(prices[3] - prices[2]) (prices[…122.买卖股票的最佳时机II 本题中理解利润拆分是关键点 不要整块的去看而是把整体利润拆为每天的利润。假如第 0 天买入第 3 天卖出那么利润为prices[3] - prices[0]。
相当于(prices[3] - prices[2]) (prices[2] - prices[1]) (prices[1] - prices[0])。
一旦想到这里了很自然就会想到贪心了即只收集每天的正利润最后稳稳的就是最大利润了。
class Solution {public int maxProfit(int[] prices) {int result0;for(int i1;iprices.length;i){if(prices[i]-prices[i-1]0){result(prices[i]-prices[i-1]);}}return result;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
55. 跳跃游戏 本题的思路是不断更新覆盖范围而不去纠结具体跳了几步。 局部最优每次取最大的覆盖范围 全局最优最终能覆盖的最大范围
class Solution {public boolean canJump(int[] nums) {int cover0;if(nums.length1) return true;for(int i0;icover;i){coverMath.max(inums[i],cover);if(covernums.length-1) return true;//一旦到达终点了直接return true}return false;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
45.跳跃游戏II 本题的思路在于每走一步都取能达到的最远位置。这就需要记录当前步的最远位置和下一步的最远位置每当达到当前步的最远位置直接走一步并且把当前步的最远位置更新成下一步的最远位置继续寻找下一步的最远位置知道当前步的最远位置大于等于终点位置。
class Solution {public int jump(int[] nums) {if(nums.length1) return 0;int nextMax0;//记录下一步的最远位置int cur0;//记录当前步的最远位置int step0;//记录最终的结果for(int i0;inums.length;i){nextMaxMath.max(nextMax,inums[i]);if(icur){curnextMax;step;//向前走一步if(curnums.length-1) break;//如果走的这一步可以到达终点直接break}}return step;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
