[PYTHON] Lassen Sie Code Day 29 "46. Permutationen" von vorne beginnen

Überblick

Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.

Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.

Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.

Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.

Leetcode

Leet Code-Tabelle ab Null

Letztes Mal Leet Code Tag 28 "198. Hausräuber" ab Null

Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.

Twitter Ich mache es.

Problem

46. Permutations Der Schwierigkeitsgrad ist Mittel. Auszug aus den 100 beliebtesten Fragen.

Das Problem besteht darin, alle Sequenzen mit einer Liste unterschiedlicher Nummern zurückzugeben. Die Permutation im Titel scheint eine Sequenz zu bedeuten.

Example:

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

Dies ist ein Beispiel für die Rückgabe aller Sequenzen.

Lösung

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.

Ja. Es tut mir Leid. Vor Python ist das Medium Let Code wie ein Baby.

Dies ist das Ende, danke für das Match.

Es tut mir leid, das ist zu schrecklich, also habe ich über eine andere Lösung nachgedacht.

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.

Ich habe dfs separat implementiert. Es dreht sich mit der Wiederholungsfunktion weiter, bis die Anzahl der Elemente von nums erschöpft ist.

Es kann mit Slices implementiert werden.

Zur Erinnerung: Gehen Sie im Fall von nums [: i] vom ersten zum i-ten Element und im Fall von nums [i + 1:] vom i + 1th zum letzten Element. Ich werde.

Wenn das Element dann verschwindet, wird emp zum "ans" der ursprünglich vorbereiteten Liste hinzugefügt, um es zu einem zweidimensionalen Array zu machen.

Das geht etwas schneller.

Wenn es eine gute Antwort gibt, werde ich sie hinzufügen.