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

概要

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

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

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

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

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

Leetcode

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

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day28「198. House Robber」
次回
ゼロから始めるLeetCode Day30「234. Palindrome Linked List」

問題

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に追加することで二次元配列にしています。

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

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