leetcode刷题笔记

（1）Best Time to Buy and Sell Stock

Total Accepted: 10430 Total Submissions: 33800My Submissions

Say you have an array for which the i^th 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 i^th 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;
    }
}