0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

AI支招!终于知道如何买卖股票了!(妙招,干货)

电子工程师 来源: 聂磊 作者:电子发烧友 2019-03-01 11:05 次阅读

Leetcode第121题到123题连续出现了三道买卖股票相关的题目,一年前的网易笔试和半年前的百度面试都遇到过121题,不过不用慌,看完本文,你一定能够完美解决买卖股票的问题。那么我们由易到难,依次介绍这三道题目。

best time to buy and sell stock

121题题目是这样的:

在所有的过程中,我们只允许一次的买卖,基于这个问题,我们得到了下面的两种解法。

解法1

根据题意,我们只需要找出数组中最大的差值即可,即 max(prices[j] – prices[i]) ,i < j。

如何得到最大的差值,只需要一次遍历即可,在遍历的用一个变量记录遍历到当前时的最小值即可。时间复杂度为O(n).

相关的实现代码如下:

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length< 2){return0;}intmin=prices[0];intprofit=0;//第i天的价格可以看作是买入价也可以看作是卖出价for(inti=1;i< prices.length; i++) {    //找到更低的买入价if(min>prices[i]){//更新买入价min=prices[I];}//当天的价格不低于买入价else{//如果当天买出的价格比之前卖出的价格高if(profit< prices[i] - min) {            //更新卖出价profit=prices[i]-min;}}}returnprofit;}}
解法2

第二题的解法是我在面试百度的时候想到的,应用的是求数组中和最大的连续子数组序列的思路,这种思路又被称为Kadane's Algorithm。我们有两个问题:

如何转化为求数组中的和最大的连续子序列?相邻两个数作差即可,这样的话子序列的和就是我们在子序列开始卖出股票,在子序列最后买回股票所能得到的收益。

那么什么是Kadane's Algorithm呢?

kadane算法利用了数学归纳法的思想。简单来讲就是,随意给你一个现成的数组,比如说−2, 1, −3, 4, −1, 2, 1, −5, 4,让你求其中的最大子列和,并不是容易的事情。但如果我们能从第一个数开始,随着数组的扩充,始终对其最大子列和保持跟踪,就可以轻易的求出任意一个数组的最大子列和。换言之,长度n的数组我们不会求,长度为一的总能算出来吧?长度为一的算出来了,二也就能算出来,二算出来了,三就能算出来,以此类推,用这种根据i求i+1的思想,我们就能达到最终目的。

详细的分析一下,往一个长度为i的数组后面插入第i+1个数,这时,数组的最大子列只有两种情况,要么包括第i+1个数,要么不包括第i+1个数。即:

maxsubarraum = max(以第i+1个数结尾的子列和, 不以第i+1个数结尾的子列和)。*

先计算前者,以第i+1个数结尾的子列和怎么算呢?很简单,要么它是以第i个数结尾的子列作为前缀,要么它不以之作为前缀。假设第i+1个数为x,那么:

以第i+1个数结尾的子列和 = max(x,以第i个数结尾的子列和+x) (1)。

再计算后者,也就是不以第i+1个数结尾的子列和。这啥意思呢?其实就是插入第i+1个数之前的数组的最大子列和嘛。我们的数学归纳思想也就体现在这里,如果你还看不明白,我们将*式改写:

数列长度i+1的最大子列和 = max(以第i+1个数结尾的子列和, 数列长度i的最大子列和)。(2)

看到了吧,无论(1)式还是(2)式,后一种情况都可以由前一种情况推出,妥妥的数学归纳。我们的算法只要从i=1开始,一步一步按照上面的规则走下去,那么任意一个数列的最大子列和就能求出来了!

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length<2)return0;intmaxCur=0;intmaxSoFar=0;for(inti=1;i0,Math.max(prices[i]-prices[i-1],maxCur+prices[i]-prices[i-1]));maxSoFar=Math.max(maxCur,maxSoFar);}returnmaxSoFar;}}
122.best time to buy and sell stockII

这道题的描述如下:

这道题允许无限次的买卖,简直太简单了吧,只要后一天的价值比前一天的大,那就买卖呗。不忍吐槽的一道题,代码如下:

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length<2)return0;intmaxProf=0;for(inti=1;iprices[i-1]?prices[i]-prices[i-1]:0);}returnmaxProf;}}
123 best time to buy and sell stock III

这一题还是比较难的,题目描述如下:

我们只允许最多两次的买卖,这可如何是好?我们同样提供两种思路:

解法1

这个问题可以转换成Best Time to Buy and Sell Stock I问题。

两次股票交易的核心是可以定义一个交易点,在这个交易点之前可以做一次交易(赚的最大数目的钱为firstProf),在这个交易点之后可以做一个交易(赚的最大数目的钱是secondProf)。那么要求的是max(firstProf+secondProf)。但是这个方法的时间复杂度是O(N^2),空间复杂度是O(1)。leetcode中显示超时。

可以使用两次扫描的方法避免上面的双重循环。

不同于Best Time to Buy and Sell Stock I中定义的初始状态A[i]表示第i天卖出挣的最大数目的钱,这个更进一步直接定义A[i]表示前i天赚的最大数目的钱。minPrice表示从第0天到第i-1天中的最低价格。

A[0]=0。(初始状态)A[1]=max(prices[1]-prices[0],A[0])A[2]=max(prices[2]-minPrice,A[1]).....

即A[i]=max(price[i]-minPrice,A[i-1]).

另外一次扫描从数组后向前扫描,定义B[i]表示从第i天到最后一天n能赚的最大数目的钱。

maxPrice表示第i+1天到n天的最高价格。B[n]=0。(初始状态)B[n-1]=max(maxPrice-prices[n-1],B[n])B[n-2]=max(maxPrice-prices[n-2],B[n-1]).....

即B[i]=max(maxPrice-prices[i],B[i+1])

那么以第i天为分割点能赚的最多数目的钱为A[i]+B[i]问题的解为max{A[i]+B[i]}。0<=i<=n。时间复杂度是O(N),空间复杂度是O(N)。

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length<2)return0;int[]asc=newint[prices.length];int[]desc=newint[prices.length];intn=prices.length;intminprice=prices[0];intmaxProf=0;asc[0]=0;for(inti=1;iasc[i]=Math.max(prices[i]-minprice,maxProf);minprice=Math.min(prices[i],minprice);maxProf=asc[i];}desc[prices.length-1]=0;maxProf=0;intmaxprice=prices[prices.length-1];for(inti=prices.length-2;i>=0;i--){desc[i]=Math.max(maxprice-prices[i],maxProf);maxprice=Math.max(maxprice,prices[i]);maxProf=desc[i];}maxProf=0;for(inti=0;iasc[i]+desc[i]);}returnmaxProf;}}
解法2

第二种解法的核心是假设手上最开始只有0元钱,那么如果买入股票的价格为price,手上的钱需要减去这个price,如果卖出股票的价格为price,手上的钱需要加上这个price。

因此我们定义了4个状态:

Buy1[i]表示前i天做第一笔交易买入股票后剩下的最多的钱;Sell1[i]表示前i天做第一笔交易卖出股票后剩下的最多的钱;Buy2[i]表示前i天做第二笔交易买入股票后剩下的最多的钱;Sell2[i]表示前i天做第二笔交易卖出股票后剩下的最多的钱;

那么假设我们在第i天时第二次卖出股票,我们卖出股票可以获得Buy2[i-1]+prices[i]的钱,假设在第i天前已经完成了两笔交易,那么我们最多的钱是Sell2[i-1],因此Sell2[i]=max{Sell2[i-1],Buy2[i-1]+prices[I]}同样的道理,假设我们在第i天时第二次买入股票,我们手中的钱是Sell[i-1]-prices[i],假设我们在第i天钱已经卖出了两次股票,那么我们最多的钱是Buy2[i-1],因此Buy2[i]=max{Buy2[i-1],Sell[i-1]-prices[I]}同样的道理我们还可以得到:Sell1[i]=max{Sell[i-1],Buy1[i-1]+prices[I]}Buy1[i]=max{Buy[i-1],-prices[I]}

可以发现上面四个状态都是只与前一个状态有关,所以可以不使用数组而是使用变量来存储即可。


声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 人工智能
    +关注

    关注

    1791

    文章

    47208

    浏览量

    238287

原文标题:如何买卖股票?不要慌,我有妙招!

文章出处:【微信号:atleadai,微信公众号:LeadAI OpenLab】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    基于网络共识的股票价格行为数据挖掘(英文

    【作者】:赖兴瑞;张东站;段江娇;【来源】:《心智与计算》2010年01期【摘要】:股票价格行为数据挖掘激发了计算机科学、机器学习及其他领域研究的广泛关注。然而,由于股票价格本身的不确定性和股市
    发表于 04-24 09:56

    深圳天瑞地安解析股票软件的功能需求

    强劲的增长势头。  伴随着移动互联网威廉希尔官方网站 的发展,股票APP软件开发也进入了全新的阶段。各种股票APP软件更是层出不穷,如同花顺、招商致远。不过股票APP要想赢得客户信赖,个性化体验是制胜关键!
    发表于 02-13 19:16

    股票数据如何分析

    股票数据分析
    发表于 05-29 10:49

    2018人工智能股票龙头

    2018人工智能股票龙头,2019-01-07 10:49:43近年来中国的人工智能行业可以说是***,一边是像云从科技、商汤科技这些持续获得融资的AI巨头,一边是AI创业公司的密集倒闭,根据
    发表于 07-28 07:40

    经音频电话系统处理现金转帐及股票买卖授权及补偿协议

    经音频电话系统处理现金转帐及股票买卖授权及补偿协议
    发表于 07-13 20:45 16次下载

    节约电池有妙招

    节约电池有妙招  少刹车 匀速骑 起步人力助骑        在日前扬州市某单位举办的电动车极限挑战赛上,不同品牌的电
    发表于 11-10 16:44 437次阅读

    手机=定时炸弹?专家支招让您手机防窃听

    手机=定时炸弹?专家支招让您手机防窃听
    发表于 12-28 08:56 630次阅读

    马云的话绝对可信 终于知道马云为什么不让年轻人去买房!原来如此

    终于知道马云为什么不让年轻人去买房!原来阿里有大招啊!
    发表于 08-12 10:15 1.4w次阅读

    终于知道手机AI芯片的作用是什么

    手机上的AI威廉希尔官方网站 确实能够提升手机的运行速度,但是不是所有宣称具有AI功能的手机在运行速度上都能维持高水平。只有搭载了人工智能AI芯片的手机,在独立的高浮点性能芯片支持下,在处理一些任务时才能高效率完成。
    发表于 01-31 09:54 2.2w次阅读

    乐视网将进入停牌状态——这是股票暂停上市程序的前奏

    乐视网明确表示,公司预约的年报披露日期为4月26日,如果公司触及《创业板股票上市规则》(2018年11月修订)13.1.1相关规定,即经审计后上市公司2018年度归母净资产为负,公司股票将被暂停上市,暨公司股票将于4月26日开市
    的头像 发表于 04-26 11:40 2939次阅读

    如何快速设计脉搏血氧仪?德州仪器来支招

    如何快速设计脉搏血氧仪?德州仪器来支招
    发表于 10-31 08:23 6次下载
    如何快速设计脉搏血氧仪?德州仪器来<b class='flag-5'>支招</b>!

    干货 | 数字万用表四种妙用方法,你知道么?

    干货 | 数字万用表四种妙用方法,你知道么?
    的头像 发表于 01-05 09:52 1131次阅读

    A6伺服操作小妙招您必须掌握!

    A6伺服操作小妙招您必须掌握
    的头像 发表于 02-06 15:37 1047次阅读
    A6伺服操作小<b class='flag-5'>妙招</b>您必须掌握!

    比起各式各样的AI应用,我们可能更需要AI for OS

    打造 AI时代的操作系统,谷歌和微软都在抢船票了
    的头像 发表于 06-07 22:19 861次阅读
    比起各式各样的<b class='flag-5'>AI</b>应用,我们可能更需要<b class='flag-5'>AI</b> for OS

    气象监测站——气象观测有妙招

    气象监测站——气象观测有妙招
    的头像 发表于 09-04 09:47 482次阅读