1354. Construct Target Array With Multiple Sums - kumaeki/LeetCode GitHub Wiki

1354. Construct Target Array With Multiple Sums

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

Constraints:

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

解法1

从结果反推, 如果可以得到每个值都为1的数组, 就OK了.

但是很可惜, 超时了.因为要一步一步的计算.

class Solution {
    public boolean isPossible(int[] target) {
        
        int len = target.length;
        if(len == 1 && target[0] > 1)
            return false;
        
        // 数组的和
        int sum = 0;
        
        // 用que来存储位置和值信息, 每次取出最大的值
        PriorityQueue<int[]> que = new PriorityQueue<int[]>((x, y) -> y[1] - x[1]);
        for(int i = 0; i < len; i++){
            sum += target[i];
            que.offer(new int[]{i, target[i]});
        }
        
        while(!que.isEmpty()){
            // 取出最大值
            int[] cur = que.poll();
            int index = cur[0], val = cur[1];
            // 如果值等于1, 那么所有的值都是1, 返回true
            if(val == 1)
                return true;
            
            // 将val退回前一次的值
            val = val - (sum - val);
            sum -= (cur[1] - val); 
            // 如果得到的值小于1, 那么说明无法得到该值, 返回false
            if(val < 1)
                return false;
            
            que.offer(new int[]{index, val});
        }
        return true;        
    }
}

解法2

基本思路不变, 但是相对于解法1有几个改进点.

  • 不需要在PriorityQueue中保存位置信息.
  • 正向运算中,连续多次将计算结果保存在同一位置时, 可以用取余运算来代替单纯的减运算来减少运算次数
  • 虽然根据题目中的条件, target[i]都是在int范围内, 但是第一次计算的时候sum的和是有可能超出int范围的, 为了第一次计算sum的时候避免overflow,用long.
class Solution {
    public boolean isPossible(int[] target) {
        
        // 数组的和
        long sum = 0;
        
        // 用que来存储值, 每次取出最大
        PriorityQueue<Integer> que = new PriorityQueue<Integer>((x, y) ->  y - x);
        for(int t : target){
            sum += t;
            que.offer(t);
        }
        
        while(true){
            // 取出最大值
            int cur = que.poll();
            
            // 得到除去当前最大值以外的值的和
            sum -= cur;
            
            // 如果当前值等于1, 或者其他值的和等于1(即只有两个数值,而其中一个是1), 那么返回true
            if(cur == 1 || sum == 1)
                return true;

            // 如果当前值小于 其他值的和, 或者其他值的和为0, 或者 余运算的结果为0 那么说明无法得到该值, 返回false
            if(cur < sum || sum == 0 || cur % sum == 0)
                return false;

            // 这里可以用减, 但是用取余更快
            // 如果正向计算的时候, 在当前位置连续多次储存结果, 那么取余可以直接反向得到对应的初始值
            // 比如 [1,1,1,1] 连续3次在位置0储存结果时,会得到[4,1,1,1],[7,1,1,1],[10,1,1,1]
            //      即 10%3 可以直接得到初始值
            cur %= sum;
            sum += cur;
            
            que.offer(cur);
        }
    }
}
⚠️ **GitHub.com Fallback** ⚠️