Opération de soustraction première

2601。素数減算演算

難易度: 中

トピック: 配列、数学、二分探索、貪欲、整数論

長さ n の 0 インデックス付き 整数配列 nums が与えられます。

次の操作は何度でも実行できます:

• これまでに選択したことのないインデックス i を選択し、厳密に nums[i] より小さい素数 p を選択し、nums[i] から p を減算します。

上記の操作を使用して nums を厳密に増加する配列にできる場合は true を返し、それ以外の場合は falseを返します。

厳密に増加する配列は、各要素がその前の要素より厳密に大きい配列です。

例 1:

• 入力: 数値 = [4,9,6,10]
• 出力: true
• 説明: 最初の操作: i = 0 および p = 3 を選択し、nums[0] から 3 を引くと、nums は [1,9,6,10] になります。
  • 2 番目の演算: i = 1、p = 7 では、nums[1] から 7 を減算し、nums は [1,2,6,10] と等しくなります。
  • 2 番目の操作の後、nums は厳密に昇順にソートされるため、答えは true になります。

例 2:

• 入力: 数値 = [6,8,11,12]
• 出力: true
• 説明: 当初、nums は厳密に昇順にソートされるため、操作を行う必要はありません。

例 3:

• 入力: 数値 = [5,8,3]
• 出力: false
• 説明: 数値を厳密に昇順にソートする操作を実行する方法がないことが証明できるため、答えは false です。

制約:

• 1
• 1
• nums.length == n

ヒント:

1. nums[i] から減算する素数がたくさんあるかどうかを考えてみましょう。どの素数がより最適ですか?
2. nums[i] から減算するのに最も最適な素数は、nums[i] を可能な限り小さくし、nums[i-1] より大きくする素数です。

解決策:

アルゴリズムを分解し、PHP の構文と機能に適応させる必要があります。この解決策には主に次の手順が含まれます:

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

<?php
class Solution {

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

    /**
     * Helper function to generate all primes up to n using Sieve of Eratosthenes
     *
     * @param $n
     * @return array
     */
    private function sieveEratosthenes($n) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Helper function to find the largest prime less than a given limit using binary search
     *
     * @param $primes
     * @param $limit
     * @return mixed|null
     */
    private function findLargestPrimeLessThan($primes, $limit) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage:
$solution = new Solution();
echo $solution->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:

1. 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.

2. 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.

3. 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!