LeetCode: Permutations II

一些小失误，基本一次过，这题可以明显看到自己的进步，map用得比较成熟了

 1 class Solution {
 2 public:
 3     void dfs(int dep, int maxdep, map<int, int> &s, vector<vector<int>> &ret, vector<int> &tmp) {
 4         if (dep == maxdep) {
 5             ret.push_back(tmp);
 6             return;
 7         }
 8         for (map<int, int>::iterator it = s.begin(); it != s.end(); it++) {
 9             int temp = it->first;
10             if (s[temp]) {
11                 s[temp]--;
12                 tmp.push_back(temp);
13                 dfs(dep+1, maxdep, s, ret, tmp);
14                 tmp.pop_back();
15                 s[temp]++;
16             }
17         }
18     }
19     vector<vector<int> > permuteUnique(vector<int> &num) {
20         // Start typing your C/C++ solution below
21         // DO NOT write int main() function
22         map<int, int> s;
23         sort(num.begin(), num.end());
24         int size = num.size();
25         for (int i = 0; i < size; i++) {
26             map<int, int>::iterator it;
27             it = s.find(num[i]);
28             if (it == s.end()) {
29                 s.insert(pair<int, int>(num[i], 1));
30             }
31             else s[num[i]]++;
32         }
33         vector<vector<int>> ret;
34         vector<int> tmp;
35         dfs(0, size, s, ret, tmp);
36         return ret;
37     }
38 };

推荐下一段代码

 1 class Solution {
 2 public:
 3     void dfs(vector<int> &num, vector<vector<int> > &ans, int k) {
 4         if (k == num.size()) {
 5             ans.push_back(num);
 6             return;
 7         }
 8         set<int> visit;
 9         for (int i = k; i < num.size(); ++i) {
10             if (visit.find(num[i]) != visit.end()) continue;
11             swap(num[i], num[k]);
12             dfs(num, ans, k+1);
13             swap(num[i], num[k]);
14             visit.insert(num[i]);
15         }
16     }
17     vector<vector<int> > permuteUnique(vector<int> &num) {
18         vector<vector<int> > ans;
19         sort(num.begin(), num.end());
20         dfs(num, ans, 0);
21         return ans;
22     }
23 };

 1 public class Solution {
 2     public List<List<int>> PermuteUnique(int[] nums) {
 3         List<List<int>> ans = new List<List<int>>();
 4         Array.Sort(nums);
 5         dfs(nums, ref ans, 0);
 6         return ans;
 7     }
 8     public void dfs(int[] nums, ref List<List<int>> ans, int dep) {
 9         if (dep == nums.Length) {
10             ans.Add(new List<int>(nums));
11             return;
12         }
13         HashSet<int> visit = new HashSet<int>();
14         for (int i = dep; i < nums.Length; i++) {
15             if (visit.Contains(nums[i])) continue;
16             int tmp = nums[i];
17             nums[i] = nums[dep];
18             nums[dep] = tmp;
19             dfs(nums, ref ans, dep+1);
20             tmp = nums[i];
21             nums[i] = nums[dep];
22             nums[dep] = tmp;
23             visit.Add(nums[i]);
24         }
25     }
26 }

View Code