。修補陣列

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中文網其他相關文章！