[PYTHON] [Enregistrement d'apprentissage Leet Code] Résolution de la conversion en ZigZag

Aujourd'hui, j'ai résolu Conversion ZigZag. Notez ce que vous y avez appris. Je suis nouveau sur Python et je viens de commencer des problèmes comme LetCode, donc j'aimerais entendre des erreurs ou des conseils.

Problème de réglage

Lorsque numRows = 3 est donné à la chaîne de caractères s = "PAYPALISHIRING"

result

P A H N
APLSIIG
Y I R

Cela devient déchiqueté comme. La sortie est "PAHNAPLSIIGYIR" dans lequel chaque ligne est organisée dans l'ordre à partir de la gauche.

Le code que j'ai écrit en premier

politique

--Pour la chaîne de caractères donnée s, key = like 0,1, ..., (numRows-1), (numRows-2), ..., 1,0, ... depuis le début. Allouez 0,1, ..., numRows-1. --Besoin de l'identifiant ʻInc` pour déterminer l'incrémentation / décrémentation? --Combine dans l'ordre croissant de la clé et la renvoie en sortie. ――Comment puis-je combiner des chaînes?

Sur la base de la politique ci-dessus, j'ai écrit le code suivant:

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        #Gestion des boîtiers Edge
        if(numRows <= 1):
            return s
        
        d = defaultdict(list)
        Inc = True
        key = 0
        # label 0, 1,2,...,numRows,numrows-1,...,1,0,...
        for i in range(len(s)):
            d[key].append(s[i])
            if(key == numRows - 1):
                Inc = False
            elif(key == 0):
                Inc = True
            if(Inc == True):
                key += 1
            else:
                key -= 1
                
        # join d
        ans = ''
        for i in range(numRows):
            ans += ''.join(d[i])
        return ans

Runtime: 64ms Memory: 12.8MB

Point de trébuchement

Comment stocker des éléments avec la même clé

Pour s [i] avec la même clé,

d[key] = s[i]

Ensuite, la valeur a été écrasée. Cela a été résolu en utilisant la méthode list ʻappend () `pour ajouter un élément à la fin. Il existe de nombreuses autres méthodes liées aux listes que je pourrais utiliser à l'avenir, je les étudierai donc à l'avenir.

Comment convertir une liste en chaîne

Le d immédiatement après la boucle for est

{0: [u'P', u'A', u'H', u'N'], 
1: [u'A', u'P', u'L', u'S', u'I', u'I', u'G'], 
2: [u'Y', u'I', u'R']}

C'était comme ça. Je pensais que ce serait un problème de rejoindre en utilisant une boucle for, alors je l'ai recherchée et j'ai trouvé une méthode join () qui convertit la liste en une chaîne. Par exemple

d[0] = ['P','A','H','N']
'.'.join(d[0]) # => 'P.A.H.N'

devenir de cette façon. Cette fois, si rien n'est mis dans '', il sera simplement connecté. Ensuite, en ajoutant les chaînes de caractères «join» à «an» dans l'ordre croissant de «clé», la «sortie» souhaitée peut être obtenue.

Améliorations du code

Dans LeetCode, "Discuter" qui vous permet de voir le code que d'autres ont pensé est très bon. Pour ce problème, je me suis référé à ici. Le code amélioré est illustré ci-dessous:

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if(numRows <= 1):
            return s        
        
        d = [""] * numRows
        Inc = True
        key = 0

        for i in range(len(s)):
            d[key] += s[i]
            if(key == numRows - 1):
                Inc = False
            elif(key == 0):
                Inc = True
            if(Inc == True):
                key += 1
            else:
                key -= 1
                
        
        return ''.join(d)

Runtime: 28ms(<= 64ms) Memory:12.7MB(<=12.7MB) Ainsi, le temps d'exécution pourrait être réduit à 1/2 ou moins.

Initialisation du tableau de liste

Par exemple

L = ['','','']

Lors de la création d'un tableau de liste tel que

L = [''] * 3

Si oui, j'ai appris que la même chose que ci-dessus peut être faite. Cette fois, numRows de 0 à numRows-1 Il est clair que cet élément est nécessaire, donc ce sera plus flexible et explicite.

Amélioration de la classification par clé

Quand j'y pense maintenant, j'ai remarqué que dans le cas de la même «clé», une étape peut être réduite en combinant depuis le début plutôt que par «append ()». En faisant cela, vous n'avez pas besoin de joindre à nouveau les chaînes de caractères en utilisant la boucle for après la boucle for, et vous n'avez qu'à utiliser `` '. Join () `.