概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day27「101. Symmetric Tree」
基本的にeasyのacceptanceが高い順から解いていこうかと思います。
Twitterやってます。
問題
198. House Robber
難易度はeasy。
Top 100 Liked Questionsからの抜粋です。
あなたは通り沿いの家から泥棒することを計画している泥棒です。各家には一定のお金が隠されています。各家からの強盗を防ぐ唯一の制約は、それぞれ隣接する家にセキュリティシステムが接続されており、隣接する2つの家が同じ夜に侵入された場合に自動的に警察に通報されることです。
各家庭の金額を表す負ではない整数のリストを考慮して、警察に警告されずに今夜奪うことができる最大金額を求めましょう。
説明を元に問題を見てみましょう。
Example 1:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
この例の場合、1つめの家と3つめの家から奪った場合の金額が最大になるため、4が返されます。
Example 2:
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
この例の場合、1つめの家と3つめの家と5つめの家から奪った場合の金額が最大になるため、12が返されます。
解法
class Solution:
def rob(self, nums: List[int]) -> int:
pre = cur = 0
for i in nums:
pre,cur = cur,max(pre+i,cur)
return cur
# Runtime: 20 ms, faster than 98.32% of Python3 online submissions for House Robber.
# Memory Usage: 14.1 MB, less than 9.09% of Python3 online submissions for House Robber.
リストを前から舐めていき、preにcurをcurにはpre+iとcurの大きい方を代入する、ということを行えば完走できると思います。
例えば。例の[1,2,3,1]の場合は
pre = 0,1,2,4
cur = 1,2,4,4
の順で推移し、最終的に正答である4が返されます。
下手に難しく考えずに、前から舐めていく場合はどのように操作すれば上手く動作するかという点に重点を置いた方が上手く解ける問題かと思います。
良さげな解答があれば追記します。