1354. Construct Target Array With Multiple Sums

Question

You are given an array target of n integers. From a starting array arr consisting of n 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 < n and set the value of arr 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 arr, otherwise, return false.

Solution 1

递归，每次寻找到数组中最大的数字的下标maxIndex，并对整个数组加和。
当数组中出现小于1的数时，不成立，返回false。
当数组加和等于数组长度时，返回true。

记录剩余的数字others，如果没有剩余数字，则返回false。
将target[maxIndex]减去others，因此每次翻倍，快速逼近。
当小于0时，则还原到上一个target[maxIndex]。

递归更改后的数组。

Code

class Solution {
    public boolean isPossible(int[] target) {
        int maxIndex = 0, sum = 0;
        for(int i = 0; i < target.length; i++){
            if(target[i] <= 0) return false;    //数组中出现小于1的数，则不成立，返回false
            if(target[maxIndex] < target[i]) maxIndex = i;
            sum += target[i];
        }
        if(sum == target.length) return true;   //加和等于长度，则数组内全部为1，返回true
        int others = sum - target[maxIndex];
        if(others == 0) return false;   //没有其他值时返回false
        target[maxIndex] -= others;
        int n = 1;
        while(target[maxIndex] > others){
            target[maxIndex] -= n * others;
            if(target[maxIndex] <= 0){
                target[maxIndex] += n * others;
                break;
            }
            n*=2;   //因子每次翻倍，快速逼近
        }
        return isPossible(target);
    }
}

Solution 2

优先级队列， 大根堆。
每次挤出队列里最大的数字max。

如果max的值为1，则返回true。

计算加和和新的值，并更新sum。
如果最大的数字max小于0，或者剩余的sum小于0，则返回false。

当max仍然大于剩下的数字时，继续做减法。采用因数翻倍，快速接近目标值。
如果max小于0，则恢复到上一个值，并添加到优先级队列中。

Code

class Solution {
    public boolean isPossible(int[] target) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int sum = 0;
        for(int num : target){
            pq.offer(num);
            sum+=num;
        }
        while(true){
            int max = pq.poll();
            if(max == 1) return true;

            sum -= max;
            max = max - sum;
            if(sum <= 0 || max <= 0) return false;
            
            int n = 1;
            while(max > sum){
                max -= n * sum;
                if(max <= 0){
                    max += n * sum;
                    break;
                }
                n*=2;
            }
            sum += max;
            pq.offer(max);
        }
    }
}