解決策:複数の和を持つ構成目標配列

これは一連のleetcode解決説明の一部です.あなたがこの解決が好きであるか、それが役に立つとわかるならば、このポストとmy solution post on Leetcode's forums .

Leetcode Problem #1354 (Hard): Construct Target Array With Multiple Sums

説明
にジャンプします.Solution Idea || コードJavaScript | Python | Java | C++ )

Given an array of integers target. From a starting array, A consisting of all 1's, you may perform the following procedure :

• let x be the sum of all elements currently in your array.
• choose index i, such that 0 <= i < target.size and set the value of A at index i to x.
• You may repeat this procedure as many times as needed.

Return True if it is possible to construct the target array from A otherwise return False.

例:

Example 1:
Input:	target = [9,3,5]
Output:	true
Explanation:	Start with [1, 1, 1] [1, 1, 1], sum = 3 choose index 1 [1, 3, 1], sum = 5 choose index 2 [1, 3, 5], sum = 9 choose index 0 [9, 3, 5] Done

Example 2:
Input:	target = [1,1,1,2]
Output:	false
Explanation:	Impossible to create target array from [1,1,1,1].

Example 3:
Input:	target = [8,5]
Output:	true

制約

• N == target.length
• 1 <= target.length <= 5 * 10^4
• 1 <= target[i] <= 10^9

考え
にジャンプします.Problem Description || コードJavaScript | Python | Java | C++ )
私たちがすぐに気付くことができる1つのこと:すべての正の数字で始まるので、意志の要素の合計は常にAのどんな一つの要素よりも大きいでしょう.したがって、我々はソリューションのプロセスを繰り返すと合計が上がるだけです.これは、私たちがちょうど正しい場所に与えられた数を置く1つの試みをするだけであることを意味します.
また、最後のステップは常に目標配列の最高値を解決することです.つまり、最後のステップの前の右の性質を再構築することができます.そこから、我々は最大の残りの値に対処し続ける必要があります.
値の降順で目標値を扱う必要があるので、値のインデックスを気にしないので、目標値を追跡するために、max priority queueやmax - heap構造を使用する必要がある理由になります.
一旦プライオリティキュー(PQ/HEAP)に挿入されたすべての目標値と計算された合計があれば、我々は順番に値に対処することができます.各ステップでは、最大値を削除し、その置換値を計算し、その置換をpqに再挿入する必要があります.繰り返しの開始時に、PQの最大値が1の場合、PQ内のすべての値が1 sであり、真を返すことを意味します.
一方、PQに1未満の数を挿入することに気づいたなら、私たちは失敗したことを知っています.
しかし、この時点で、我々はまだ微妙な結果を取得し、さらに最適化する必要があります.最大値を処理する状況を考えてください.いくつかのエッジケースでは、この値を完全に処理するために何千もの反復を取ることができます.そうすれば、すべての処理を1ステップでより簡単に行うことができます.
例えば、target =[ 3 , 5 , 33 ]を取る.通常、33を削除し、置換を25とし、25から17まで、17から9まで、最後に9から1まで計算します.たびに、我々はすべての残りの値の合計を削除している(3 + 5 = 8)現在の数字から.任意の有効なターゲット配列では、非常に最初に注意したように、max valueは残りの要素の合計より大きくなければなりません.
つまり、残りの合計(33)が現在の最大値(33)から削除されることができることを意味します.残りの部分だけがその合計の下に私たちをもたらすので.これは、すべてのステップを繰り返す必要がなく、私たちの置換値(33 % 8 = 1)をもたらすmod演算子と非常に簡単に達成することができます.
最近注目されているように、MAX値が実際の残りの値よりも少ない場合には、配列は有効ではなく、falseを返すことができます.また、NUMがmod演算子を適用した後に0になっていれば、sum = 1の場合にはfalseを返すべきです.代わりに、私たちは、サムのPQ整数に合計をプッシュすることができました.そして、それはすぐに端ケースのすべてで失敗を引き起こします.

実装
JavaScriptのMaxPriorityQueue () NPMは便利ですが、効率的ではありません.カスタムマックスヒープ実装は、より多くのパフォーマーです.両方のオプションが含まれます.
Pythonはデフォルトでは最小のヒープになりますので、ヒープから挿入されて削除されると、各要素の記号を変更することで最大ヒープをシミュレートできます.

JavaScriptコード
にジャンプします.Problem Description || Solution Idea )

w/maxpriorityqueue () :

var isPossible = function(target) {
    let pq = new MaxPriorityQueue({priority: x => x}), sum = 0
    for (let num of target) sum += num, pq.enqueue(num)
    while (pq.front().element !== 1) {
        let num = pq.dequeue().element
        sum -= num
        if (num <= sum || sum < 1) return false
        num %= sum, sum += num, pq.enqueue(num || sum)
    }
    return true
};

w/maxヒープ

var isPossible = function(target) {
    let heap = [,], sum = 0

    const heapify = val => {
        let i = heap.length, par = i >> 1, temp
        heap.push(val)
        while (heap[par] < heap[i]) {
            temp = heap[par], heap[par] = heap[i], heap[i] = temp
            i = par, par = i >> 1
        }
    }
    const extract = () => {
        if (heap.length === 1) return null
        let top = heap[1], left, right, temp,
            i = 1, child = heap[3] > heap[2] ? 3 : 2
        if (heap.length > 2) heap[1] = heap.pop()
        else heap.pop()
        while (heap[i] < heap[child]) {
            temp = heap[child], heap[child] = heap[i], heap[i] = temp
            i = child, left = i << 1, right = left + 1
            child = heap[right] > heap[left] ? right : left
        }
        return top
    }

    for (let num of target) sum += num, heapify(num)
    while (heap[1] !== 1) {
        let num = extract()
        sum -= num
        if (num <= sum || sum < 1) return false
        num %= sum, sum += num, heapify(num || sum)
    }
    return true
};

Pythonコード:
にジャンプします.Problem Description || Solution Idea )

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        heap = [-num for num in target]
        total = sum(target)
        heapify(heap)
        while heap[0] != -1:
            num = -heappop(heap)
            total -= num
            if num <= total or total < 1: return False
            num %= total
            total += num
            heappush(heap, -num or -total)
        return True

Javaコード:
にジャンプします.Problem Description || Solution Idea )

class Solution {
    public boolean isPossible(int[] target) {
        Queue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);
        int sum = 0;
        for (int num : target) {
            sum += num;
            pq.add(num);
        }
        while (pq.peek() != 1) {
            int num = pq.poll();
            sum -= num;
            if (num <= sum || sum < 1) return false;
            num %= sum;
            sum += num;
            pq.add(num > 0 ? num : sum);
        }
        return true;
    }
}

C++コード:
にジャンプします.Problem Description || Solution Idea )

class Solution {
public:
    bool isPossible(vector<int>& target) {
        priority_queue<int> pq;
        unsigned int sum = 0;
        for (int num : target)
            sum += num, pq.push(num);
        while (pq.top() != 1) {
            int num = pq.top();
            pq.pop();
            sum -= num;
            if (num <= sum || sum < 1) return false;
            num %= sum, sum += num, pq.push(num ? num : sum);
        }
        return true;
    }
};