ARTS - Week 8

ARTS - Week 8

ARTS 是耗叔发起的一项活动,每周完成以下内容:

Algorithm - 至少做一个 LeetCode 上的算法题
Review - 阅读并点评至少一篇英文技术文章
Tip - 学习至少一个技术技巧
Share - 至少分享一篇有观点和思考的技术文章

Algorithm

LeetCode Problems 121 - Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Difficulty: Easy

examples

Solution

DP(动态规划)

经典的买卖股票系列问题,优先用动态规划尝试解决。

# Python

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices: return 0

        result = 0

        profit = [[0 for i in range(3)] for i in range(len(prices))]

        profit[0][0], profit[0][1], profit[0][2] = 0, -prices[0], 0

        for i in range(1, len(prices)):
            profit[i][0] = profit[i - 1][0]
            profit[i][1] = max(profit[i - 1][1], profit[i - 1][0] - prices[i])
            profit[i][2] = profit[i - 1][1] + prices[i]
            result = max(result, profit[i][0], profit[i][1], profit[i][2])

        return result
# Ruby

def max_profit(prices)
  return 0 if prices.empty?

  result = 0

  profit = prices.size.times.map{ 3.times.map{0} }

  profit[0][0], profit[0][1], profit[0][2] = 0, -prices[0], 0

  for i in 1...prices.size
    profit[i][0] = profit[i - 1][0]
    profit[i][1] = [profit[i - 1][1], profit[i - 1][0] - prices[i]].max
    profit[i][2] = [profit[i - 1][1] + prices[i], profit[i - 1][2]].max

    result = [result, profit[i][0], profit[i][1], profit[i][2]].max
  end

  return result
end

运行结果

Python:
Runtime: 68 ms.
Your runtime beats 17.95 % of python3 submissions.

Ruby:
Runtime: 72 ms.
Your runtime beats 5.56 % of ruby submissions.


# ARTS 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×