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
xbe the sum of all elements currently in your array. - choose index
i, such that0 <= i < nand set the value ofarrat indexitox. - 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.
Example 1:
Input: target = [9,3,5]
Output: true
Explanation: Start with arr = [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.length1 <= n <= 5 * 1041 <= target[i] <= 109
这道题说是给了一个目标数组 target，让我们从一个长度相同，但是全是1的数组开始变动，变化的规则是可以将任意位置上的数字变成当前数组的数字之和，并说了可以进行任意次数的变化，问最终是否能变化成给定的数组。参见题目中给定的例子不难理解题意，比如例子1中，就通过了三次变换，可以得到目标数组。而例子2，是没法得到的，因为初始数组的和为4，而目标数组中有个2，是小于4的。再比如例子3，题目中没有给变化过程，我们这里自己推导一下吧：
[1, 1] -> [1, 2] -> [3, 2] -> [3, 5] -> [8, 5]
博主最先看到这题的思路就是暴力搜索，从初始数组开始去尝试每一种可能，这种方法虽然可行，但是运算效率十分的低下，当数组的长度很大的时候，会无法通过 OJ，必须要想出更加优化的解法。由于这道题只是问能否组成目标数组，并不要求组成目标数组的不同方法，所以比较好的思路是倒着推，即从目标数组开始，往回推，看是否能得到初始数组。这种方法的优势在于，我们可以优先处理最大的数字，将其尽可能的最快减小到1。就拿题目中的例子1来举例吧，最大的数字是9，这个9怎么来的呢？在上一轮它是所有数字之和，这样话就可以通过减去其它所有数字得到替换之前的数字，即 9 - (5 + 3) = 1，说明是由 [1, 3, 5] 变化来的。接下来处理数字5，同样的方法求替换之前的数字 5 - (3 + 1) = 1，说明是由 [1, 3, 1] 变化来的。接下来处理数字3，同样的方法求替换之前的数字 3 - (1 + 1) = 1，说明是由 [1, 1, 1] 变化来的，这样就反推得到了初始数组。
这个是可以反推回去的情况，接下来想一下不能反推回去的情况，比如例子2中最大的数字是2，而其余数字之和是3，说明这个2并不是由数组之和变化来的，所以不能反推回去。这就是能反推的一个限定条件，即数组中最大的数字要大于其余数字之和，等于都不行，等于的话说明替换前的数字是0，是不对的，同理，最大数字是其余数字之和的整数倍也是不行的，因为最终还是会减到0。另一个限制条件就是其余数字之和也不能是0，因为初始数组每个数字都是1。说完了限制条件，再来说说到达什么条件就知道可以反推到初始数组，首先就是当数组中的最大数字为1的时候，因为此时在反推回去的过程中，上述的限制条件通过了之后，最大数字仍是1，说明所有数字都是1了，就满足条件了。其实还有个判断条件，即当其余数字之和为1的时候就可以返回 true，这个放到后面来解释。
先来解释一下代码，为了更好的取出最大数，这里用个优先队列，将目标数组所有数字放进去，就可以完成自动排序，同时计算出目标数组之和 sum。然后开始 while 循环，首先取出队首元素t，然后计算出其余数字之和，用数组数组总和 sum 减去t。此时需要判断下是否可以返回 true，即t是否等于1，或者其余数字之和 sum 是否等于1（后面讲解）。不能直接返回 true 的话，就来检查上面解释过的限制条件，即若t小于 sum，或者 sum 等于0，或者t是 sum 的整数倍时，都要返回 false。此时t要对 sum 取余，为啥不是相减，而是取余呢，这其实是一种优化，若数组中最大数字远大于其他数字之和，则减过一次之后还有可能大于其余数字之和，这时为了避免大量的重复计算，则可以直接用取余来跳过重复的步骤。
好，现在再来解释一下前面为啥判断 sum 为1的时候，就可以返回 true。因为这种情况只有一种可能，就是数组中只有两个数字，当前数字是2，而另一个数字是1，这种情况下之所以没法通过下一轮遍历中判断最大数字是1来返回 true，是由于任何数字对1取余都会变成0，于是只能通过判断 sum 的值来返回 true 了，这也是用取余操作比较 tricky 的地方。得到新的 t 之后，要将其加到 sum 中，此时的 sum 就是当前数组所有数字之和了，就可以在下一轮循环中，再减去最大数字，从而又可以得到其它数字之和的那个 sum 了，参见代码如下：
class Solution {
public:
bool isPossible(vector<int>& target) {
long sum = 0;
priority_queue<int> pq;
for (int num : target) {
pq.push(num);
sum += num;
}
while (true) {
int t = pq.top(); pq.pop();
sum -= t;
if (t == 1 || sum == 1) return true;
if (t < sum || sum == 0 || t % sum == 0) return false;
t %= sum;
sum += t;
pq.push(t);
}
return true;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1354
类似题目：
Minimum Amount of Time to Fill Cups
参考资料：
https://leetcode.com/problems/construct-target-array-with-multiple-sums/