ゼロから始めるLeetCode Day28「198. House Robber」

概要

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

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

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

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

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

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day27「101. Symmetric Tree」
次回
ゼロから始めるLeetCode Day29「46. Permutations」

問題

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.

リストを前から舐めていき、precurcurにはpre+icurの大きい方を代入する、ということを行えば完走できると思います。

例えば。例の[1,2,3,1]の場合は

pre = 0,1,2,4
cur = 1,2,4,4

の順で推移し、最終的に正答である4が返されます。

下手に難しく考えずに、前から舐めていく場合はどのように操作すれば上手く動作するかという点に重点を置いた方が上手く解ける問題かと思います。

良さげな解答があれば追記します。

コメント

このブログの人気の投稿

Braveブラウザの同期機能をiPhoneで設定した話。

failed: unable to get local issuer certificate (_ssl.c:1123)と出たので解決した話

自作のChrome Extensionをインポートした時に "Invalid value for 'content_scripts[0].matches[0]': Empty path."というエラーが出たので解決した