极客时间算法课笔记整理9——理论讲解+面试题实战:贪心算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了极客时间算法课笔记整理9——理论讲解+面试题实战:贪心算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1008字,纯文字阅读大概需要2分钟。
内容图文
![极客时间算法课笔记整理9——理论讲解+面试题实战:贪心算法](/upload/InfoBanner/zyjiaocheng/620/9e8b3432804f4f5cbc1f4c6f64b58ad0.jpg)
贪心算法
面试题
122. Best Time to Buy and Sell Stock II
我的方法:flag记录该买还是该卖,判断不同拐点的状态。模拟了真实的操作,但不是本题条件下的最简单的想法
class Solution {
public int maxProfit(int[] prices) {
int day = prices.length;
boolean flag=true;
if(day==1 || day==0){return 0;}
int buy=prices[0], sell=0, profit=0;
for (int i = 1; i<day;i++){
if(flag && prices[i]<prices[i-1]){
buy=prices[i];
}else if(flag && prices[i]>=prices[i-1]){
flag=false;
sell=prices[i];
}
if((!flag) && prices[i]>=prices[i-1]){
sell=prices[i];
}else if((!flag) && prices[i]<prices[i-1]){
flag=true;
profit+=sell-buy;
buy=prices[i];
}
}
if(!flag){
sell=prices[day-1];
profit+=sell-buy;}
return profit;
}
}
其他solution:
暴力求解法时间复杂度太高
Approach 2: Peak Valley Approach:
比我的方法节约了内存空间。
简单方法:利润是所有连续上升差值的和:
class Solution {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1])
maxprofit += prices[i] - prices[i - 1];
}
return maxprofit;
}
}
内容总结
以上是互联网集市为您收集整理的极客时间算法课笔记整理9——理论讲解+面试题实战:贪心算法全部内容,希望文章能够帮你解决极客时间算法课笔记整理9——理论讲解+面试题实战:贪心算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。