这是四则或许对你有些许帮助的信息:

1、👉 最近我发现了一个每日都会推送最新校招资讯的《校招日程》文档,其中包括往届补录应届实习校招信息,比如各种大厂、国企、银行、事业编等信息都会定期更新,帮忙扩散一下。

2、😍 免费分享阿秀个人学习计算机以来收集到的免费学习资源,点此白嫖;也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏

3、🚀如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人踩过的坑留下的经验,事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

4、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子,一个人踽踽独行不如一群人报团取暖,圈子里沉淀了很多过去21/22/23届学长学姐的经验和总结,好好跟着走下去的,最后基本都可以拿到不错的offer!此外,每周都会进行精华总结和分享!如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话,可以点此下载

# 714. 买卖股票的最佳时机含手续费

力扣原题链接(点我直达) (opens new window)

给定一个整数数组 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.
1
2
3
4
5
6
7
8

注意:

  • 0 < prices.length <= 50000.
  • 0 < prices[i] < 50000.
  • 0 <= fee < 50000.

# 第一版,动态规划,优化

执行用时 :128 ms, 在所有 cpp 提交中击败了80.36%的用户

内存消耗 :19.7 MB, 在所有 cpp 提交中击败了24.70%的用户

当天买入的最大收益是:1、昨天买入的最大收益,即当天不买入。2、昨天卖出的最大收益-当天股票价格-手续费。

当天卖出的最大收益是:1、昨天卖出的最大收益,即当天无法卖出。2、昨天买入的最大收益+当天股票价格。

手续费算在买入和卖出里都是一样的结果。
思路:动态规划

代码


class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
      if (prices.empty()) return 0;

	int size = prices.size();
	vector<int> hold(size), sold(hold);
	hold[0] = -prices[0];
	for (int i = 1; i < size; ++i) {
		//表示没有股票在手时,身上含有的金额,状态的变化。
		sold[i] = max(sold[i - 1], hold[i - 1] + prices[i] - fee);
		//表示有股票在手时,含有的金额状态的变化
		hold[i] = max(hold[i - 1], sold[i - 1] - prices[i]);
	}
	return sold[size - 1];
};
优化空间
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if (prices.empty()) return 0;
        int size = prices.size();
        int sold = 0, hold = -prices[0];        
        for (int i = 1; i < size; ++i) {
            sold = max(sold, hold + prices[i] - fee);
            hold = max(hold, sold - prices[i]);
        }
        return sold;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 第二版,贪心算法

public int maxProfit(int[] prices, int fee) {
		 int len = prices.length;
		 if(len == 0 || len == 1) return 0;//边界条件
		 int sum = 0,cur=0;
		 int max = prices[0],min = prices[0];
		 for(int i=1;i<len;i++) {
			 min = Math.min(min, prices[i]);//记录当前最小值
			 max = Math.max(max, prices[i]);//记录当前的最大值
			 cur = Math.max(cur, prices[i]-min-fee);//记录当前可能的最大收益
			 if(max - prices[i] > fee) {//如果掉价超过了手续费还不如花手续费买卖股票
				 sum += cur;//赶紧抛出手中股票,能转多少是多少,然后又重新开始
				 min = prices[i];
				 max = prices[i];
				 cur = 0;
			 }
		 }
		 sum += cur;
		 return sum;
	 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19