Error message here!

Hide Error message here!

Error message here!

Hide Error message here!

Error message here!

Close

刷题46. Permutations

siwei718 2020-02-12 08:51:00 阅读数:18 评论数:0 点赞数:0 收藏数:0

``````#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
class Solution{
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<vector<int>> next;
unordered_map<int,vector<vector<int>>> dp;
vector<int> cur;
if(nums.empty()) return res;
cur.push_back(nums[0]);
res.push_back(cur);
dp[1] = res;
int currLength = 2;
for(int j=1;j<nums.size();j++){
res = dp[j];
next.clear();
for(int k=0;k<currLength;k++){
cur.clear();
cur.resize(j+1);
for(int m=0;m<res.size();m++){
cur[k] = nums[j];
int t1=0,t2=0;
while(t2<res[m].size()){
if(cur[t1]!=nums[j]){
cur[t1] = res[m][t2];
}else{
++t1;
cur[t1] = res[m][t2];
}
t1++;
t2++;
}
next.push_back(cur);
cur.clear();
cur.resize(j+1);
}
}
currLength++;
dp[j+1] = next;
}
return dp[nums.size()];
}
};
int main(){
Solution s;
vector<int> nums = {1,2,3,4};
vector<vector<int>> r = s.permute(nums);
for(int i=0;i<r.size();i++){
for(int j=0;j<r[i].size();j++){
cout<<r[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}``````

``````Runtime: 8 ms, faster than 98.85% of C++ online submissions for Permutations.
Memory Usage: 9.5 MB, less than 46.27% of C++ online submissions for Permutations.``````

dp算法，是按照空间换时间的，所以时间还可以，空间就差了点。

``````class Solution{
private:
vector<vector<int>> result;
vector<int> path;
vector<bool> used;
public:
//枚举每个位置放哪个数
void dfs(const vector<int>&nums,int pos){
if(pos == nums.size()){
result.push_back(path);
return;
}
for(int i=0;i<nums.size();i++){
if(!used[i]){
path.push_back(nums[i]);
used[i] = true;
dfs(nums,pos+1);
used[i] = false;
path.pop_back();
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
if(nums.empty()){
return result;
}
used.resize(nums.size());
dfs(nums,0);
return result;
}
};``````

https://www.cnblogs.com/siweihz/p/12245079.html