X

LEETCODE 1354. Construct Target Array With Multiple Sums 解题思路分析

题目大意:

多次求和构造目标数组

给你一个整数数组 target 。一开始,你有一个数组 A ,它的所有元素均为 1 ,你可以执行以下操作:

  • 令 x 为你数组里所有元素的和
  • 选择满足 0 <= i < target.size 的任意下标 i ,并让 A 数组里下标为 i 处的值为 x 。
  • 你可以重复该过程任意次

如果能从 A 开始构造出目标数组 target ,请你返回 True ,否则返回 False 。

示例 1:

输入:target = [9,3,5]
输出:true
解释:从 [1, 1, 1] 开始
[1, 1, 1], 和为 3 ,选择下标 1
[1, 3, 1], 和为 5, 选择下标 2
[1, 3, 5], 和为 9, 选择下标 0
[9, 3, 5] 完成

示例 2:

输入:target = [1,1,1,2]
输出:false
解释:不可能从 [1,1,1,1] 出发构造目标数组。

示例 3:

输入:target = [8,5]
输出:true

提示:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1354

解题思路分析:

本题要求是否能够将一个全是1的数组,经过一系列变化变成给定数组target,变化的方式是将当前数组的数字和赋值到数组的任意一位置上。如果我们正向思考的话,每次需要考虑n种情况,n为数组长度,即尝试将数组的和赋值到数组的每一位,查看最终是否能够出现目标数组。但是如果反过来思考,我们利用target数组来反推全是1的数组就会相对简单许多,target数组中最大值max一定是最后一步变化得来的,这个max变化前的前身是max减去剩余数字的和。计算出max的前身之后,我们利用它的前身替换掉数组中的max值,再重复上述步骤。

在反推过程中,因为所有数字都是大于等于1的,所以当遇到最大值max小于剩余数字和的情况时,说明max的前身只能是负数,这不符合题意,可以返回false。如果最大值max等于剩余数字和,说明max的前身是0,同样不符合题意,除非max是1,即当数组中最大值等于1时,说明数组中所有数组都已经变成1,返回true。

我们举个例子,比如[5,8]。此时max是8,8的前身是8减去数组中其他数字和5,为3,将8的前身替换掉8,数组变为 [5,3],此时max是5,5的前身是5-3=2。数组变成 [2,3]。接下来同理,数组继续变化成 [2,1],最后变为 [1,1]。

以上即是本题的核心解题思路。不过提交代码后发现一个极端测试用例,[1,1000000000],此时max是1000000000,它的前身是999999999,仍然是最大值,这样我们需要进行999999999次减一计算才能将target数组变成 [1,1]。这时我们可以直接使用求余运算,余数即是max前身。另外如本例,当余数为0时(1000000000%1),说明max的前身与其他数字之和相同,上文我们说过,如果一个数字与其他数字和相同时,需要看max是否为1,如果是1,返回true,否则返回false。

解题时,我们可以使用PriorityQueue来保存数组中的数字,这样我们可以快速的取出数组中的最大值max。另外我们需要提前计算出数组中所有数字和sum。变化过程中将max以外数字和可以通过sum-max计算得出。将max变成其前身后,注意别忘了将sum减去max与前身的差值。

其实本题与我们之前讲过的一道题目非常类似:

LEETCODE 780. Reaching Points 解题思路分析

780. Reaching Points那道题比本题略微简单,它只是一个长度为2的数组,而本题数组长度不定,最大可能是5万。

实现代码:

public boolean isPossible(int[] target) {
    // 定义PriorityQueue,排序为由大到小
    PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
    // 数组元素和
    long sum=0;
    // 循环每一个元素
    for(int num: target){
        sum+=num; // 累加数组元素和
        q.offer(num); // 将当前元素添加到Queue
    }
    // 当数组元素和大于数组长度时循环
    // 当sum等于数组长度时,说明元素值都是1
    while(sum>target.length){
        int max=q.poll(); // 取出最大值
        long rest=sum-max; // 数组中剩余元素和
        // 如果最大值小于等于剩余元素和,返回false
        if(max<=rest) return false;
        // 计算max的前身
        int pre = (int)(max % rest);
        // 如果前身是0时(max与rest余数为0)。
        // 说明max的前身与剩余数字和相同。
        // 如果剩余数字和是为1,说明前身也是1,返回true
        if(pre==0) return rest==1;
        // 更新所有数字和
        sum-=(max-pre);
        // 将前身加入到Queue
        q.offer(pre);
    }
    return true;
}

本题解法执行时间为7ms。

Runtime: 7 ms, faster than 72.91% of Java online submissions for Construct Target Array With Multiple Sums.

Memory Usage: 48.2 MB, less than 100.00% of Java online submissions for Construct Target Array With Multiple Sums.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1354-construct-target-array-with-multiple-sums-解题思路分析/
Categories: leetcode
kwantong: