概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day49 「1323. Maximum 69 Number」
今はTop 100 Liked QuestionsのMediumを優先的に解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。
Twitterやってます。
50回ですよ！50回！
問題
739. Daily Temperatures
難易度はMedium。
Top 100 Liked Questionsからの抜粋です。
問題としては、それぞれの日の気温を格納したリストであるTが与えられます。
それらの要素が入力の各日より暖かい気温になるまで何日かかるかを示すリストを返すアルゴリズムを設計してください。
例えば、T = [73、74、75、71、69、72、76、73]である場合、返すリストは[1、1、4、2、1、1、0、0]となります。
なお、気温の長さは[1,30000]、各気温は[30,100]の間で与えられるものとします。
問題を見た時、最初はえ？？なんで出力がこうなるの？と思いましたが、よくよく見てみたら自分の理解力が低いだけでした。
次の日との差とかではなく、単純に何日後にその日の気温を超えるかを導けば良いだけなんですね。
解法
最初に0が要素の長さ分入ったリストを用意してあげて、素直にリストを舐めていくのが分かりやすいかと思いました。
stackを使えばLIFOなので、より簡単に実装できるでしょう。
例の場合でしたら、stackと[0]をTの長さの分だけ最初に用意します。
そこからリストを舐めていきましょう。
ここで大事なのは、どういった条件付けで代入を行い、そして要素をずらすためにはどういった処理を行えば良いかという点でしょう。
この場合であれば、stackが存在し、かつT[stack[-1]]が 前から舐めていった際の要素よりも大きい場合にのみansの要素をポップし、要素の順番からstackの最後の要素を引いたものを入れれば良い、ということになります。
そして、stackにインデックスを追加し、要素がなくなるまで繰り返し行えばansの中に各日程の所要日数が取れると思います。
ここまでの流れを書いてみました。
class Solution(object):
def dailyTemperatures(self, T):
ans,stack = [0] * len(T),[]
for i, j in enumerate(T):
while stack and T[stack[-1]] < j:
ans[stack.pop()] = i - stack[-1]
stack.append(i)
return ans
# Runtime: 548 ms, faster than 32.01% of Python3 online submissions for Daily Temperatures.
# Memory Usage: 17.1 MB, less than 95.07% of Python3 online submissions for Daily Temperatures.
おなじみのenumerateです。
forループの中でリスト（配列）などのイテラブルオブジェクトの要素と同時にインデックス番号（カウント、順番）を取得できる、というもので、こういったカウントと順番を両方取得して変数に代入できる優れものです。
Easy問題を何度か挟んでいたので久しぶりにこんな感じで頭を使いました。よくよく考えてみたら二点間の距離的な考え方もできそうですね。
今回はここまで。お疲れ様でした。