Сложность: hard
Дан отсортированный массив целых чисел nums и целое число n. Добавьте/дополните элементы в массив таким образом, чтобы любое число в диапазоне [1, n] включительно могло быть сформировано как сумма некоторых элементов массива.
Верните минимальное количество дополнений, необходимых для этого.
Пример:
Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.
👨💻 Алгоритм:
1⃣Инициализация переменных:
Создайте переменную miss, представляющую наименьшее пропущенное число, которое еще не покрыто, и установите ее значение на 1. Создайте переменную patches для подсчета необходимых дополнений и переменную i для итерации по массиву nums.
2⃣Основной цикл:
Используйте цикл while, который будет выполняться до тех пор, пока miss не станет больше n.
Внутри цикла проверьте, покрывает ли текущий элемент nums[i] значение miss. Если да, добавьте nums[i] к miss и увеличьте i. Если нет, добавьте значение miss к самому себе (это означает добавление нового элемента в массив) и увеличьте счетчик patches.
3⃣Возврат результата:
После завершения цикла верните значение patches, которое представляет минимальное количество необходимых дополнений.
😎 Решение:
class Solution {
function minPatches($nums, $n) {
$patches = 0;
$i = 0;
$miss = 1;
while ($miss <= $n) {
if ($i < count($nums) && $nums[$i] <= $miss) {
$miss += $nums[$i++];
} else {
$miss += $miss;
$patches++;
}
}
return $patches;
}
}Ставь 👍 и забирай 📚 Базу знаний