锐客网

  1. 首页 > it技术 > >

面试算法题--股票问题

1.只能进行一次的股票交易
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例：
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意: 利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

#用了双层循环，复杂度是O(n^2）,继续优化 value=https://www.it610.com/article/[] for i in range(len(list1)): for j in range(i+1,len(list1)): if list1[i]

#用单层循环，用一个变量来存放此刻买入的最小值，同时用一个变量来存放最大的利润value,判断此时是不是最大的利润 value1=0 min1=1000 for i in range(0,len(list1)-1): if list1[i]value1: value1=value print(value1)

#动态规划 #核心转移方程dp[i](前i天最大的利润)= max(dp[i-1)(前i-1天的最大利润)，list1[i]-minprice(第i天卖出的最大利润)） dp = [0] * n minprice = list1[0] for i in range(1, len(list1)): minprice = min(minprice, list1[i]) dp[i] = max(dp[i - 1], list1[i] - minprice) print(dp) print(dp[-1])

2.可以进行无限次的股票交易
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
【面试算法题--股票问题】示例：
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
#贪心算法：把问题分解成子问题，总是选择当前子问题的一个最有解，但是有可能最后的结果不是最优的解 #把找到最大利润分成求解若干个相近的两点，若后者比前者大，则计算利润 value=https://www.it610.com/article/0 for i in range(1,len(list1)): if list1[i]>list1[i-1]: value=https://www.it610.com/article/value+list1[i]-list1[i-1] print(value)

""" #画图，找到波峰波谷，其实最大的利润则为相邻的波峰减去波谷 i=0 value=https://www.it610.com/article/0 while i=list1[i+1]: i+=1 gu=list1[i] #找到峰 while i

#动态规划 #分为两个状态 0--持有现金1---持有股票dp[len-1][0] #核心转移公式 dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]) dp=[[0 for i in range(2)] for j in range(len(prices))] dp[0][1]= -prices[0] print(dp)for i in range(1,len(prices)): dp[i][0] =max(dp[i - 1][0], dp[i - 1][1] + prices[i]) dp[i][1] =max(dp[i - 1][1], dp[i - 1][0] - prices[i]) #print(dp) print(dp[len(prices)-1][0])

3.只能进行两次的股票交易
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 :
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
#动态规划 #分为两个状态 0--持有现金1---持有股票max(dp[len-1][2][0],dp[len-1][1][0]) #分为三个状态 0--没有交易1---交易一次2--交易两次 #核心转移公式 dp[i][0][0]=0 dp[0][0][0]=0dp[0][1][0]=0dp[0][2][0]=0dp[0][0][1] = dp[0][1][1] = dp[0][2][1] = -prices[0]; #dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][0][1]+prices[i]) #dp[i][1][1]=max(dp[i-1][1][1],dp[i-1][0][0]-prices[i]) #dp[i][2][0]=max(dp[i-1][2][0],dp[i-1][1][1]+prices[i]) #dp[i][2][1]=max(dp[i-1][2][1],dp[i-1][1][0]-prices[i])if len(prices)<2: print(0) dp=[[[0 for i in range(2)] for j in range(3)] for k in range(len(prices))] #print(dp) dp[0][0][1] = dp[0][1][1] = dp[0][2][1] = -prices[0] dp[0][0][0] = dp[0][1][0] = dp[0][2][0] = 0 for i in range(1,len(prices)): dp[i][0][0] = 0 dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][0][1]+prices[i]) dp[i][1][1]=max(dp[i-1][1][1],dp[i-1][1][0]-prices[i]) dp[i][2][0]=max(dp[i-1][2][0],dp[i-1][1][1]+prices[i]) dp[i][0][1]=max(dp[i-1][0][1],dp[i-1][0][0]-prices[i]) dp[i][2][1]=0 #print(dp) print(max(dp[len(prices)-1][2][0],dp[len(prices)-1][1][0]))

    推荐阅读


    上一篇：Bert实战--文本分类(一)

    下一篇：SQUAD数据集分析