. Patch-Array

330. Patch-Array

Schwer

Angenommen ein sortiertes Ganzzahl-Array nums und eine Ganzzahl n, fügen Sie dem Array Elemente hinzu bzw. fügen Sie Elemente hinzu, sodass jede Zahl im Bereich einschließlich [1, n] durch die Summe einiger Elemente im Array gebildet werden kann.

Geben Sie die erforderliche Mindestanzahl an Patches zurück.

Beispiel 1:

• Eingabe: nums = [1,3], n = 6
• Ausgabe: 1
• Erklärung:
  • Zahlenkombinationen sind [1], [3], [1,3], die mögliche Summen von 1, 3, 4 bilden.
  • Wenn wir nun 2 zu Zahlen hinzufügen/patchen, sind die Kombinationen: [1], [2], [3], [1,3], [2,3], [1,2,3].
  • Mögliche Summen sind 1, 2, 3, 4, 5, 6, was nun den Bereich [1, 6] abdeckt.
  • Wir brauchen also nur 1 Patch.

Beispiel 2:

• Eingabe: nums = [1,5,10], n = 20
• Ausgabe: 2
• Erklärung:Die beiden Patches können [2, 4] sein.

Beispiel 3:

• Eingabe: nums = [1,2,2], n = 5
• Ausgabe: 0

Einschränkungen:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10⁴
• Die Nummern werden in aufsteigender Reihenfolge sortiert.
• 1 <= n <= 2³¹ - 1

Lösung:

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;
    }
}

Kontaktlinks

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt von. Patch-Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!