网站建设主机耗电量,淘宝网页版手机登录,做网站获取手机号码,做网站的最大的挑战是什么文章目录 买卖股票思路一#xff1a;贪心代码#xff1a; 思路#xff1a;动态规划代码#xff1a; 跳跃游戏思路#xff1a;贪心找最大范围代码#xff1a; 跳跃游戏②思路#xff1a;代码#xff1a; 方法二#xff1a;处理方法一的特殊情况 买卖股票 思路一#x… 文章目录 买卖股票思路一贪心代码 思路动态规划代码 跳跃游戏思路贪心找最大范围代码 跳跃游戏②思路代码 方法二处理方法一的特殊情况 买卖股票 思路一贪心 代码
// 贪心思路
class Solution {public int maxProfit(int[] prices) {int result 0;for (int i 1; i prices.length; i) {//如果为正result Math.max(prices[i] - prices[i - 1], 0);}return result;}
//或者
class Solution {public int maxProfit(int[] prices) {int res0;for(int i1;iprices.length;i){//如果递增if(prices[i]prices[i-1]){resprices[i]-prices[i-1];}}return res;}
}思路动态规划 代码
class Solution {public int maxProfit(int[] prices) {int[][] dpnew int[prices.length][2];dp[0][0]-prices[0];dp[0][1]0;for (int i 1; i prices.length; i) {dp[i][0]Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]Math.max(dp[i-1][1],dp[i-1][0]prices[i]);}return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);}
}跳跃游戏 思路贪心找最大范围 代码
class Solution {public boolean canJump(int[] nums) {if (nums.length 1) {return true;}//覆盖范围, 初始覆盖范围应该是0因为下面的迭代是从下标0开始的int cover0;//在覆盖范围内更新最大的覆盖范围for(int i0;icover;i){coverMath.max(cover,inums[i]);//cover当前步数覆盖范围 inums[i]扩展范围if(covernums.length-1)return true;}return false;}
}跳跃游戏② 思路 记录这一步的最大覆盖范围在这个覆盖范围里去找里面包含的下一步能达到的最大覆盖范围。按照最大覆盖范围去跳次数就会最少。 每找到一次覆盖范围则相当于跳跃了一次
代码
遇到终点则停止
class Solution {public int jump(int[] nums) {if (nums.size() 1) return 0;//单一数组int curdis0; // 当前覆盖最远距离下标int nextdis0; // 下一步覆盖最远距离下标int ans0; // 记录走的最大步数for (int i 0; i nums.length; i) {nextdisMath.max(nextdis,inums[i]);// 更新下一步覆盖最远距离下标if(icurdis){ // 遇到当前覆盖最远距离下标ans;curdis nextdis;if(nextdisnums.length-1)break;}}return ans;}
}方法二处理方法一的特殊情况
// 版本二
class Solution {public int jump(int[] nums) {int result 0;// 当前覆盖的最远距离下标int curdis 0;// 下一步覆盖的最远距离下标int nextdis 0;for (int i 0; i nums.length - 1; i) {nextdis Math.max(nextdis, i nums[i]);// 可达位置的改变次数就是跳跃次数if (i curdis) {curdis nextdis;result;}}return result;}
}
