Redian新闻
>
leetcode combinationsum2 超时
avatar
leetcode combinationsum2 超时# JobHunting - 待字闺中
s*n
1
不知道什么地方可以改进?请有时间的朋友指点一下
combinationsum1用类似的办法就没超时
class Solution {
public:
vector > combinationSum2(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort (num.begin(), num.end());
vector > results(0);
addOneBit(num, target, results);
return results;
}

void addOneBit (vector &num, int target, vector > &
results){
if (target == 0){
vector empty;
results.push_back(empty);
return;
}else if (num.size() <= 0){
return;
}
/*if (accumulate(num.begin(), num.end(), 0) < target){
return;
}*/
int ele = num.back();
num.pop_back();
int counter = 1;
while (num.back() == ele){//eliminate dupes
num.pop_back();
counter++;
}
vector > temp(0);
for (int i=0; i<=counter; ++i){
addOneBit (num, target-i*ele, results);
vector tail(i,ele);
for (int j=0; jresults[j].insert(results[j].end(), tail.begin(), tail.end()
);
}
temp.insert(temp.end(), results.begin(), results.end());
results.clear();
}
results = temp;
for (int i=1; i<=counter; ++i){
num.push_back(ele);
}
return;
}
};
avatar
s*n
2
self fixed, add
{if target<0 return}

【在 s*****n 的大作中提到】
: 不知道什么地方可以改进?请有时间的朋友指点一下
: combinationsum1用类似的办法就没超时
: class Solution {
: public:
: vector > combinationSum2(vector &num, int target) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: sort (num.begin(), num.end());
: vector > results(0);
: addOneBit(num, target, results);

avatar
l*b
3
呵呵呵。。。。

【在 s*****n 的大作中提到】
: self fixed, add
: {if target<0 return}

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。