Website-Suche

Python3-Programm zum Ermitteln der maximalen Anzahl von Nullen, die nacheinander am Anfang und am Ende einer beliebigen Rotation eines Binärstrings platziert werden

In diesem Problem schreiben wir den Python-Code, um die maximale Summe aufeinanderfolgender Nullen am Anfang und Ende der Zeichenfolge zu zählen.

Die Problemlösung lässt sich in zwei Teile gliedern. Der erste Teil besteht darin, alle Drehungen der Saite zu ermitteln. Der zweite Teil besteht darin, die aufeinanderfolgenden Anfangs- und Endnullen in allen Rotationen der Binärzeichenfolge zu finden.

Eine andere Möglichkeit, das Problem zu lösen, besteht darin, dass das Zählen der maximalen aufeinanderfolgenden Nullen das Problem lösen kann.

Problemstellung – Wir müssen die Gesamtzahl der maximalen aufeinanderfolgenden Nullen am Anfang und Ende einer beliebigen Rotation der gegebenen Binärzeichenfolge ermitteln.

Beispiele

Eingabe 

str = "00100100"

Ausgabe 

4

Erklärung – Nehmen wir alle Drehungen der angegebenen Zeichenfolge.

  • 00100100 – Anfangsnullen – 2, Endnullen – 2, Summe – 4.

  • 01001000 – Anfangsnullen – 1, Endnullen – 3, Summe – 4.

  • 10010000 – Anfangsnullen – 0, Endnullen – 4, Summe – 4.

  • 00100001 – Anfangsnullen – 2, Endnullen – 0, Summe – 2.

  • 01000010 – Anfangsnullen – 1, Endnullen – 1, Summe – 2.

  • 10000100 – Anfangsnullen – 0, Endnullen – 2, Summe – 2.

  • 00001001 – Anfangsnullen – 4, Endnullen – 0, Summe – 4.

  • 00010010 – Anfangsnullen – 3, Endnullen – 1, Summe – 4.

Eingabe 

str = ‘00000000’

Ausgabe 

8

Erklärung – Da die Zeichenfolge nur Nullen enthält, entspricht die Antwort der Zeichenfolgenlänge.

Eingabe 

str = ‘111111111’

Ausgabe 

0

Erklärung – Da die Zeichenfolge nur „1“ enthält, ist die Antwort 0.

Ansatz 1

Wir werden die Zeichenfolge mit sich selbst in Kontakt bringen und ausgehend von jedem Index Teilzeichenfolgen der Länge N erhalten, um die Rotationszeichenfolge zu erhalten. Danach berechnen wir die Summe der Anfangs- und Endnullen.

Algorithmus

Schritt 1 – Definieren Sie „totalOnes“-Variablen, um die Anzahl der „1“ in der angegebenen Binärzeichenfolge zu speichern.

Schritt 2 – Verwenden Sie die Schleife, um die Zeichenfolge zu durchlaufen. Wenn str[p] gleich „1“ ist, erhöhen Sie totalOnes um 1.

Schritt 3 – Wenn der Wert der Variable „totalOnes“ Null ist, drucken Sie die Länge der Zeichenfolge aus, da die Zeichenfolge nur Nullen enthält.

Schritt 4 – Verwenden Sie den Operator „+=“, um die Zeichenfolge „str“ mit sich selbst zu verketten und die Variable „maxZeros“ zu definieren.

Schritt 5 – Durchlaufen Sie die verkettete Zeichenfolge. Definieren Sie die Variablen „startZeros“ und „endZeros“.

Schritt 6 – Durchlaufen Sie den Teilstring von p nach p + len-Index. Wenn das Zeichen am Index q nicht „0“ ist, unterbrechen Sie die Schleife. Andernfalls erhöhen Sie „totalZeros“ um 1.

Schritt 7 – Durchlaufen Sie den Teilstring von p + len -1 bis p. Wenn das Zeichen am Index q nicht vorhanden ist, unterbricht „0“ die Schleife. Andernfalls erhöhen Sie die Anzahl von „endZeros“.

Schritt 8 – Ermitteln Sie die Summe der Anfangs- und Endnullen.

Schritt 9 – Verwenden Sie die Methode max(), um das Maximum aus sum und maxZeros zu ermitteln.

Schritt 10 – Drucken Sie den Wert von maxZeros.

Beispiel

def countStartEndZeros(str, len):
    # variable to store count of ones
    totalOnes = 0
    # Traverse the string
    for p in range(len):
        if (str[p] == '1'):
            totalOnes += 1
    # If the string doesn't contain any 1, print the len value
    if (totalOnes == 0):
        print('The maximum sum of starting and end zeros in the rotation of the string is - {}'.format(len))
        return
    # Merge the string
    str += str
    # Maximum zeros
    maxZeros = 0

    # Traverse the merged string
    for p in range(len):
        startZeros = 0
        endZeros = 0
        # total zeros at start
        for q in range(p, p + len):
            if (str[q] != '0'):
                break
            else:
                startZeros += 1

        # total zeros at the end
        for q in range(p + len - 1, p - 1, -1):
            if (str[q] != '0'):
                break
            else:
                endZeros += 1
        # sum of zeros at start and end
        sum = startZeros + endZeros
        # change maxZeros if the sum is greater
        maxZeros = max(sum, maxZeros)
    print('The maximum sum of starting and end zeros in the rotation of the string is - {}'.format(maxZeros))
if __name__ == "__main__":
    # Given string
    str = "00100100"
    str_size = len(str)
    countStartEndZeros(str, str_size)

Ausgabe

The maximum sum of starting and end zeros in the rotation of the string is - 4

Zeitkomplexität – O(N*N) zum Finden jeder String-Rotation.

Raumkomplexität – O(N) zum Speichern verketteter Zeichenfolgen.

Ansatz 2

Bei diesem Ansatz lösen wir das Problem anhand der Beobachtung aufeinanderfolgender Nullstellen. Die Lösung für das Problem ist entweder die maximale Anzahl aufeinanderfolgender Nullen oder die Summe der Anfangs- und Endnullen in der ursprünglichen Binärzeichenfolge.

Algorithmus

Schritt 1 – Drucken Sie die Zeichenfolgenlänge, wenn die Gesamtzahl der Einsen in der Binärzeichenfolge 0 ist.

Schritt 2 – Definieren Sie die Maxi-Variable, um die maximale Summe der Start- und Endnullen in jeder Rotation zu speichern.

Schritt 3 – Definieren Sie die Variable „zeroConsecutive“, um die maximale Anzahl aufeinanderfolgender Nullen in der Zeichenfolge zu speichern.

Schritt 4 – Durchlaufen Sie die Zeichenfolge und das Zeichen am p-ten Index ist „0“, addieren Sie 1 zu „zeroConsecutive“. Andernfalls verwenden Sie die Methode max(), um das Maximum aus Maxi und ZeroConsecutive zu ermitteln, und speichern Sie das Ergebnis in „Maxi“. Initialisieren Sie außerdem „zeroConsecutive“ mit Null neu.

Schritt 5 – Ermitteln Sie als Nächstes die Gesamtzahl der aufeinanderfolgenden Nullen am Anfang und Ende der Zeichenfolge.

Schritt 6 – Aktualisieren Sie erneut den Wert der Variablen „maxi“, wenn der Wert von „zeroConsecutive“ größer ist.

Schritt 7 – Drucken Sie den Wert der Variablen „Maxi“.

Beispiel

def countStartEndZeros(binStr, bin_size):
    # one counts
    cnt1 = 0
    for p in range(bin_size):
        if (binStr[p] == '1'):
            cnt1 += 1
    # print len if string size is equal to zero count
    if (cnt1 == bin_size):
        print('The maximum sum of starting and end zeros in the rotation of the string is - {}'.format(bin_size))
        return
    # maximum sum
    maxi = 0
    zeroConsecutive = 0
    for p in range(bin_size):
        if (binStr[p] == '0'):
            zeroConsecutive += 1
        else:
            maxi = max(maxi, zeroConsecutive)
            zeroConsecutive = 0

    # Change value of maxi
    maxi = max(maxi, zeroConsecutive)
    # start and end zeros
    left = 0
    right = bin_size - 1
    zeroConsecutive = 0
    # lef tzeros
    while (binStr[left] != '1' and left < bin_size):
        zeroConsecutive += 1
        left += 1
    # right zeros
    while (binStr[right] != '1' and right >= 0):
        zeroConsecutive += 1
        right -= 1
    # Change value of maxi
    maxi = max(maxi, zeroConsecutive)
    print('The maximum sum of starting and end zeros in the rotation of the string is - {}'.format(maxi))

if __name__ == "__main__":
    # Given string
    str = "00100100"
    str_size = len(str)
    countStartEndZeros(str, str_size)

Ausgabe

The maximum sum of starting and end zeros in the rotation of the string is - 4

Zeitkomplexität – O(N) zum Durchlaufen der Zeichenfolge.

Raumkomplexität – O(1)

Programmierer sollten immer versuchen, die optimale Lösung für das Problem zu finden. Zunächst können wir beginnen, das Problem mit dem naiven Ansatz zu lösen, wie wir es beim ersten Ansatz getan haben. Danach können wir es weiter optimieren, wie wir es im zweiten Ansatz getan haben.

Verwandte Artikel: