leetcode刷题笔记
（1）Best Time to Buy and Sell Stock
Total Accepted: 10430 Total Submissions: 33800My Submissions
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
url：http://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/
测试用例：
空数组: []
只有一个元素的数组: [1]
所有收益均为负数的数组: [8,7,4,2]
这一题，首先使用的是暴力办法，中间做了一些局部优化，但是总体复杂度仍然是O（n2），于是乎，妥妥的Time Limit Exceeded，下面是暴力代码
public int maxProfit(int[] prices){
int i,j,max,temp,holda,holdb;
if(prices.length==0 || prices.length==1){
return 0;
}
temp = prices[0];
max = prices[1]-prices[0];
for(i=0;i<prices.length-1;i++){
if(prices[i]<temp){
temp = prices[i];
for(j=i;j<prices.length;j++){
if(prices[j]-prices[i]>max){
max = prices[j]-prices[i];
holda = i;
holdb = j;
}
}
}
}
return max;
}
既然TLE了，于是乎，就去想办法了。
可以得到如果本月买入，下个卖出能够得到的收益，然后股票的最大收益问题就变成了一个已知int数组的最大和子串问题。而这个问题本身有很成熟的解决方案：暴力循环--》O（n2），递归--》O（nlgn），动态规划--》O（n） 都可以解决。
/*复杂度：O（n）：accpt*/
public class Solution {
public int maxProfit(int[] prices){
int temp = 0;
int max = 0;
int[] det = new int[prices.length];
for(int i=0;i<prices.length-1;i++){
det[i] = prices[i+1]-prices[i];
}
for(int i=0;i<det.length;i++){
temp = temp + det[i];
if(temp < 0){
temp = 0;
}
if(temp > max){
max = temp;
}
}
return max;
}
}
本题也可以使用下面一题里面的思路，求出所有波段的profit值，在过程中记录获利最大的一个波段，复杂度同样为O（n）。
（2）Best Time to Buy and Sell Stock II
Total Accepted: 10315 Total Submissions: 29085My SubmissionsSay you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
url：http://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
测试用例：
空数组: []
只有一个元素的数组: [1]
所有收益均为负数的数组: [8,7,4,2]
算法：周期性检查波底和封顶的值，profit=prices[封顶]-price[波底]；直到数组全部元素都结束，注意点主要是边界值不能越界。
/*算法复杂度：O（n）*/
public class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
int minPos = 0;
int maxPos = 0;
while (maxPos < prices.length-1) {
minPos = findMin(prices, maxPos);
maxPos = findMax(prices, minPos);
profit = profit +( prices[maxPos] - prices[minPos]);
}
return profit;
}
public int findMax(int[] prices, int pos) {
int i;
for(i=pos;i<prices.length-1 && prices[i+1]>=prices[i];i++){
}
return i;
}
public int findMin(int[] prices, int pos) {
int i;
for(i=pos;i<prices.length-1 && prices[i+1]<=prices[i];i++){
}
return i;
}
}
最新文章
- Iterator
- bluetooth 蓝牙协议和标准,配置
- .net 实现Office文件预览,word文件在线预览、excel文件在线预览、ppt文件在线预览
- (转).NET代码混淆实践
- Git 10 周年之际，创始人 Linus Torvalds 访谈
- HTML+CSS学习笔记(4) - 认识标签（3）
- （转载）图解Linux系统的系统架构
- 【转】Android开发学习笔记：EditText的属性介绍
- [RxJS] Basic DOM Rendering with Subscribe
- Android自定义控件（四）——让每一个Activity UI都具有弹性
- python中3个帮助函数help、dir、type的使用
- 转 错误：ORA-28002： the password will expire within 7 days 解决方法
- 模仿jquery的fileupload插件
- MPAndroidChart的K线图上添加均线
- 7-27 Codeforces Round #499 (Div. 2)
- 《程序设计入门——C语言》翁恺老师 第二周编程练习记录
- amaze ui 滚动监听
- 拦截过滤防御XSS攻击 -- Struts2.3 以及 2.5 的解决方式
- Win#password;;processon #clone;;disassemble;;source find
- BZOJ3625 [Codeforces Round #250]小朋友和二叉树（生成函数+多项式开根）