to do
8.3.2 Next Permutation
reference to sth can not "repoint" like pointer does
实在写太久了哭。。mark
void nextPermutation(vector<int>& nums) {
int pivoti = -1;
// from R->L, find first occurence of out of order.(descending) if 1220, 1
for (int i=nums.size()-1; i>0; --i) {
if (nums[i-1] < nums[i]) {
pivoti=i-1;
break;
}
}
if (pivoti==-1) {
reverse(nums.begin(), nums.end());
return;
}
// from R->L. find first occurence of greater than [pivoti]
for (int j=nums.size()-1; j>=0; --j) {
if (nums[j] > nums[pivoti]) {
swap(nums[j], nums[pivoti]);
// int tmp = nums[pivoti];
// nums[pivoti] = nums[j];
// nums[j] = tmp;
reverse(nums.begin()+pivoti+1, nums.end());
return;
}
}
}
std::for_each
template <class InputIterator, class Function>
Function for_each (InputIterator first, InputIterator last, Function fn);
**Apply function to range**
template <class InputIterator,class Function>
Function for_each(InputIterator first, InputIterator last, Function fn) {
while (first!=last) { fn (*first); ++first; }
return fn;// or, since C++11: return move(fn);
}
8.4.3] permutation II rec, 也可以用next permutation
或者看了答案的..感觉自己想的话,这个方法并不trivial。希望下次做的时候再明白透彻些。
有compiler问题,error required from here,ubuntu下次跑!
lambda func:[&reference_to_captured_var](params) {};
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
n = nums.size();
// record occurences of each elem in map
unordered_map<int, int> map;
for (auto i: nums) ++map[i];
// convert map to vector of pair for tmp recording
vector<pair<int, int>> record;
// fn appy to each unordered_map<Key,T> entry, WHICH IS PAIR<INT, INT>
for_each(map.begin(), map.end(), [&record](pair<int, int>& entry){
record.push_back(entry);
});
vector<int> path;
vector<vector<int>> ret;
permuteR(record.begin(), record.end(), path, ret);
return ret;
}
private:
size_t n;
void permuteR(vector<pair<int, int>>::iterator begin, vector<pair<int, int>>::iterator end, vector<int>& path, vector<vector<int>>& ret) {
if (path.size()==n) {
ret.push_back(path);
return;
}
// iterate through nums, if hasn't used up all occurrences of some elem, add and backtrack
for (auto it=begin; it<end; ++it) {
// count occurrence of *it .first in path
int ct = 0;
for (auto p=path.begin(); p<path.end(); ++p) {
if (*p==(*it).first) ++ct;
}
// if still (*it).first left to use, append
if ((*it).second > ct) {
path.push_back((*it).first);
permuteR(begin, end, path, ret);
path.pop_back();
}
}
}
};
网友评论