昨晚咨询了师兄面试算法岗问的问题;有点慌呀。现在的机试都不问leetcode上的题了,而是更加贴近于深度学习的问法,譬如,写一个算法检测出图片中最大的人脸框。我该看看牛客网上今年的机试题了。
- Best Time to Buy and Sell Stock
**思路:只能买卖一次,挑选差值最大的一组。
这种直观的思路超时了。
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
tmp = [0 for x in range (len(prices)-1)]
for i in range(0,len(prices)-1):
tmp[i] = prices[len(prices)-1]-prices[i]
return max(self.maxProfit(prices[0:len(prices)-1]),max(tmp))
动态规划解题,从新添的点里找最低买入点,从新添的点里找最高利润差。
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) <=1:
return 0
buy_price = prices[0]
max_profit = 0
for i in range(1,len(prices)):
buy_price = min(buy_price, prices[i])
max_profit = max(max_profit, prices[i]-buy_price)
return max_profit
- Best Time to Buy and Sell Stock II
**思路:可以买卖多次,但是交易不能同时进行,只能卖完上一注股票才能买入。所以只要找到有增加的值,就算进去。累加得最大利润。
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
max_profit = 0
for i in range(len(prices)-1,0,-1):
if prices[i] > prices[i-1]:
max_profit += prices[i] - prices[i-1]
return max_profit