。配列のパッチ適用

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:

• 入力: 数値 = [1,5,10]、n = 20
• 出力: 2
• 説明: 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;
    }
}

連絡先リンク

• LinkedIn
• GitHub

以上が。配列のパッチ適用の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。