六六力扣刷题贪心算法之买卖股票的最佳时机含手续费

简介: 六六力扣刷题贪心算法之买卖股票的最佳时机含手续费

前言

之前小六六一直觉得自己的算法比较菜,算是一个短板吧,以前刷题也还真是三天打鱼,两台晒网,刷几天,然后就慢慢的不坚持了,所以这次,借助平台的活动,打算慢慢的开始开刷,并且自己还会给刷的题总结下,谈谈自己的一些思考,和自己的思路等等,希望对小伙伴能有所帮助吧,也可以借此机会把自己短板补一补,希望自己能坚持下去呀

题目

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

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

返回获得利润的最大值。

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

输入: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

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

解析

昨天的题,没有手续费,所以我们就只需要找把后一天-前一天〉0的值全部加起来,就是我们的结果了,那今天的题,其实是有手续费了,就不一样了 如果使用贪心策略,就是最低值买,最高值(如果算上手续费还盈利)就卖。

所以我们在做收获利润操作的时候其实有三种情况:

  • 情况一:收获利润的这一天并不是收获利润区间里的最后一天(不是真正的卖出,相当于持有股票),所以后面要继续收获利润。
  • 情况二:前一天是收获利润区间里的最后一天(相当于真正的卖出了),今天要重新记录最小价格了。
  • 情况三:不作操作,保持原有状态(买入,卖出,不买不卖)
class Solution {
     public int maxProfit(int[] prices, int fee) {
        //定义一个res
        int res = 0;
        //记录最低价格
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            // 记录最小值,相当于买入
            if (prices[i] < min) {
                min = prices[i];
            }
            // 就是中间状态,不需要买,也不需要卖
            if (prices[i]>=min&&prices[i]<min+fee){
                continue;
            }
            //算利润
            if(prices[i]>min+fee){
                res+=prices[i]-min-fee;
                min=prices[i]-fee;
            }
        }
        return res;
    }
}

min=prices[i]-fee很关键,因为如果还在收获利润的区间里,表示并不是真正的卖出,而计算利润每次都要减去手续费,所以要让minPrice = prices[i] - fee;,这样在明天收获利润的时候,才不会多减一次手续费!  其实就是prices[i]-(prices[i]-fee)-fee  负负得正

结束

好了,今天就到这了,小六六觉得贪心还是有点小难,因为每个题都是不同的思路,大家加油吧!

image.png

相关文章
|
3月前
|
算法 Python
【Leetcode刷题Python】309. 最佳买卖股票时机含冷冻期
解决LeetCode上309题“最佳买卖股票时机含冷冻期”的Python代码示例,利用动态规划方法计算在含有冷冻期约束下的最大利润。
40 1
|
23天前
|
算法
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
|
18天前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
10 0
|
23天前
|
算法
【链表】算法题(一) ----- 力扣 / 牛客
【链表】算法题(一) ----- 力扣 / 牛客
|
23天前
|
算法
【顺序表】算法题 --- 力扣
【顺序表】算法题 --- 力扣
|
3月前
|
算法 Python
【Leetcode刷题Python】121. 买卖股票的最佳时机
解决LeetCode上121题“买卖股票的最佳时机”的Python代码示例,采用一次遍历的方式寻找最佳买卖时机以获得最大利润。
58 1
|
3月前
|
算法
leetcode188 买卖股票的最佳时机IV
leetcode188 买卖股票的最佳时机IV
60 0
|
3月前
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
|
3月前
|
算法 Python
【Leetcode刷题Python】714. 买卖股票的最佳时机含手续费
提供了两种解决买卖股票最佳时机含手续费问题的Python实现方法:贪心算法和动态规划算法。
41 0