Finden Sie das K-te Bit im N-ten Binärstring

1545. Finden Sie das K-te Bit im N-ten Binärstring

Schwierigkeit:Mittel

Themen:String, Rekursion, Simulation

Bei zwei positiven ganzen Zahlen n und k wird die Binärzeichenfolge S_n wie folgt gebildet:

• S₁ = "0"
• S_i = S_{i - 1} "1" reverse(invert(S_{i - 1})) für i > 1

Wobei bezeichnet die Verkettungsoperation, reverse(x) gibt die umgekehrte Zeichenfolge x zurück und invert(x) invertiert alle Bits in x (0 ändert sich in 1 und 1 ändert sich in 0).

Zum Beispiel sind die ersten vier Zeichenfolgen in der obigen Sequenz:

• S₁ = "0"
• S₂ = "011"
• S₃ = "0111001"
• S₄ = "011100110110001"

Gibt das k^te Bit in S_n zurück. Es ist garantiert, dass k für das gegebene n gültig ist.

Beispiel 1:

• Eingabe: n = 3, k = 1
• Ausgabe: „0“
• Erklärung:S₃ ist „0111001“. Das 1^ste Bit ist „0“.

Beispiel 2:

• Eingabe: n = 4, k = 11
• Ausgabe: „1“
• Erklärung:S₄ ist „011100110110001“. Das 11^te Bit ist „1“.

Beispiel 3:

• Eingabe: n = 3, k = 2
• Ausgabe: „0“

Einschränkungen:

• 1 <= n <= 20
• 1 <= k <= 2ⁿ - 1

Hinweis:

1. Da n klein ist, können wir den Prozess der Konstruktion von S1 bis Sn einfach simulieren.

Lösung:

Wir müssen den rekursiven Prozess verstehen, der zum Generieren jeder Binärzeichenfolge S_n verwendet wird, und diesen verwenden, um das k-te Bit zu bestimmen, ohne das Ganze zu konstruieren Zeichenfolge.

Ansatz:

1. Rekursive String-Konstruktion:

   • S₁ = "0".
   • Denn ich > 1:
     • S_i ist wie folgt aufgebaut: S_i = S_i-1 "1" reverse(invert(S_i-1))
   • Das bedeutet, dass S_i aus drei Teilen besteht:
     • S_i-1 (das Originalteil)
     • „1“ (das mittlere Bit)
     • reverse(invert(S_i-1)) (der transformierte Teil)

2. Wichtige Beobachtungen:

   • S_i hat eine Länge von 2^i-1.
   • Das mittlere Bit (Position 2^i-1 von S_i ist immer „1“.
   • Wenn k in der ersten Hälfte liegt, fällt es in S_i-1.
   • Wenn k genau die mittlere Position ist, ist die Antwort „1“.
   • Wenn k in der zweiten Hälfte liegt, entspricht es dem umgekehrt invertierten Teil.

3. Umkehren und Umkehren:

   • Um das Bit in der zweiten Hälfte zu bestimmen, ordnen Sie k der entsprechenden Position in der ersten Hälfte zu, indem Sie Folgendes verwenden: k' = 2ⁱ - k
   • Das Bit an dieser Position in der Originalhälfte ist invertiert, daher müssen wir das Ergebnis umdrehen.

4. Rekursive Lösung:

   • Bestimmen Sie rekursiv das k-te Bit, indem Sie n reduzieren und k bis n = 1.
Lassen Sie uns diese Lösung in PHP implementieren:

1545. Finden Sie das K-te Bit im N-ten Binärstring


<?php
/**
 * @param Integer $n
 * @param Integer $k
 * @return String
 */
function findKthBit($n, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

Erläuterung:
• Basisfall: Wenn n = 1, ist Si „0“ , daher ist der einzig mögliche Wert für jedes k „0“.
• Rekursive Schritte:
  Berechnen Sie den mittleren Index
  • mid, der 2n-1 ist.
  Wenn
  • k mit dem mittleren Index übereinstimmt, wird „1“ zurückgegeben.
  Wenn
  • k kleiner als Mitte ist, wird der k-th Das Bit liegt in der ersten Hälfte, daher finden wir rekursiv das k-te Bit in Sn-1.
  Wenn
  • k größer als mid ist, finden wir das entsprechende Bit in der umgekehrt invertierten zweiten Hälfte und drehen es um.
Komplexitätsanalyse:
• Zeitkomplexität: O(n), da jeder rekursive Aufruf n um 1 reduziert.
• Raumkomplexität: O(n) für den rekursiven Aufrufstapel.
Beispielhafte Vorgehensweise:

1. Eingabe: n = 3 , k = 1

   • S₃ = "0111001"
   • k = 1 fällt in die erste Hälfte, also suchen wir nach k = 1 in S₂.
   • In S₂ = "011" , k = 1 entspricht „0“.

2. Eingabe: n = 4 , k = 11

   • S₄ = "011100110110001"
   • Der mittlere Index für S₄ ist 8.
   • k = 11 fällt in die zweite Hälfte.
   • Ordnen Sie k = 11 dem entsprechenden Bit in der ersten Hälfte zu: k' = 2 ^{4 - 11 = 5}.
   • Finden Sie k = 5 in S₃ , was „0“ ist, und drehen Sie es dann um auf „1“.

Durch die Nutzung der Rekursion und der Eigenschaften der String-Konstruktion vermeidet diese Lösung die Generierung des gesamten Strings und macht sie so auch für größere n effizient.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonFinden Sie das K-te Bit im N-ten Binärstring. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!