Let Code Day 29 "46. Permutations" à partir de zéro

Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est d'implémenter des fonctions et des classes spécifiques en fonction du thème.

En guise de contre-mesure, il semble qu'un site appelé Let Code prendra des mesures.

Un site qui forme une puissance algorithmique capable de résister aux tests de codage dont on parle très tôt.

Je pense qu'il vaut mieux avoir la puissance de l'algorithme d'un être humain, donc je vais résoudre le problème de manière irrégulière et écrire la méthode que j'ai pensé à ce moment-là sous forme de mémo.

Leetcode

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 28 "198. House Robber" à partir de zéro

En gros, je voudrais résoudre l'acceptation facile par ordre décroissant.

Twitter Je le fais.

problème

46. Permutations Le niveau de difficulté est moyen. Extrait des 100 questions les plus appréciées.

Étant donné une liste de nombres différents, le problème est de renvoyer toutes les séquences. La permutation dans le titre semble signifier une séquence.

Example:

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

Ceci est un exemple de retour de toutes les séquences.

Solution

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.

Oui. Je suis désolé. Devant Python, le Medium de Let Code est comme un bébé.

C'est la fin, merci pour le match.

Je suis désolé, c'est trop terrible, alors j'ai pensé à une autre solution.

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.

J'ai implémenté dfs séparément. Il continue de tourner avec la fonction de récurrence jusqu'à ce que le nombre d'éléments de nums soit épuisé.

Il peut être implémenté à l'aide de tranches.

Pour rappel, dans le cas de nums [: i], va du premier élément au i-ème, et dans le cas de nums [i + 1:], va du i + 1 au dernier élément. Je vais.

Ensuite, lorsque l'élément disparaît, emp est ajouté à la liste préparée à l'origine ʻans` pour en faire un tableau bidimensionnel.

C'est un peu plus rapide.

S'il y a une bonne réponse, je l'ajouterai.