[LeetCode] 46. Permutation

7377 ワード
leetcode Pythonアルゴリズムインタビュー テキストリンク

🔦 提问链接


🔊 파이썬 알고리즘 인터뷰冊の本を参考にしました.
  • 題
    • 可能なすべてのシーケンスを返します

    ▼▼▼▼草


  • 私が前に開いた方法で、各ステップの選択値をtmpリストに保存して、次のステップでtmpリストにない値だけを選択します.

  • リストから選択した値を除外しながら、本に示すように操作を続行します.
  • ページごとに、選択した値がリストから削除され、選択した値が個別に記録されます.
  • dfsを離れると、レコードの値が削除され、コピーされたリストから再実行されます.

    • 🛠 コード#コード#

  • code 1 
    • class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(index):
            if len(tmp) == len(nums):
                cp = tmp[:] # 파이썬의 객체 참조 특성으로 인해 꼭 복사를 해줘야 한다.d
                result.append(cp)
                return
            for i in range(len(nums)):
                if nums[i] not in tmp:
                    tmp.append(nums[i])
                    dfs(i + 1)
                    tmp.pop()
        result = []
        tmp = []
        dfs(0)
        print(result)
        return result
  • code 2 
    • class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(elements):
            if len(elements) == 0:
                result.append(prev_elements[:])
            for e in elements:
                next_elements = elements[:]
                next_elements.remove(e)
                
                prev_elements.append(e)
                dfs(next_elements)
                prev_elements.pop()
                
        result = []
        prev_elements = []
        dfs(nums)
        return result

    📝 整理する


    🎈 リファレンス


    ブックリンク
    Oracleブロック情報の表示
    [アルゴリズムの解答]携帯電話番号をブロックする