做淘宝客的网站需要备案吗,昆明的互联网公司有哪些,手机软件分类,江苏雷威建设工程有限公司网站1. 题目
给你一个整数数组 target 。一开始#xff0c;你有一个数组 A #xff0c;它的所有元素均为 1 #xff0c;你可以执行以下操作#xff1a;
令 x 为你数组里所有元素的和选择满足 0 i target.size 的任意下标 i #xff0c;并让 A 数组里下标为 i 处的…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若小于1false大于1先pop原数再push大于1的那个数进队列 超时例子
class Solution {
public:bool isPossible(vectorint target) {int i, num;long sum 0, s;priority_queueint 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则falsereturn false;q.pop();//弹出栈顶q.push(num);//把剩余的数再push进去sum - s;//和减少了s}return true;}
};超时原因queue的数据类型int溢出了改为long
class Solution {
public:bool isPossible(vectorint target) {long sum 0, s, i, num;priority_queuelong 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则falsereturn 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(vectorint target) {if(target.size() 1)return target[0] 1;long sum 0, s, i, num, tp, scale;priority_queuelong 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则falsereturn false;q.push(num);sum - scale*s;//和减少了n*s}return true;}
};
