首页 > 学院 > 开发设计 > 正文

40. Combination Sum II / 46. Permutations / 47. Permutations II

2019-11-14 08:54:50
字体:
来源:转载
供稿:网友

Combination Sum IIPermutationsPermutations II题目描述解决方法

40. Combination Sum II

class Solution {public: void combinationSumBT(vector<vector<int> > & rel, int stt, int &last, vector<int> &candidates, vector<int> &tmp, int target) { if(target == 0) { rel.push_back(tmp); return; } if(stt == last || target < 0) return; for(int i = stt; i < last; i++) { if(target >= 0) { if(candidates[i] > target) return; if(i&&candidates[i]==candidates[i-1]&&i > stt) continue; tmp.push_back(candidates[i]); combinationSumBT(rel, i+1, last, candidates, tmp, target - candidates[i]); tmp.pop_back(); } } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { int c_len = candidates.size(); vector<vector<int> > rel; vector<int> tmp; sort(candidates.begin(), candidates.end()); combinationSumBT(rel, 0, c_len, candidates, tmp, target); return rel; }};

46. Permutations

题目描述:

Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] Subscribe to see which companies asked this question.

class Solution {public: void permutation(vector<vector<int>> &rel, vector<int> &nums, int stt, int last, vector<int> &tmp) { if(stt == last) { rel.push_back(nums); return; } for(int i = stt; i < last; i++) { swap(nums[stt], nums[i]); permutation(rel, nums, stt+1, last, tmp); swap(nums[stt], nums[i]); } } vector<vector<int>> permute(vector<int>& nums) { int nums_len = nums.size(); vector<vector<int>> rel; vector<int> tmp; permutation(rel, nums, 0, nums_len, tmp); return rel; }};

47. Permutations II

题目描述

Given a collection of numbers that might contain duplicates, return all possible unique permutations.For example,[1,1,2] have the following unique permutations:[ [1,1,2], [1,2,1], [2,1,1]]

解决方法

法一:使用set去掉重复部分。

class Solution {public: void permutation2(set<vector<int> > &rel, int stt, const int &last, vector<int>&nums) { if(stt == last) { rel.insert(nums); return; } for(int i = stt; i < last; i++) { swap(nums[i], nums[stt]); permutation2(rel, stt+1, last, nums); swap(nums[i], nums[stt]); } } vector<vector<int>> permuteUnique(vector<int>& nums) { int nums_len = nums.size(); set<vector<int>> tmp; permutation2(tmp, 0, nums_len, nums); vector<vector<int> > rel(tmp.begin(), tmp.end()); return rel; }};

这种做法速度慢,而且浪费空间。所以正确的做法应该是在回溯的部分使用剪枝去除冗余。

法二: 纯粹调用函数:

public: vector<vector<int>> permuteUnique(vector<int>& nums) { auto beg = nums.begin(); auto end = nums.end(); vector<vector<int>> ret; sort(beg, end); do { ret.push_back(nums); } while (next_permutation(beg, end)); return ret; }};

法三:击败91%的代码:

class Solution {public: vector<vector<int> > permuteUnique(vector<int> &num) { int n = num.size(); vector<vector<int>> res; sort(num.begin(), num.end()); //sort the list permuteUnique(num, res, n, 0); return res; } void permuteUnique(vector<int> &num, vector<vector<int>> &res, int n, int s) { if (s == n) { res.push_back(num); return; } for (int j = s; j < n; j++) { if (j > s & num[j] == num[j-1]) continue; //PRevent duplicates move(num, j, s); //set the s-th element in the permutation to be //num[j], while leaving the rest elements sorted permuteUnique(num, res, n, s+1); move(num, s, j); //reset } } void move(vector<int> &num, int j, int i) { num.insert(num.begin() + i + (i > j), num[j]); num.erase(num.begin() + j + (j > i)); }};

法四:击败92.94%。这里需要注意的是在函数permutation2里面,如果last使用&的话会比较慢,变成46%。

class Solution {public: void permutation2(vector<vector<int> > &rel, int stt, int last, vector<int>&nums) { if(stt == last) { rel.push_back(nums); return; } for(int i = stt; i < last; i++) { if(i > stt & nums[i] == nums[i-1]) continue; move(nums, i, stt);//swap(nums[stt], nums[i]); permutation2(rel, stt+1, last, nums); move(nums, stt, i);//swap(nums[stt], nums[i]); } } void move(vector<int> &num, int j, int i) { num.insert(num.begin() + i + (i > j), num[j]); num.erase(num.begin() + j + (j > i)); } vector<vector<int>> permuteUnique(vector<int>& nums) { int nums_len = nums.size(); vector<vector<int> > rel; sort(nums.begin(), nums.end()); permutation2(rel, 0, nums_len, nums); return rel; }};

法五:使用普通的DFS计算。击败92.94%的代码

class Solution {public: void permutation2(vector<vector<int> > &rel, int stt, const int last, vector<int>nums) { if(stt == last) { rel.push_back(nums); return; } for(int i = stt; i < last; i++) { if(i != stt && nums[i] == nums[stt]) continue; swap(nums[stt], nums[i]); permutation2(rel, stt+1, last, nums); } } vector<vector<int>> permuteUnique(vector<int>& nums) { int nums_len = nums.size(); vector<vector<int> > rel; sort(nums.begin(), nums.end()); permutation2(rel, 0, nums_len, nums); return rel; }};
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表