首页 > 代码库 > LeetCode OJ-- 二战 Combinations
LeetCode OJ-- 二战 Combinations
在1 - 10 中，求出 7 个数的排列组合。
出现了超时，而超时的原因是有好多重复情况，复杂度上来说，和答案的复杂度是一样的，但是答案中重复了太多了，体会下。
超时1：
class Solution {public: vector<vector<int> > combine(int n, int k) { vector<vector<int> > ans; if(n < k || n <= 0 || k <= 0) return ans; vector<int> ansPiece; set<int> checkExist; for(int i = 1; i <= n; i++) { ansPiece.clear(); ansPiece.push_back(i); checkExist.clear(); checkExist.insert(i); if(k > 1) combine(ans,ansPiece,k,n,checkExist); } return ans; } void combine(vector<vector<int> > &ans, vector<int> &ansPiece, int &k, int &n, set<int> &checkExist) { if(ansPiece.size() == k) { vector<int> temp = ansPiece; ans.push_back(temp); return; } for(int i = 1; i <=n; i++) { if(checkExist.find(i) == checkExist.end()) { ansPiece.push_back(i); checkExist.insert(i); combine(ans,ansPiece,k,n,checkExist); ansPiece.pop_back(); checkExist.erase(i); } } }};
超时2：
class Solution {public: vector<vector<int> > combine(int n, int k) { vector<vector<int> > ans; if(n < k || n <= 0 || k <= 0) return ans; vector<int> ansPiece; set<int> checkExist; //记录还没有选的元素 for(int i = 1; i <= n; i++) { checkExist.insert(i); } combine(ans,ansPiece,k,checkExist); return ans; } void combine(vector<vector<int> > &ans, vector<int> &ansPiece, int &k, set<int> &checkExist) { if(ansPiece.size() == k) { vector<int> temp = ansPiece; ans.push_back(temp); return; } set<int>::iterator itr; for(itr = checkExist.begin(); itr != checkExist.end(); itr++) { ansPiece.push_back(*itr); set<int> check2 = checkExist; check2.erase(*itr); combine(ans,ansPiece,k,check2); ansPiece.pop_back(); } }};
正确的：（控制了顺序）
class Solution {public: vector<vector<int> > combine(int n, int k) { vector<vector<int> > ans; if(n < k || n <= 0 || k <= 0) return ans; vector<int> ansPiece; int start = 1; combine(ans,ansPiece, k,n, start); return ans; } void combine(vector<vector<int> > &ans, vector<int> &ansPiece, int &k, int &n, int start) { if(ansPiece.size() == k) { vector<int> temp = ansPiece; ans.push_back(temp); return; } for(int i = start; i <= n; i++) { if(n - i + 1 < k - ansPiece.size()) return; ansPiece.push_back(i); combine(ans,ansPiece,k,n,i+1); ansPiece.pop_back(); } }};
LeetCode OJ-- 二战 Combinations
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。