最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

【前端算法】买卖股票的最佳时机含手续费_贪心算法、动态规划实现

XAMPP新闻 admin 114浏览 0评论

【前端算法】买卖股票的最佳时机含手续费—— 贪心算法、动态规划实现

drf002

题目描述

给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。

示例 1:

输入:prices = [1, 3, 2, 8, 4, 9], fee = 2
输出:8
解释:能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2:

输入:prices = [1,3,7,5,10,3], fee = 3
输出:6

提示:

1 <= prices.length <= 5 * 104 1 <= prices[i] < 5 * 104 0 <= fee < 5 * 104

来源:力扣(LeetCode) 链接:leetcode-cn.com/problems/be…[1] 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

思路1:动态规划实现

动态规划三部曲

  • 定义dp含义

    • 定义dp[n][2]:
    • n代表第n天有2种状态,持有或者不持有
    • dp[i][0] 第i天不持有获得的最大利润;
    • dp[i][1] 第i天持有获得的最大利润;(tip:是持有不是买入)
  • 定义状态转移方程:

    对于今天不持有,可以从两个状态转移过来:1. 昨天也不持有;2. 昨天持有,今天卖出且支付手续费fee。两者取较大值。

    对于今天持有,可以从两个状态转移过来:1. 昨天也持有;2. 昨天不持有,今天买入。两者取较大值。

    • dp[i][1]=Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);
    • dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
  • 初始化dp;

    • 不持有:dp[0][0]=0;
    • 持有:dp[0][1]=-prices[0] ((即花了price[0] 的钱买入))

由于dp[n][0]>dp[i][1],当天不持有股票利润一定大于当天持有股票,因此返回dp[len-1][0]即可

时空复杂度

  • 时间复杂度:O(n),遍历一遍即可。
  • 空间复杂度:O(n)

代码

function maxProfit(prices: number[], fee: number): number {
    
    let len=prices.length;
     // define dp
     let dp=new Array(len);
     for(let i=0;i<len;i++){
         dp[i]=new Array(2).fill(0);
     }
     // init dp 
     dp[0][0]=0;
     dp[0][1]=-prices[0];
     for(let i=1;i<len;i++){
         dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
         dp[i][1]=Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);
     }
     console.log(dp);
    return dp[len-1][0]
};

优化

降维:状态转移的时候,dp[i] 只会从 dp[i-1] 转移得来,因此第一维可以去掉:

时空复杂度

  • 时间复杂度:O(n),遍历一遍即可。
  • 空间复杂度:O(1)
 function maxProfit(prices: number[], fee: number): number {
    
    let len:number=prices.length;
     // define dp
     let dp=new Array(2);

     // init dp 
     dp[0]=0;
     dp[1]=-prices[0];
     for(let i=1;i<len;i++){
         let temp=dp[0]
         dp[0]=Math.max(dp[0],dp[1]+prices[i]-fee);
         dp[1]=Math.max(temp-prices[i],dp[1]);
     }
     console.log(dp);
    return dp[0]
};

思路2:贪心算法

  • 将手续费买入时进行计算,即可得到一种贪心的方法;
  • 我们定义buy表示:最大化利益的前提下,当我们手上有一只股票时,那么他的买入最低价格。
    • profit=prices[i]-buy;
    • 但是此时我们卖出可能不是最优解,比如:第二天价格继续上升;
    • 因此我们可以假设有个反悔操作,假设当前手上有一只买入价格为prices[i]的股票,
    • 将buy更新为prices[i]:buy=prices[i] ;
    • 如果第二天价格继续上升,我们将获得prices[i+1]-prices[i],此时,加上前一天prices[i]-buy的收益,
    • 由上可知,相当于当天不做任何操作,而在第二天卖出:prices[i+1]-buy
    • 初始化为buy=prices[0]+fee;
    • 如果当前股票prices[i]+fee<buy;则我们更新最低买入价格buy;
    • 如果当前股票大于buy,则我们可以直接卖出获得利润
    • 其余情况,不值得卖出;

时空复杂度

  • 时间复杂度:O(n),遍历一遍即可。
  • 空间复杂度:O(1)
function maxProfit(prices: number[], fee: number): number {
  let len=prices.length;
  let buy=prices[0]+fee;
  let profit=0;
  for(let i=1;i<len;i++){
      if(prices[i]+fee<buy){
          buy=prices[i]+fee;
      }else if(prices[i]>buy){
          profit+=prices[i]-buy
          buy=prices[i]
      }
  }// end of for 
  return profit
};

转载请注明:XAMPP中文组官网 » 【前端算法】买卖股票的最佳时机含手续费_贪心算法、动态规划实现