首页 > 代码库 > leetcode permutation/combination
leetcode permutation/combination
Next Permutation
将整个排列看成是一个数,按数大小排列,求下一个排列
// ①从右到左找到第一个非递增的位置 pivot // ②从右到左找到第一个大于 *pivot 的位置 change // ③交换*pivot与*change // ④将pivot右边的元素全部逆置 // @algorithm http://?sherlei.blogspot.com/2012/12/leetcode-next-permutation.html // @author soulmachine http://github.com/soulmachine/leetcode void nextPermutation(vector<int> A) { return next_permutation(A.begin(), A.end()); } template<typename Itr> bool next_permutation(Itr first, Itr last) { const auto rfirst = reverse_iterator<Itr>(last); const auto rlast = reverse_iterator<Itr>(first); auto pivot = next(rfirst); while (pivot != rlast && *pivot >= *prev(pivot)) { pivot = next(pivot); } if (pivot == rlast) { reverse(rfirst, rlast); return false; } auto change = find_if(rfirst, pivot, bind1st(less<int>, *pivot)); swap(*pivot, *change); reverse(rfirst, pivot); return true; }
Permutations/ Permutations II
// 求全排列 // @author soulmachine http://github.com/soulmachine/leetcode vector<vector<> > permute(vector<int> &A) { vector<vector<int> > v; sort(A.begin(), A.end()); do { v.push_back(A); }while (next_permutation(A.begin(), A.end())); return v; }
Combinations
// 求全组合Cnk,深搜, O(n!) // @author soulmachine http://github.com/soulmachine/leetcode vector<vector<int> > combine(int n, int k) { vector<vector<int> > v; vector<int> t; dfs(n, k, 1, 0, t, v); return v; } void dfs(int n, int k, int start, int curr, vector<int> &t, vector<vector<int> > &v) { if (curr == k) v.push_back(t); for (int i = start; i <= n; ++i) { // 确定一个找下一个 t.push_back(t); dfs(n, k, i + 1, curr + 1, t, v); // 深度 t.pop_back(); // 返回该层 } }
leetcode permutation/combination
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。