こんにちは
今回の学びは
・アルゴいいの思いつかなければ、グラフを書くとパターンが見える確率が30%あがる
・そろそろ、紙の上で集中アルゴひらめき体操をおこないましょう
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
最初にbuy and sell stock iを解いたわけですが、この問題は急に難しい
と感じました。
考えても思いつかなかったのでbrute forceでいけるんじゃないか？
と思い。実装しはじめます。easy問題ですし、通るのではないかと。
そしてTLEで弾かれますw
その後、枝刈りや、キャシュやらでももがきます。以下のようにもがく。
# 2329pm TLE(time limit exceed)でございます
# TLE at 199 / 201 test cases passed.
# 配列の大きさは1000でしたので(1000/2)^n
# 2339pm
# RecursionError: maximum recursion depth exceeded while calling a Python object
# でたので広げた
# 2338pm へー、普通にprimitiveで宣言してもて内部関数から参照できいんだ、だから
# わざわざオブジェクトにしています。
# 2342pm キャッシュ実装開始
最初にbought = 0でも買ってるのに買ってないと意図せず判定されていた。
# 2340pm いやちがうやんけ
# O(2^n)やんけ、1000なんて天文学てきやわ、おわんね。
# 枝刈りでもすっかた
# まずはキャッシュで
# 2348pm gaveup
# 2351pm https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/solution/
# おもったよりちゃんとグラフを読み解かんとアカンのかい
# 明日や
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は O(2^n)
pseudocode（擬似コード）をかいてみますか。
実際の実装はこちら
import sys
# 2339pm
# RecursionError: maximum recursion depth exceeded while calling a Python object
# でたので広げた
sys.setrecursionlimit(314159265)
from collections import defaultdict
class Solution:
@timeit
def maxProfit(self, prices: List[int]) -> int:
class Counter():
def __init__(self):
self.n = 0
hits = Counter()
calls = Counter()
# 2338pm へー、普通にprimitiveで宣言してもて内部関数から参照できいんだ、だから
# わざわざオブジェクトにしています。
# 2342pm キャッシュ実装開始
cache = defaultdict(lambda:-1)
def rec(S, bought, i, sofar):
if cache[(bought, i, sofar)] != -1:
hits.n += 1
return cache[(bought, i, sofar)]
#print("%s%i:sofar:%s" %(' '*i, i, sofar))
calls.n += 1
if i == len(S):
return sofar
maxi = 0
# debugging took 15 mins
# if bought:ってやってたんだけど 最初にbought = 0でも買ってるのに買ってないと意図せず判定されていた。
# 学び,None判定は気を使ってね
if bought is not None:
tmp1 = rec(S, None, i+1, sofar + S[i] - S[bought]) # sell
cache[(None, i+1, sofar + S[i] - S[bought])] = tmp1
tmp2 = rec(S, bought, i+1, sofar)
cache[(bought, i+1, sofar)] = tmp2
maxi = max(
maxi,
tmp1,
tmp2,
)
else:
tmp3 = rec(S, i, i+1, sofar) # bought
cache[(i, i+1, sofar)] = tmp3
tmp4 = rec(S, None, i+1, sofar) # pass
cache[(None, i+1, sofar)] = tmp4
maxi = max(
maxi,
tmp3,
tmp4,
)
return maxi
ans = rec(prices, None, 0, 0)
print("calls:%s" % calls.n)
print("hits:%s" % hits.n)
return ans
# 2329pm TLE(time limit exceed)でございます
# TLE at 199 / 201 test cases passed.
# 配列の大きさは1000でしたので(1000/2)^n
# 2340pm いやちがうやんけ
# O(2^n)やんけ、1000なんて天文学てきやわ、おわんね。
# 枝刈りでもすっかた
# まずはキャッシュで
# 2348pm gaveup
# 2351pm https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/solution/
# おもったよりちゃんとグラフを読み解かんとアカンのかい
# 明日や
samples = [
# ([7,1,5,3,6,4], 7),
# ([1,2,3,4,5], 4),
# ([7,6,4,3,1], 0),
# TLE
# https://leetcode.com/submissions/detail/266233801/testcase/
]
for S, expected in samples:
ans = Solution().maxProfit(S)
print(ans)
ここまでやってダメだったので解答をみることにしました。
ちらっとソリューションを見て
なんかグラフかいてるぞっと言うことで
別日に中二日w
にリフレッシュした気持ちで
絵をかきました。ぐらふですね。
すると、行けそうなアルゴリズムが思い付いたのでこれで実装してみたいと思います。
O(n)です。
ここでの学びは、グラフを書くことの大切さです。
グラフを書くとパターンが見える確率が30%あがる
数字はズバリ適当です。
適当に言い切ってしまっておきます。
こういう風なほうが、個人的には覚えやすいので。改めていいますが、論拠のない数字ですので
読者の皆様はこの数字は鵜呑みにしないでくだいさい。あくまで個人の感想です。
思い付いてからの実装は15分ほどでした。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
bought_price = 0 # no stock
bought = 0
# bought_price = 1 # bought something
profit = 0
for i in range(len(prices)):
curr_price = prices[i]
if (i + 1) < len(prices): # 次がある
next_price = prices[i+1]
if bought == 0:
# 買う遷移を考える
if next_price > curr_price:
bought_price = curr_price
bought = 1 # はいー、買いましたよーー
else: # それ以外が同一値か、下がるので買いません
pass
else:
# 売る遷移をかんがえる
if next_price < curr_price:
# 次は下がるらしいので今売ってしまいましょ
local_profit = curr_price - bought_price # stateには買値が保存されているので
#
profit += local_profit
bought_price = 0 # 売ったので0にもどす
bought = 0
else:
# 最後のエレメント
if bought > 0:
if curr_price > bought_price:
profit += curr_price - bought_price
return profit
実装後です。timespace analysis (時間とスペースの分析）は O(n)
アルゴリズムを考えの状態からソースコードに変換する技術はだいぶついてきたと思うので
もう少し紙の上で、ひたすら解いて、問題数をこなしパターンを自分の脳の筋力が慣れるようにするというエクセサイズをしてもいい
そろそろ、紙の上で集中アルゴひらめき体操をおこないましょう
（一日一時間とかってやってもいいかも）
とおもう
同時に実装技術は注いてきただ、15分では、まだ遅いの事実
上記のエクセサイズとは別にパソコンで今まで通り実装する練習も怠らないようにしたい。
次はいきなりハードですね！！♡ best-time-to-buy-and-sell-stock-iii
まとめ
・アルゴいいの思いつかなければ、グラフを書くとパターンが見える確率が30%あがる
・そろそろ、紙の上で集中アルゴひらめき体操をおこないましょう
以上です