排列
permutation i ii 递归方法
class Solution {
void helper(vector<vector<int> > & result, vector<int> & nums, vector<int> & now, vector<bool>& flag) {
if(now.size() == nums.size()) {
result.push_back(now);
return;
}
for(int i = 0; i < nums.size(); i++) {
if(flag[i] == false) {
now.push_back(nums[i]);
flag[i] = true;
helper(result,nums,now,flag);
now.pop_back();
flag[i] = false;
}
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > result;
vector<int> now;
vector<bool> flag(nums.size(), false);
helper(result, nums, now, flag);
return result;
}
};
非unique
class Solution {
void helper(vector<vector<int> > & result, vector<int> & nums, vector<int> & now, vector<bool>& flag) {
if(now.size() == nums.size()) {
result.push_back(now);
return;
}
for(int i = 0; i < nums.size(); i++) {
if(i > 0 && nums[i] == nums[i-1] && flag[i-1] == false) {
continue;
}
if(flag[i] == false) {
now.push_back(nums[i]);
flag[i] = true;
helper(result,nums,now,flag);
now.pop_back();
flag[i] = false;
}
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int> > result;
vector<int> now;
vector<bool> flag(nums.size(), false);
vector<int> sorted_nums(nums);
sort(sorted_nums.begin(), sorted_nums.end());
helper(result, sorted_nums, now, flag);
return result;
}
};
next permutation
http://blog.csdn.net/qq575787460/article/details/41206601
http://blog.csdn.net/qq575787460/article/details/41215475
https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
这个感觉更难的是证明
时间复杂度是O(n)
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int k;
for(k = nums.size() - 2; k >= 0; k--) {
if(nums[k] < nums[k + 1]) {
break;
}
}
if(k == -1) {
reverse(nums.begin(), nums.end());
return;
}
int l;
for(l = nums.size() - 1; l > k; l--) {
if(nums[l] > nums[k]) {
break;
}
}
swap(nums[k], nums[l]);
reverse(nums.begin() + k + 1, nums.end());
}
};
binary search版本：
注意binary search中==的情况
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int k;
for(k = nums.size() - 2; k >= 0; k--) {
if(nums[k] < nums[k + 1]) {
break;
}
}
if(k == -1) {
reverse(nums.begin(), nums.end());
return;
}
int l = k + 1,r = nums.size() - 1;
while(l < r) {
int m = l + (r - l) / 2 + 1;
if(nums[m] <= nums[k]) {
r = m - 1;
} else {
l = m;
}
}
swap(nums[k], nums[l]);
reverse(nums.begin() + k + 1, nums.end());
}
};
组合
subsets
dfs方法
class Solution {
void helper(vector<vector<int> > & result, vector<int> & nums, vector<int> & now, int begin) {
result.push_back(now);
if(begin > nums.size()) {
return;
}
for(int i = begin; i < nums.size(); i++) {
now.push_back(nums[i]);
helper(result, nums, now, i + 1);
now.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& unsorted_nums) {
vector<vector<int> > result;
vector<int> now;
vector<int> nums(nums);
sort(nums.begin(), nums.end());
helper(result, nums, now, 0);
return result;
}
};
iterative方法
class Solution {
public:
vector<vector<int>> subsets(vector<int>& unsorted_nums) {
vector<vector<int> > result;
vector<int> nums(unsorted_nums);
sort(nums.begin(), nums.end());
result.push_back(vector<int>());
for(int i = 0; i < nums.size(); i++) {
int n = result.size();
for(int j = 0; j < n; j++) {
result.push_back(result[j]);
result.back().push_back(nums[i]);
}
}
return result;
}
};
bitmap方法
class Solution {
public:
vector<vector<int>> subsets(vector<int>& unsorted_nums) {
int n = pow(2, unsorted_nums.size());
int m = unsorted_nums.size();
vector<int> nums(unsorted_nums);
sort(nums.begin(), nums.end());
vector<vector<int> > result(n, vector<int>());
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(((i >> j) & 1) == 1) {
result[i].push_back(nums[j]);
}
}
}
return result;
}
};
subsetsii
含重复元素
dfs
class Solution {
void helper(vector<vector<int> > & result, vector<int> & nums, vector<int> & now, int begin) {
result.push_back(now);
if(begin > nums.size()) {
return;
}
for(int i = begin; i < nums.size(); i++) {
if(i > begin && nums[i] == nums[i-1])
continue;
now.push_back(nums[i]);
helper(result, nums, now, i + 1);
now.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& unsorted_nums) {
vector<vector<int> > result;
vector<int> now;
vector<int> nums(unsorted_nums);
sort(nums.begin(), nums.end());
helper(result, nums, now, 0);
return result;
}
};
iterative
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& unsorted_nums) {
vector<vector<int> > result;
result.push_back(vector<int>());
vector<int> nums(unsorted_nums);
sort(nums.begin(), nums.end());
int n = nums.size();
int m, start;
for(int i = 0; i < n; i++) {
if(i > 0 && nums[i] == nums[i-1]) {
start = m;
} else {
start = 0;
}
m = result.size();
for(int j = start; j < m; j++) {
result.push_back(result[j]);
result.back().push_back(nums[i]);
}
}
return result;
}
};
letter combinations of a phone number
很有意思的一道题，iterative到极致，虽然不明白为啥空字符串返回{}，而不是{""}
class Solution {
public:
vector<string> letterCombinations(string digits) {
if(digits.size() == 0) return {};
vector<string> result;
result.push_back("");
string dic[9] = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
for(int i = 0; i < digits.size(); i++) {
vector<string> tmp;
int n = result.size();
int digit = digits[i] - '1';
for(int j = 0; j < dic[digit].size(); j++) {
for(int k = 0; k < n; k++) {
tmp.push_back(result[k]);
tmp.back().push_back(dic[digit][j]);
}
}
result.swap(tmp);
}
return result;
}
};
