概要

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

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

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

Leetcode

ゼロから始めるLeetCode 目次

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

基本的にeasyのacceptanceが高い順から解いていこうかと思います。

Twitterやってます。

問題

46. Permutations
難易度はMedium。
Top 100 Liked Questionsからの抜粋です。

異なる数字を集めたリストが与えられるので、全ての順列を返しなさい、という問題です。
タイトルのPermutationは順列という意味らしいですよ。

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

これが全ての順列を返している例ですね。

解法

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))
# Runtime: 36 ms, faster than 87.99% of Python3 online submissions for Permutations.
# Memory Usage: 14.1 MB, less than 5.36% of Python3 online submissions for Permutations.

はい。
あっけないですね。Python様の前ではLeetCodeのMediumも赤子同然です。

これにて終了です、対戦ありがとうございました。

ごめんなさい、流石にこれだとあまりにもひどいので他に解法を考えました。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        self.dfs(nums, [], ans)
        return ans

    def dfs(self, nums, emp, ans):
        if not nums:
            ans.append(emp)
        for i in range(len(nums)):
            self.dfs(nums[:i]+nums[i+1:], emp+[nums[i]], ans)
# Runtime: 32 ms, faster than 96.70% of Python3 online submissions for Permutations.
# Memory Usage: 13.9 MB, less than 5.36% of Python3 online submissions for Permutations.

dfsを別個に考えて実装しました。
numsの要素数が尽きるまで再起関数で回し続けるというものです。

スライスを使えば実装できます。

念のために書いておきますが、nums[:i]の場合は最初の要素からi番目までを取得し、nums[i+1:]の場合はi+1番目から最後の要素まで取得します。

そして、要素が無くなったときにempを元々用意していたリストのansに追加することで二次元配列にしています。

こちらの方が若干速くなりました。

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

ゼロから始めるLeetCode Day29「46. Permutations」

概要

問題

解法