Leetcode-330. Patching Array

問題の説明:

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

は、秩序化された正数配列numsと正数nを与えます.質問、numsの数を自由に選択して、1～nのいずれかの数を追加したい場合は、まだいくつかの数が欠けています.

Example 1

nums = [1, 3], n = 6 Return 1. 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.

Example 2

nums = [1, 5, 10], n = 20 Return 2. The two patches can be [2, 4].

Example 3

nums = [1, 2, 2], n = 5 Return 0.

leetcodeリンク

構想分析

まずこの問題は最小値を求めることであり、最適な問題でもある.一般的に,最適問題は動的計画や貪欲アルゴリズムで解決できる.この問題は貪欲なアルゴリズムを使う.

は、現在達成可能な最大範囲、すなわち配列(0~i-1)位置の要素で(1~range)範囲内のすべての数を加算できる変数rangeを定義し、rangeはその範囲を表す最大右境界である.したがって初期化rangeは0であり,このとき配列のいずれの数も計算されていない.

大構想は左から右へ配列を遍歴し、rangeを更新し続け、range>nまで遍歴を終了する.では、rangeをどのように更新(反復)し、配列にパッチを適用しますか(数を追加します).

(0~i-1)位置を遍歴し終えると、配列(0~i-1)位置の要素で(1~range)範囲内のすべての数を加算することができ、rangeはその範囲の最大右境界を表す.では、cur[i] > range+1でnums[0~i]でrange+1を加算できないとブレークポイントが発生し、その場合はrange+1のパッチ、すなわち配列にrange+1という数を追加して範囲の連続性を保証しなければならない.このときrangeはrange +=range + 1に更新され、cur[i]とrange+1のサイズのチェックが継続される.cur[i] <= range+1であれば、このときnums[0~i]で(1~cur[i]+range)内のすべての数を加算することができ、パッチを適用する必要がなく、rangeはcur[i]+rangeに更新される.右へ遍歴を続けます.

は、例えば、既存の配列[1,2,3,9]のrange初期値が0であり、1の場合、rangeが1に更新される.右へ遍歴し,2に対してrangeは3に更新され,[1,2]で1,2,3を加算できる.3については、3と(1~range)を加算すると(4~range+3)すなわち(4~6)を加算することができ、以前の範囲は(1~3)であったが、この2つの区間を無間隔で併合することができ、説明用[1,2,3]を加算することができ(1~6)、このときrangeが6に更新される.ただし、9については、9と(1~range)を加算して(10~15)、元の範囲(1~6)と間隔があり、合併できず、7,8,9の3つの値は加算できず、現在パッチを適用しなければならないことを示している.

では、パッチを適用する必要があるかどうか、パッチを適用する方法をどのように判断しますか?元の範囲は(1~range)であり、cur[i]に加算されて(1+cur[i]、range+cur[i])、cur[i]は他の数に加算されず、すなわちこの値のみが選択されるため、区間が拡張される(cur[i],range+cur[i]).2つの区間が無間隔で1つの区間に統合できることを保証するために、cur[i] <= range+1を要求しなければならない.cur[i] > range+1の場合、パッチを適用する必要があります.区間が連続していることを保証します.補充された値は最初のブレークポイント位置です.range+1で、range+1より小さい数をパッチとして使用できますが、range+1はブレークポイントをパッチすることができます.また、パッチを適用した後、rangeは最大の値に更新され、パッチの数を最小限に抑えることができます.これが欲張りアルゴリズムの応用点であり,毎回の選択が最適である.

配列はすべてループが終了し、nが追加されていない可能性があることに注意してください.それでは、range+1のパッチを毎回適用し、range>n

までrangeを繰り返し更新します.

経験と教訓.

一般的に、最適な問題は、動的計画または貪欲なアルゴリズムで解決することができる.

この問題rangeの概念と用法は別の問題の進級問題と類似しており、リンクを添付している:正数配列の最小不可構成と問題

rangeの使い方を深く理解する

rangeは配列中のすべての数の累積和である可能性があり、オーバーフローを防止するためにlong

とする.
コード実装

方法1

public static int minPatches(int[] nums, int n) {
        int patchesNum = 0;
        long range = 0;
        //    
        for (int i = 0; i < nums.length; i++) {
            //range+1   ：   range + 1   ，      ，        
            while (nums[i] > range + 1) {
                patchesNum++;
                range += range + 1;
                //     n
                if (range >= n) {
                    return patchesNum;
                }
            }
            //     ，    range,      n
            range += nums[i];
            if (range >= n) {
                return patchesNum;
            }
        }
        //           n,
        //       range + 1   ，      ，  range，  range >= n
        while (range < n) {
            patchesNum++;
            range += range+1;
        }
        return patchesNum;
    }

方法二

public static int minPatches(int[] nums, int n) {
        int patchesNum = 0;
        long range = 0;
        int index = 0;
        while(range < n) {
            //       ，  nums[index] <= range+1：     ，    range
            if (index < nums.length && nums[index] <= range+1) {
                range += nums[index];
                index++;
            }else {//   nums[index] > range+1,  range+1   ;                n
                //      range + 1   ，      ，  range
                patchesNum++;
                range += range + 1;
            }
        }
        return patchesNum;
    }