ゼロから始めるLeetCode Day109「213. House Robber II」

• 概要
• 問題
• 解法

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day108「300. Longest Increasing Subsequence」

次回
ゼロから始めるLeetCode Day110「1535. Find the Winner of an Array Game」

Twitterやってます。

問題

213. House Robber II
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、あなたは街中の家々を襲っているプロの強盗です。それぞれの家には一定の金額のお金が隠されています。この場所にある全ての家は円を描くように配置されています。つまり、最初の家は最後の家の隣人です。一方、隣の家にはセキュリティシステムが接続されており、同じ夜に隣の家に侵入された場合、自動的に警察に連絡してくれる。
各家の金額を表す非負の整数のリストが与えられたとき，警察に通報せずに今夜奪える最大金額を決定する、というものです。

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
because they are adjacent houses.

Example 2:

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.

解法

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) < 2:
            return max(nums)
        return max(self.helper(nums[1:]), self.helper(nums[:-1]))        
    
    def helper(self, nums):
        pre_max = cur_max = 0
        for num in nums:
            swap = cur_max
            cur_max = max(pre_max + num, cur_max)
            pre_max = swap
        return cur_max
# Runtime: 20 ms, faster than  99.72%  of  Python3  online submissions for  House Robber II.
# Memory Usage: 13.9 MB, less than  43.51%  of  Python3  online submissions for  House Robber II.

以前解いた

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

の発展問題です。

以前は最初と最後が隣接していない設定だったのですが、今回は隣接している設定のため、少し問題が複雑になっています。

といっても、行っていること自体は基本的には変わらないです。

二つのランナーを用意する一方で

例えば、今回のテストケースである

nums = [2,3,2]

で考えてみると、

pre_max = [0,3,0,2]

cur_max = [3,3,2,3]

となります。

これはhelper関数の引数でnums[1:]とnums[:-1]を与えているためで、これらはスライスといって特定のインデックスから要素を抽出するために使っています。
Pythonではインデックスの数え上げが0から始まるため、今回はインデックスが1からスタートするようにしています。

すなわち、その値を取っているnums[1:]のリストは以下のようになります。

[3,2]

逆にこれをnums[:-1]の場合は以下のようになります。

[2,3]

これらをまとめて出力しているために最初のような表記になってしまうわけなんですね。

また、なぜリストの中の二つ目の要素である1から、そして逆順の-1から取得しているか、についてですが、最初と最後の値が隣接している、という設定が追加されたためです。

この設定を解決するためには、あえて最初の要素を無かったことにして対応するのが分かりやすいです。

すなわち、

 2
| |
3-2

といった形からnums[0]とnums[-1]を削除することで以下のようになります。

3-2

2
|
3

ここまで説明すれば分かった方も多いと思いますが、これらの処理を行うことで、残った要素に対して
ゼロから始めるLeetCode Day28「198. House Robber」
と同じ処理を行うと解答が出るのです。

今回はたまたま要素が3つのために最大値を出すだけとなっていますが、仮に要素が増えたとしてもきっちり動作する理由がわかるかと思います。

こういった追加の条件付けを行わなければならない点が発展問題、と言えるのかもしれませんね。

少し普段よりも解説が長くなりましたが今回はここまで。お疲れ様でした。