[PYTHON] [Leet Code-Lerndatensatz] Zick-Zack-Konvertierung gelöst

Heute habe ich [ZigZag Conversion] gelöst (https://leetcode.com/problems/zigzag-conversion/). Notieren Sie sich, was Sie darin gelernt haben. Ich bin neu in Python und habe gerade Probleme wie LetCode gestartet. Daher würde ich gerne Fehler oder Ratschläge hören.

Problemstellung

Wenn numRows = 3 für die Zeichenfolge s = "PAYPALISHIRING" angegeben ist

result

P A H N
APLSIIG
Y I R

Es wird gezackt wie. Die Ausgabe ist "PAHNAPLSIIGYIR", in der jede Zeile in der Reihenfolge von links angeordnet ist.

Der Code, den ich zuerst geschrieben habe

Politik

• Für die angegebene Zeichenfolge s ist key = like 0,1, ..., (numRows-1), (numRows-2), ..., 1,0, ... von Anfang an. Ordnen Sie 0,1, ..., numRows-1 zu.
• Benötigen Sie die Kennung "Inc", um das Inkrement / Dekrement zu bestimmen?
• Kombiniert in aufsteigender Reihenfolge des Schlüssels und gibt ihn als Ausgabe zurück. ――Wie kann ich Strings kombinieren?

Basierend auf der obigen Richtlinie habe ich den folgenden Code geschrieben:

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        #Umgang mit Kantengehäusen
        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

Stolperpunkt

So speichern Sie Elemente mit demselben Schlüssel

Für s [i] mit dem gleichen Schlüssel,

d[key] = s[i]

Dann wurde der Wert überschrieben. Dies wurde mithilfe der Listenmethode "append ()" behoben, um am Ende ein Element hinzuzufügen. Es gibt viele andere listenbezogene Methoden, die ich möglicherweise in Zukunft verwenden werde, daher werde ich sie in Zukunft untersuchen.

So konvertieren Sie eine Liste in eine Zeichenfolge

Das d unmittelbar nach der for-Schleife ist

{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']}

Es war so. Ich dachte, es wäre mühsam, mit einer for-Schleife zu verbinden, also habe ich nachgeschlagen und eine Methode join () gefunden, die die Liste in eine Zeichenfolge konvertiert. Zum Beispiel

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

so werden. Wenn diesmal nichts in "" eingefügt wird, wird es einfach verbunden. Wenn Sie dann die Zeichenfolge "join" in aufsteigender Reihenfolge von "key" zu "ans" hinzufügen, erhalten Sie die gewünschte "Ausgabe".

Codeverbesserungen

In LeetCode ist "Diskutieren", mit dem Sie den Code sehen können, an den andere gedacht haben, sehr gut. Für dieses Problem habe ich auf [hier] verwiesen (https://leetcode.com/problems/zigzag-conversion/discuss/3404/Python-O(n)-Solution-in-96ms-(99.43)). Der verbesserte Code wird unten gezeigt:

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) Die Ausführungszeit könnte also auf 1/2 oder weniger reduziert werden.

Initialisierung des Listenarrays

Zum Beispiel

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

Beim Erstellen eines Listenarrays wie z

L = [''] * 3

Wenn ja, habe ich gelernt, dass das Gleiche wie oben gemacht werden kann. Diesmal numRows von 0 bis numRows-1 Es ist klar, dass dieses Element notwendig ist, daher ist dies flexibler und expliziter.

Verbesserung der Klassifizierung nach Schlüssel

Wenn ich jetzt darüber nachdenke, habe ich festgestellt, dass es bei demselben "Schlüssel" möglich ist, einen Schritt zu reduzieren, indem man von Anfang an kombiniert und nicht durch "append ()". Auf diese Weise müssen Sie die Zeichenfolgen nicht erneut mit der for-Schleife nach der for-Schleife verbinden, sondern nur mit ''. Join ().