Opération de soustraction première

2601. Opération de soustraction première

Difficulté :Moyen

Sujets :Tableau, mathématiques, recherche binaire, gourmand, théorie des nombres

Vous recevez un tableau de nombres entiers indexé à 0 de longueur n.

Vous pouvez effectuer l'opération suivante autant de fois que vous le souhaitez :

• Choisissez un indice i que vous n'avez pas choisi auparavant, et choisissez un premier p strictement inférieur à nums[i], puis soustrayez p de nums[i].

Renvoyer true si vous pouvez faire de nums un tableau strictement croissant en utilisant l'opération ci-dessus et false sinon.

Un tableau strictement croissant est un tableau dont chaque élément est strictement supérieur à son élément précédent.

Exemple 1 :

• Entrée : nums = [4,9,6,10]
• Sortie : vrai
• Explication : Dans la première opération : choisissez i = 0 et p = 3, puis soustrayez 3 de nums[0], de sorte que nums devienne [1,9,6,10].
  • Dans la deuxième opération : i = 1, p = 7, soustrayez 7 de nums[1], donc nums devient égal à [1,2,6,10].
  • Après la deuxième opération, les nombres sont triés par ordre strictement croissant, donc la réponse est vraie.

Exemple 2 :

• Entrée : nums = [6,8,11,12]
• Sortie : vrai
• Explication : Initialement, les nombres sont triés par ordre strictement croissant, nous n'avons donc pas besoin d'effectuer d'opérations.

Exemple 3 :

• Entrée : nums = [5,8,3]
• Sortie : faux
• Explication : Il peut être prouvé qu'il n'existe aucun moyen d'effectuer des opérations pour trier les nombres dans un ordre strictement croissant, donc la réponse est fausse.

Contraintes :

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• nums.length == n

Indice :

1. Pensez si nous avons de nombreux nombres premiers à soustraire des nombres[i]. Quel nombre premier est le plus optimal ?
2. Le nombre premier le plus optimal à soustraire de nums[i] est celui qui rend nums[i] le plus petit possible et supérieur à nums[i-1].

Solution :

Nous devons décomposer l'algorithme et l'adapter à la syntaxe et aux fonctionnalités PHP. La solution passe principalement par les étapes suivantes :

1. Génération des nombres premiers (tamis d'Ératosthène) : Générez une liste de tous les nombres premiers jusqu'à la valeur maximale possible en nombres (1000).
2. Opération de soustraction des nombres premiers : Pour chaque nombre en nombres, vérifiez si nous pouvons soustraire un nombre premier pour rendre le tableau strictement croissant.
3. Recherche binaire de Prime : Utilisez une recherche binaire pour trouver le plus grand nombre premier inférieur au nombre actuel qui maintiendrait toujours la séquence strictement croissante.

Implémentons cette solution en PHP : 2601. Opération de soustraction première

primeSubOperation([4, 9, 6, 10]) ? 'true' : 'false';  // Output: true
echo $solution->primeSubOperation([6, 8, 11, 12]) ? 'true' : 'false'; // Output: true
echo $solution->primeSubOperation([5, 8, 3]) ? 'true' : 'false';      // Output: false
?>





  
  
  Explication:




primeSubOperation : parcourt chaque élément en nombres et vérifie si nous pouvons rendre chaque élément supérieur au précédent en soustrayant un nombre premier approprié.


Nous utilisons $this->findLargestPrimeLessThan pour trouver le plus grand nombre premier inférieur à num - prevNum.
Si un tel nombre premier existe, nous le soustrayons du nombre actuel.
Si après soustraction du nombre premier, le num actuel n'est pas supérieur au prevNum, nous renvoyons false.
Sinon, nous mettons à jour prevNum avec le numéro actuel.


sieveEratosthène : génère tous les nombres premiers jusqu'à 1000 à l'aide du tamis d'Eratosthène et les renvoie sous forme de tableau.
findLargestPrimeLessThan : utilise la recherche binaire pour trouver le plus grand nombre premier inférieur à une limite donnée, garantissant ainsi que nous trouvons le nombre premier optimal pour la soustraction.



  
  
  Analyse de complexité




Complexité temporelle : O(n . √m), où n est la longueur des nombres et m est la valeur maximale d'un élément en chiffres (ici m = 1000).

Complexité spatiale : O(m), utilisé pour stocker la liste des nombres premiers jusqu'à 1000.


Cette solution renverra vrai ou faux selon qu'il est possible de rendre les nombres strictement croissants en effectuant les opérations de soustraction de nombres premiers décrites.

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!