. Tableau de correctifs

330. Tableau de correctifs

Dur

Étant donné un tableau d'entiers triés nums et un entier n, ajoutez/corrigez des éléments au tableau de telle sorte que tout nombre compris dans la plage [1, n] inclus puisse être formé par la somme de certains éléments du tableau.

Renvoyer le nombre minimum de correctifs requis.

Exemple 1 :

• Entrée : nums = [1,3], n = 6
• Sortie : 1
• Explication :
  • Les combinaisons de nombres sont [1], [3], [1,3], qui forment des sommes possibles de : 1, 3, 4.
  • Maintenant, si nous ajoutons/corrigeons 2 aux nombres, les combinaisons sont : [1], [2], [3], [1,3], [2,3], [1,2,3].
  • Les sommes possibles sont 1, 2, 3, 4, 5, 6, ce qui couvre désormais la plage [1, 6].
  • Nous n’avons donc besoin que d’un seul patch.

Exemple 2 :

• Entrée : nums = [1,5,10], n = 20
• Sortie : 2
• Explication : Les deux patchs peuvent être [2, 4].

Exemple 3 :

• Entrée : nums = [1,2,2], n = 5
• Sortie : 0

Contraintes :

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10⁴
• nums est trié par ordre croissant.
• 1 <= n <= 2³¹ - 1

Solution :

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $n
     * @return Integer
     */
    function minPatches($nums, $n) {
        $ans = 0;
        $i = 0;
        $miss = 1;
         while ($miss <= $n) {
            if ($i < count($nums) && $nums[$i] <= $miss) {
                $miss += $nums[$i++];
            } else {
                $miss += $miss;
                ++$ans;
            }
        }
        return $ans;
    }
}

Liens de contact

• 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!