。修补阵列

330。修补数组

难

给定一个排序的整数数组 nums 和一个整数 n，向数组添加/修补元素，使得 [1, n] 范围内的任何数字都可以由数组中某些元素的总和形成。

返回所需的最小补丁数。

示例1：

• 输入： nums = [1,3], n = 6
• 输出： 1
• 说明：
  • 数字的组合是 [1]、[3]、[1,3]，它们形成可能的和：1、3、4。
  • 现在，如果我们向 nums 添加/修补 2，则组合为：[1]、[2]、[3]、[1,3]、[2,3]、[1,2,3]。
  • 可能的和为 1, 2, 3, 4, 5, 6，现在涵盖范围 [1, 6]。
  • 所以我们只需要 1 个补丁。

示例2：

• 输入： nums = [1,5,10], n = 20
• 输出： 2
• 说明：这两个补丁可以是[2, 4]。

示例 3：

• 输入： nums = [1,2,2], n = 5
• 输出： 0

约束：

• 1
• 1 4
• nums 按升序排序。
• 1 31 - 1

解决方案：

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

联系链接

• 领英
• GitHub

以上是。修补阵列的详细内容。更多信息请关注PHP中文网其他相关文章！