LeetCode 1354. 多次求和构造目标数组（优先队列+逆向思考）
LeetCode 1354. 多次求和构造目标数组（优先队列+逆向思考）
Michael阿明
修改于 2020-10-21 20:07:32
修改于 2020-10-21 20:07:32
1. 题目
给你一个整数数组 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来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/construct-target-array-with-multiple-sums 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 和会越加越大，要先往最小的上面加（动态的过程）
- 逆向思考，给定的数组，数字全部push进优先队列
- 数组和往下减去最大的，应该等于1，若小于1，false
- 大于1，先pop原数，再push大于1的那个数进队列
在这里插入图片描述
class Solution {
public:
bool isPossible(vector<int>& target) {
int i, num;
long sum = 0, s;
priority_queue<int> q;//默认大顶堆
for(i = 0; i < target.size(); ++i)
{
sum += target[i];//总和
q.push(target[i]);
}
while(q.top() != 1)
{
s = sum-q.top();//剩余的和
num = q.top()-s;//栈顶-s，应该为1或者比1大的数
if(num < 1)//小于1则false
return false;
q.pop();//弹出栈顶
q.push(num);//把剩余的数再push进去
sum -= s;//和减少了s
}
return true;
}
};超时原因：queue的数据类型int溢出了，改为long
class Solution {
public:
bool isPossible(vector<int>& target) {
long sum = 0, s, i, num;
priority_queue<long> q;//默认大顶堆
for(i = 0; i < target.size(); ++i)
{
sum += target[i];//总和
q.push(target[i]);
}
while(!q.empty() && q.top() != 1)
{
s = sum-q.top();//剩余的和
num = q.top()-s;//栈顶-s，应该为1或者比1大的数
if(num < 1)//小于1则false
return false;
q.pop();//弹出栈顶
if(num != 1)//等于1就不用再放进去了，节省时间
q.push(num);
sum -= s;//和减少了s
}
return true;
}
};
在这里插入图片描述
leetcode该题的数据有点弱，上面解法在例子 [1000000000, 1]时超时。
比如对于 [5, 9, 31] 而言，31 - 14 = 17 还是最大数，不如干脆 31 - 14 * 2 = 9
更改如下，增加倍数scale
class Solution {
public:
bool isPossible(vector<int>& target) {
if(target.size() == 1)
return target[0] == 1;
long sum = 0, s, i, num, tp, scale;
priority_queue<long> q;//默认大顶堆
for(i = 0; i < target.size(); ++i)
{
sum += target[i];//总和
q.push(target[i]);
}
while(q.top() != 1)
{
tp = q.top();
q.pop();
s = sum-tp;//剩余的和
scale = max(1,int((tp-q.top())/s));//至少1倍
num = tp-scale*s;//栈顶-n*s，应该为1或者比1大的数
if(num < 1)//小于1则false
return false;
q.push(num);
sum -= scale*s;//和减少了n*s
}
return true;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-02-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录