Compter le nombre maximum de sous-ensembles OR au niveau du bit

2044. Compter le nombre maximum de sous-ensembles OR au niveau du bit

Difficulté :Moyen

Sujets : Tableau, retour en arrière, manipulation de bits, énumération

Étant donné un tableau d'entiers nums, trouver le maximum possible OU au niveau du bit d'un sous-ensemble de nums et renvoyer le nombre de sous-ensembles non vides différents avec le OU au niveau du bit maximum.

Un tableau a est un sous-ensemble d'un tableau b si a peut être obtenu à partir de b en supprimant certains éléments (éventuellement zéro) de b. Deux sous-ensembles sont considérés différents si les indices des éléments choisis sont différents.

Le OU au niveau du bit d'un tableau a est égal à a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexé).

Exemple 1 :

• Entrée : nums = [3,1]
• Sortie : 2
• Explication : Le OU au niveau du bit maximum possible d'un sous-ensemble est de 3. Il existe 2 sous-ensembles avec un OU au niveau du bit de 3 :
  • [3]
  • [3,1]

Exemple 2 :

• Entrée : nums = [2,2,2]
• Sortie :7
• Explication : Tous les sous-ensembles non vides de [2,2,2] ont un OU au niveau du bit de 2. Il y a 23 - 1 = 7 sous-ensembles au total.

Exemple 3 :

• Entrée : nums = [3,2,1,5]
• Sortie : 6
• Explication : Le OU au niveau du bit maximum possible d'un sous-ensemble est de 7. Il existe 6 sous-ensembles avec un OU au niveau du bit de 7 :
  • [3,5]
  • [3,1,5]
  • [3,2,5]
  • [3,2,1,5]
  • [2,5]
  • [2,1,5]

Contraintes :

• 1 <= nums.length <= 16
• 1 <= nums[i] <= 10⁵

Indice :

1. Pouvons-nous énumérer tous les sous-ensembles possibles ?
2. Le OU au niveau du bit maximum est le OU au niveau du bit de l'ensemble du tableau.

Solution :

Nous pouvons suivre ces étapes :

1. Calculer le OU au niveau du bit maximum : Le OU au niveau du bit maximum d'un sous-ensemble peut être déterminé en effectuant une opération OU au niveau du bit sur tous les éléments du tableau. Cela nous donne le maximum possible de OU au niveau du bit.

2. Énumérer tous les sous-ensembles : Étant donné que la taille du tableau est petite (jusqu'à 16), nous pouvons énumérer tous les sous-ensembles possibles en utilisant une technique de manipulation de bits. Pour un tableau de taille n, il existe 2^n sous-ensembles possibles.

3. Compter les sous-ensembles valides : Pour chaque sous-ensemble, calculez son OU au niveau du bit et vérifiez s'il correspond au OU au niveau du bit maximum. Si c'est le cas, incrémentez un compteur.

Implémentons cette solution en PHP : 2044. Compter le nombre maximum de sous-ensembles OR au niveau du bit

  
  
  Explication:




Calcul OU au niveau du bit maximum :


Nous utilisons une boucle pour calculer le OU au niveau du bit maximum du tableau en effectuant un OU au niveau du bit sur chaque élément.



Énumération des sous-ensembles :


Nous parcourons tous les nombres de 1 à 2^n - 1 (où n est la longueur des nombres), représentant tous les sous-ensembles non vides.
Pour chaque numéro, nous vérifions chaque bit pour voir quels éléments sont inclus dans le sous-ensemble.



Nombre de sous-ensembles valides :


Après avoir calculé le OU au niveau du bit pour le sous-ensemble actuel, nous vérifions s'il est égal à maxOR. Si c'est le cas, nous incrémentons notre compteur.




Cette solution est efficace compte tenu des contraintes et devrait bien fonctionner pour des tableaux d'une taille allant jusqu'à 16, ce qui donne au plus 65 535 sous-ensembles à évaluer.

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!