提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

golang刷leetcode：买卖股票最佳时机

2023-02-18 16:32:26 时间

BM80 买卖股票的最好时机(一)

描述

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天

2.如果不能获取到任何利润，请返回0

3.假设买入卖出均无手续费

数据范围：10^40 \le n \le 10^5 , 0 \le val \le 10^4

要求：空间复杂度O(1),空间复杂度O(n)

示例1

输入：

[8,9,2,5,4,7,1]

复制

返回值：

5

复制

说明：

在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。

示例2

输入：

[2,4,1]

复制

返回值：

2

复制

示例3

输入：

[3,2,1]

复制

返回值：

0

解题思路：

动态规划：只能买卖一次，记录历史上的最低价格min

dp[i]=min(dp[i-1],min),由于只用到了i-1所以可以降维

代码实现： 

package main
/**
  * 
  * @param prices int整型一维数组 
  * @return int整型
*/
func maxProfit( prices []int ) int {
    if len(prices)<2{
        return 0
    }
    // write code here
    min:=prices[0]
    dp:=0
    for i:=1;i<len(prices);i++{
        if prices[i]<min{
            min=prices[i]
        }
        if dp<prices[i]-min{
            dp=prices[i]-min
        }
    }
    return dp
}

BM81 买卖股票的最好时机(二)

描述

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1. 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票

2. 如果不能获取收益，请返回0

3. 假设买入卖出均无手续费

数据范围：10^40 \le n \le 10^5 , 0 \le val \le 10^4

要求：空间复杂度O(1),空间复杂度O(n)

示例1

输入：

[8,9,2,5,4,7,1]

复制

返回值：

7

复制

说明：

在第1天(股票价格=8)买入，第2天(股票价格=9)卖出，获利9-8=1
在第3天(股票价格=2)买入，第4天(股票价格=5)卖出，获利5-2=3
在第5天(股票价格=4)买入，第6天(股票价格=7)卖出，获利7-4=3
总获利1+3+3=7，返回7

示例2

输入：

[5,4,3,2,1]

复制

返回值：

0

复制

说明：

由于每天股票都在跌，因此不进行任何交易最优。最大收益为0。

示例3

输入：

[1,2,3,4,5]

复制

返回值：

4

复制

说明：

第一天买进，最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。

备注：

总天数不大于200000。保证股票每一天的价格在[1,100]范围内。

解题思路：

由于可以多次买入卖出，只要当前价格比前一天高就卖出，累计当前比前一天价格高的和就行了

代码实现：

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 计算最大收益
 * @param prices int整型一维数组 股票每一天的价格
 * @return int整型
*/
func maxProfit( prices []int ) int {
    // write code here
    sum:=0
    for i:=1;i<len(prices);i++{
        if prices[i]-prices[i-1]>0{
            sum+=prices[i]-prices[i-1]
        }
    }
    return sum
}

BM82 买卖股票的最好时机(三)

描述

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益 1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票 2. 如果不能获取收益，请返回0 3. 假设买入卖出均无手续费

数据范围：10^40 \le n \le 10^5 , 0 \le val \le 10^4

要求：空间复杂度O(1),空间复杂度O(n)

示例1

输入：

[8,9,3,5,1,3]

复制

返回值：

4

复制

说明：

第三天(股票价格=3)买进，第四天(股票价格=5)卖出，收益为2
第五天(股票价格=1)买进，第六天(股票价格=3)卖出，收益为2
总收益为4。

示例2

输入：

[9,8,4,1]

复制

返回值：

0

复制

示例3

输入：

[1,2,8,3,8]

复制

返回值：

12

复制

说明：

第一笔股票交易在第一天买进，第三天卖出；第二笔股票交易在第四天买进，第五天卖出；总收益为12。
因最多只可以同时持有一只股票，所以不能在第一天进行第一笔股票交易的买进操作，又在第二天进行第二笔股票交易的买进操作（此时第一笔股票交易还没卖出），最后两笔股票交易同时在第三天卖出，也即以上操作不满足题目要求。

备注：

总天数不大于200000。保证股票每一天的价格在[1,100]范围内。

解题思路

1，由于需要买卖两次，所以有5个状态，一直未买入，买入过一次，卖出过一次，买入过两次，卖出过两次。

2，如果没有买入过，收益一直是0，如果买入过一次收益就是当前花费的最少的钱，如果卖出过一次，收益就是当前价格减去买入价格，如果买入过两次，当前收益就是第一次卖出收益减去当前价格，如果卖出两次当前收益就是两次第二次买入后的收益加上当前卖出价格

3，由于只依赖i-1，所以可以降维

代码实现

package main
 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 两次交易所能获得的最大收益
 * @param prices int整型一维数组 股票每一天的价格
 * @return int整型
*/
func maxProfit( prices []int ) int {
    if len(prices)<2{
        return 0
    }
    // write code here
    dp:=make([][4]int,len(prices))
    dp[0][0]=-prices[0]
     dp[0][1]=-10000
     dp[0][2]=-10000
     dp[0][3]=-10000
    for i:=1;i<len(prices);i++{
        dp[i][0]=max(dp[i-1][0],-prices[i])
        dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])
        dp[i][2]=max(dp[i-1][2],dp[i-1][1]-prices[i])
        dp[i][3]=max(dp[i-1][3],dp[i-1][2]+prices[i])
    }
    return max(dp[len(prices)-1][1],dp[len(prices)-1][3])
}
 
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

优化实现 

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 两次交易所能获得的最大收益
 * @param prices int整型一维数组 股票每一天的价格
 * @return int整型
*/
func maxProfit( prices []int ) int {
    if len(prices)<2{
        return 0
    }
    // write code here
    dp:=[4]int{-prices[0],-10000,-10000,-10000}
    for i:=1;i<len(prices);i++{
        dp[3]=max(dp[3],dp[2]+prices[i])
        dp[2]=max(dp[2],dp[1]-prices[i])
        dp[1]=max(dp[1],dp[0]+prices[i])
        dp[0]=max(dp[0],-prices[i])
    }
    return max(dp[1],dp[3])
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

相关文章