ゼロから始めるLeetCode Day103「122. Best Time to Buy and Sell Stock II」

• 概要
• 問題
• 解法

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day102「322. Coin Change」

次回
ゼロから始めるLeetCode Day104「103. Binary Tree Zigzag Level Order Traversal」

Twitterやってます。

問題

122. Best Time to Buy and Sell Stock II
難易度はEasy。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、ithの要素がi日目に指定された株式の価格である配列の価格を与えられます。
最大の利益を見つけるためにアルゴリズムを設計します。あなたは好きなだけ多くのトランザクションを完了することができます。
なお、再び購入する前に株式を売却する必要があります。

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

解法

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_pro = 0
        for i in range(len(prices)-1):
            if prices[i+1] > prices[i]:
                max_pro += prices[i+1] - prices[i] 
        return max_pro
# Runtime: 60 ms, faster than 88.25% of Python3 online submissions for Best Time to Buy and Sell Stock II.
# Memory Usage: 15.1 MB, less than 47.10% of Python3 online submissions for Best Time to Buy and Sell Stock II.

以前解いた利益の最大値を求める問題ではなく、それぞれの利益を最終的に足して総和を返すという問題ですね。
複数回取引ができるというところに注意しておきましょう。

以前の問題はmax関数を使って解きましたが、今回はそれぞれの値を比較し、最終的に返すであろう変数に足していけば良いので以前よりも単純なコードになります。

では今回はここまで。お疲れ様でした。