Fin minimale du tableau

3133. Fin minimale du tableau

Difficulté :Moyen

Sujets : Manipulation des bits

Vous recevez deux entiers n et x. Vous devez construire un tableau de nombres entiers positifs de taille n où pour chaque 0 <= i < n - 1, nums[i 1] est supérieur à nums[i], et le résultat de l'opération ET au niveau du bit entre tous les éléments de nums est x.

Renvoyer la valeur minimale possible de nums[n - 1].

Exemple 1 :

• Entrée : n = 3, x = 4
• Sortie : 6
• Explication : les nombres peuvent être [4,5,6] et son dernier élément est 6.

Exemple 2 :

• Entrée : n = 2, x = 7
• Sortie : 15
• Explication : les nombres peuvent être [7,15] et son dernier élément est 15.

Exemple 3 :

• Entrée : coût = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• Sortie : 10

Contraintes :

• 1 <= n, x <= 10⁸

Indice :

1. Chaque élément du tableau doit être obtenu en « fusionnant » x et v où v = 0, 1, 2,…(n - 1).
2. Pour fusionner x avec un autre nombre v, gardez les bits définis de x intacts, pour tous les autres bits, remplissez les bits définis de v de droite à gauche dans l'ordre un par un.
3. La réponse finale est donc la « fusion » de x et n - 1.

Solution :

Nous devons construire un tableau nums d'entiers positifs de taille n, où chaque élément successif est supérieur au précédent. Le ET au niveau du bit de tous les éléments en nombres devrait donner x. On nous demande de trouver la valeur minimale possible de nums[n-1].

Voici la répartition :

1. Bit Manipulation Insight : Nous pouvons observer que nums[i] doit être construit en fusionnant x avec les entiers 0, 1, ..., n-1. Cela aidera à garantir que le résultat ET au niveau du bit donne x puisque nous commençons avec une base de x.

2. Construire les éléments du tableau : Chaque élément peut être considéré comme x fusionné avec un entier, et nous visons à garder les bits de x intacts. Nous remplissons des bits supplémentaires à partir de l'entier pour obtenir des nombres croissants tout en conservant le résultat ET comme x.

3. Stratégie de fusion : Pour trouver les nombres minimum[n-1], il suffit de fusionner x avec n-1. La fusion dans ce contexte signifie que si un bit de x est 1, il reste 1. Nous utilisons les bits de n-1 pour ajouter les bits supplémentaires requis sans modifier les bits définis dans x.

Implémentons cette solution en PHP : 3133. Fin minimale du tableau

  
  
  Explication:




Vérification et réglage des bits :


On vérifie chaque bit de ans (en partant de x), et si un bit vaut 0 dans ans, on regarde le bit correspondant dans k (qui est n-1).
Si ce bit dans k est 1, nous définissons le bit dans ans sur 1. Ce processus garantit l'incrément de valeur minimum tout en préservant les bits définis dans x.



Contraintes de boucle :


Nous parcourons chaque position de bit jusqu'à un maximum calculé (kMaxBit), en nous assurant de couvrir les bits nécessaires à la fois de x et de n.



Résultat :


La valeur finale de ans est la valeur minimale possible pour nums[n-1] qui satisfait aux conditions.





  
  
  Complexité:



L'algorithme fonctionne en temps constant puisque le nombre de bits de tout entier dans cette plage est limité par 32, ce qui rend cette approche efficace même pour les grandes valeurs de n et x.


Cette solution donne les nombres minimum souhaités[n-1] tout en conservant les propriétés requises.

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!