Sous-tableau le plus long avec ET au niveau du bit maximum

2419. Sous-tableau le plus long avec ET au niveau du bit maximum

Difficulté :Moyen

Sujets :Tableau, manipulation de bits, casse-tête

Vous recevez un tableau d'entiers numériques de taille n.

Considérons un sous-tableaunon videà partir de nombres qui a lemaximumpossibleET au niveau du bit.

• En d'autres termes, soit k la valeur maximale du ET au niveau du bit den'importe quelsous-tableau de nombres. Ensuite, seuls les sous-tableaux avec un ET au niveau du bit égal à k doivent être pris en compte.

Renvoyerla longueur dule plus longde ce sous-tableau.

Le ET au niveau du bit d'un tableau est le ET au niveau du bit de tous les nombres qu'il contient.

Unsous-tableauest une séquence contiguë d'éléments au sein d'un tableau.

Exemple 1 :

• Entrée :nums = [1,2,3,3,2,2]
• Sortie :2
• Explication :
  • Le ET maximum possible au niveau du bit d'un sous-tableau est 3.
  • Le sous-tableau le plus long avec cette valeur est [3,3], nous renvoyons donc 2.

Exemple 2 :

• Entrée :nums = [1,2,3,4]
• Sortie :1
• Explication :
  • Le ET maximum possible au niveau du bit d'un sous-tableau est de 4.
  • Le sous-tableau le plus long avec cette valeur est [4], nous renvoyons donc 1.

Contraintes :

• 1 <= nums.length <= 10¹
• 1 <= nums[i] <= 10⁶

Indice :

1. Notez que le ET au niveau du bit de deux nombres différents sera toujours strictement inférieur au maximum de ces deux nombres.
2. Qu'est-ce que cela nous apprend sur la nature du sous-réseau que nous devrions choisir ?

Solution :

Décomposons d'abord le problème étape par étape :

Informations clés :

1. Propriétés AND au niveau du bit:

   • Le ET au niveau du bit de deux nombres est généralement inférieur ou égal aux deux nombres.
   • Par conséquent, si nous trouvons une valeur maximale dans le tableau, le sous-tableau qui atteindra cette valeur ET au niveau du bit maximale doit être constitué de cette valeur maximale répétée.

2. Objectif:

   • Trouvez la valeur maximale dans le tableau.
   • Trouvez le sous-tableau contigu le plus long de cette valeur maximale, car tout autre nombre dans le sous-tableau réduirait le résultat ET global au niveau du bit.

Plan:

1. Parcourez le tableau et déterminez la valeur maximale.
2. Parcourez à nouveau le tableau pour trouver le sous-tableau contigu le plus long où tous les éléments sont égaux à cette valeur maximale.

Exemple:

Pour le tableau d'entrée [1,2,3,3,2,2], la valeur maximale est 3. Le sous-tableau contigu le plus long avec seulement 3 est [3,3], qui a une longueur de 2.

Implémentons cette solution en PHP :2419. Sous-tableau le plus long avec ET au niveau du bit maximum

        
Explication:
        

         
Étape 1: Nous trouvons d'abord la valeur maximale dans le tableau à l'aide de la fonction max() intégrée de PHP.
         
Étape 2: Nous initialisons deux variables, $maxLength pour stocker la longueur du sous-tableau le plus long et $currentLength pour suivre la longueur du sous-tableau contigu actuel de la valeur maximale.
         
Étape 3: Nous parcourons le tableau :
          

           
Si le nombre actuel est égal à la valeur maximale, nous incrémentons la longueur du sous-tableau actuel.
           
Si le nombre actuel n'est pas égal à la valeur maximale, nous vérifions si le sous-tableau actuel est le plus long jusqu'à présent et réinitialisons la longueur.
          
         
Étape finale: Après la boucle, nous nous assurons que si le sous-tableau le plus long est à la fin du tableau, nous le considérons toujours.
         
Enfin, nous renvoyons la longueur du sous-tableau le plus long qui contient uniquement la valeur maximale.
        
Complexité temporelle :
        

         
Trouver la valeur maximale prend (O(n)).
         
Parcourir le tableau pour trouver le sous-tableau le plus long prend (O(n)).
         
Complexité temporelle globale : (O(n)), où (n) est la longueur du tableau.
        
Cas de tests :
Pour l'entrée [1, 2, 3, 3, 2, 2], la sortie est 2, et pour [1, 2, 3, 4], la sortie est 1, comme prévu.
Cette solution gère les contraintes et résout efficacement le problème.
Liens de contact
Si vous avez trouvé cette série utile, pensez à donner une étoile auréférentielsur 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!