Trouver le Kième bit dans la Nième chaîne binaire

1545. Trouver le Kième bit dans la Nième chaîne binaire

Difficulté :Moyen

Sujets : Chaîne, Récursion, Simulation

Étant donné deux entiers positifs n et k, la chaîne binaire S_n se forme comme suit :

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

Où désigne l'opération de concaténation, reverse(x) renvoie la chaîne inversée x et invert(x) inverse tous les bits de x (0 passe à 1 et 1 passe à 0).

Par exemple, les quatre premières chaînes de la séquence ci-dessus sont :

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

Renvoyer le k^ième bit dans S_n. Il est garanti que k est valable pour le n donné.

Exemple 1 :

• Entrée : n = 3, k = 1
• Sortie : "0"
• Explication :S₃ est "0111001". Le 1^er bit est "0".

Exemple 2 :

• Entrée : n = 4, k = 11
• Sortie : "1"
• Explication :S₄ est "011100110110001". Le 11^ème bit est "1".

Exemple 3 :

• Entrée : n = 3, k = 2
• Sortie : "0"

Contraintes :

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

Indice :

1. Puisque n est petit, nous pouvons simplement simuler le processus de construction de S1 en Sn.

Solution :

Nous devons comprendre le processus récursif utilisé pour générer chaque chaîne binaire S_n et l'utiliser pour déterminer le k-ième bit sans construire l'intégralité chaîne.

Approche:

1. Construction de chaînes récursives :

   • S₁ = "0".
   • Pour moi > 1 :
     • S_i est construit comme : S_i = S_i-1 "1" inverse(inverser(S_i-1))
   • Cela signifie S_i se compose de trois parties :
     • S_i-1 (la pièce d'origine)
     • "1" (le bit du milieu)
     • reverse(invert(S_i-1)) (la partie transformée)

2. Observations clés :

   • S_i a une longueur de 2^i-1.
   • Le bit du milieu (position 2^i-1 de S_i est toujours "1".
   • Si k se situe dans la première moitié, il tombe dans S_i-1.
   • Si k est exactement la position médiane, la réponse est "1".
   • Si k est dans la seconde moitié, cela correspond à la partie inversée-inverse.

3. Inversion et inversion :

   • Pour déterminer le bit dans la seconde moitié, mappez k à sa position correspondante dans la première moitié en utilisant : k' = 2ⁱ - k
   • Le bit à cette position dans la moitié d'origine est inversé, nous devons donc inverser le résultat.

4. Solution récursive :

   • Déterminez de manière récursive le k-ème bit en réduisant n et en mappant k jusqu'à n=1.

Implémentons cette solution en PHP : 1545. Trouver le Kième bit dans la Nième chaîne binaire


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

Explication:

• Cas de base : Si n = 1, S_i est "0" , donc la seule valeur possible pour tout k est "0".
• Étapes récursives :
  • Calculez l'indice du milieu mid qui est 2^n-1.
  • Si k correspond à l'index du milieu, renvoie "1".
  • Si k est inférieur au milieu, le k-ème le bit se situe dans la première moitié, nous trouvons donc récursivement le k-ième bit dans S_n-1.
  • Si k est supérieur à mid, on retrouve le bit correspondant dans la seconde moitié inversée et on le retourne.

Analyse de complexité :

• Complexité temporelle : O(n) car chaque appel récursif réduit n de 1.
• Complexité spatiale : O(n) pour la pile d'appels récursifs.

Exemple de procédure pas à pas :

1. Entrée : n = 3 , k = 1

   • S₃ = "0111001"
   • k = 1 tombe en première mi-temps, on cherche donc k = 1 dans S₂.
   • En S₂ = "011" , k = 1 correspond à "0".

2. Entrée : n = 4 , k = 11

   • S₄ = "011100110110001"
   • L'indice du milieu pour S₄ est 8.
   • k = 11 tombe en seconde période.
   • Mappez k = 11 au bit correspondant dans la première moitié : k' = 2 ^{4 - 11 = 5}.
   • Trouvez k = 5 dans S₃ , qui vaut "0", puis retournez-le à "1".

En tirant parti de la récursivité et des propriétés de la construction de la chaîne, cette solution évite de générer la chaîne entière, ce qui la rend efficace même pour les n plus grands.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!