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-tableau non vide à partir de nombres qui a le maximum possible ET au niveau du bit.

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

Renvoyer la longueur du le plus long de 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.

Un sous-tableau est 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 1
• 1 6

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

<?php /**
 * @param Integer[] $nums
 * @return Integer
 */
function longestSubarray($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$nums1 = [1, 2, 3, 3, 2, 2];
$nums2 = [1, 2, 3, 4];

echo "Output for [1, 2, 3, 3, 2, 2]: " . longestSubarray($nums1) . "\n"; // Output: 2
echo "Output for [1, 2, 3, 4]: " . longestSubarray($nums2) . "\n";       // Output: 1
?>

Explication:

1. Étape 1 : Nous trouvons d'abord la valeur maximale dans le tableau à l'aide de la fonction max() intégrée de PHP.
2. É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.
3. É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.
4. É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.
5. 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 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!