Just Do IT !

Python算法学习day4:关于一道亚马逊面试题的情景分析

Python算法
字数统计: 715阅读时长: 3 min
2020/01/16 Share

题目描述

1
2
3
4
亚马逊是一家纳斯达克上市公司，通过其财报我们可以解读它在给定时期内的股票走势信息。
这些信息包括每天交易的最高价、最低价以及开盘价。假定你作为交易员，必须在股票开盘时做出买入或卖出的决定。
你负责设计一个算法，根据给定的股价走势信息，决定买入和卖出策略，该策略必须保证你的交易获得的利润最大化。
假设S数组有以下9个数值[10,4,8,7,9,6,2,5,3]

1. 暴力枚举法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# S定义股票开盘价
S = [10,4,8,7,9,6,2,5,3]

maxProfit = 0
buyDay = 0
sellDay = 0
# 暴力枚举
for i in range(len(S) - 1):
	for j in range(i+1, len(S)):
		if S[j] - S[i] > maxProfit:
			maxProfit = S[j] - S[i]
			buyDay = i
			sellDay = j
print("应该在第{0}天买入, 第{1}天卖出, 最大交易利润为: {2}").format(buyDay+1, sellDay+1, maxProfit))

算法时间复杂度为O(n*n)

2. 分而治之法

分别计算前半部分和后半部分的最大交易利润,然后在两者中选择出较大的那个,最后还要考虑一种临界情况,那就是最大利润在前半部分的某一天买入,后半部分的某一天卖出
代码实现:

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
41
def findMaxProfit(S):
	if len(S) < 2:
		return [0,0,0]
	if len(S) == 2:
		if (S[1] > S[0]):
			return 	[0,1,S[1] - S[0]]
		else :
			return [0,0,0]
	# 把交易数据分成两部分
	firstHalf = findMaxProfit(S[0:int(len(S) / 2)])
	secondHalf = findMaxProfit(S[int(len(S) / 2):len(S)])
	finalResult = firstHalf
	
	if (SecondHalf[2] > firstHalf[2]):
		# 后半部分的交易日期还要加上前半部分的天数
		secondHalf[0] += int(len(S) / 2)
		secondHalf[1] += int(len(S) / 2)
		finalResult = secondHalf
	# 看最大利润方案是否是在前半部分买入, 后半部分卖出 
	
	lowestPrice = S[0]
	highestPrice = S[int(len(S) / 2)]
	buyDay = 0
	selDay = int(len(S) / 2)
	for i in range(0, int(len(S) / 2)):
		if (S[i] < lowestPrice):
			buyDay = i
			lowestPrice = S[i]
		for i in range(int(len(S) / 2), len(S)):
			if (S[i] > highestPrice):
				selDay = i
				highestPrice = S[i]
		if (highestPrice - lowestPrice > finalResult[2]):
			finalResult[0] = buyDay
			finalResult[1] = selDay
			finalResult[2] = highestPrice - lowestPrice
		return finalResult
		
S = [10,4,8,7,9,6,2,5,3]
maxProfit = findMaxProfit(S)
print("应该在第{0}天买入, 第{1}天卖出, 最大交易利润为: {2}").format(buyDay+1, sellDay+1, maxProfit))

3. 最优解法

假设最佳交易方案是第N天卖出, 那么最佳的买入时机就是前N-1天价格最低的时候

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
S = [10,4,8,7,9,6,2,5,3]
minPrice = S[0]

N = 0

maxProfit = 0
buyDay = 0
sellDay = 0

for N in range(len(S)):
	if (S[N] < minPrice):
		minprice =S[N]
		buyDay = N
	
	if (S[N] - minPrice > maxProfit):
		maxProfit = S[N] - minPrice
		selDay = N
print("应该在第{0}天买入, 第{1}天卖出, 最大交易利润为: {2}").format(buyDay+1, sellDay+1, maxProfit))

原文作者：浩翰

原文链接：https://plutoacharon.github.io/2020/01/16/Python算法学习day4-关于一道亚马逊面试题的情景分析/

发表日期：January 16th 2020, 8:48:35 pm

更新日期：January 17th 2020, 2:39:23 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目描述
    1. 1.1. 1. 暴力枚举法
    2. 1.2. 2. 分而治之法
    3. 1.3. 3. 最优解法
Total : 190
2020
2019
CTF Liunx 高可用负载均衡 Java Hadoop Docker Esxi Dokcer Flume GitHub Kafka Golang Golang日志收集系统 Hbase Hive Git Kali Kubernetes Shell Python算法 Spark Sqoop Vmware 机器学习 Zookeeper PHP Hexo 安全 Python PySpark Maven 网络 数据采集 CDN AWD ZooKeeper
CTF Liunx Hadoop Docker GitHub Golang Golang日志收集系统 高可用负载均衡 Hive Java Kubernetes 其他 Python算法 Spark Vmware 机器学习 博客 Python 网络 CDN