Leetcode 90 - Subsets II（Search）

2019-11-08 03:06:24

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

題意

生成一個數(shù)組的所以子集。

思路

和之前的subsets一樣，但是關(guān)鍵問題是要去重。

算法1

很暴力，用一個set套一個multiset來判斷當(dāng)前結(jié)果是否出現(xiàn)過。

算法2

我們先將數(shù)組排序，然后開始考慮怎么去重。

在含有重復(fù)元素的時候，如果當(dāng)前數(shù)和前面一個數(shù)相同的時候：當(dāng)前僅當(dāng)前面的一個數(shù)使用時，當(dāng)前數(shù)字才能使用。

于是，我們添加一個use數(shù)組來記錄某位置是否訪問。

算法3

不用use數(shù)組直接跳過相同的元素。

代碼

//algorithm 1class Solution {PRivate: set<multiset<int>> has; vector<vector<int>> ans;public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { int n = nums.size(); for (int s = 0; s < (1 << n); s++) { vector<int> v; multiset<int> hs; for (int i = 0; i < n; i++) { if (s & (1 << i)) { v.push_back(nums[i]); hs.insert(nums[i]); } } if (has.find(hs) == has.end()) { ans.push_back(v); has.insert(hs); } } return ans; }};//algorithm 2class Solution {public: vector<vector<int>> ans; vector<int> a; void dfs(int pos, vector<int>& use, vector<int>& v) { if (pos == a.size()) { ans.push_back(v); return; } dfs(pos + 1, use, v); if (pos && a[pos] == a[pos - 1]) { if (use[pos - 1]) { use[pos] = 1; v.push_back(a[pos]); dfs(pos + 1, use, v); v.pop_back(); use[pos] = 0; } } else { use[pos] = 1; v.push_back(a[pos]); dfs(pos + 1, use, v); v.pop_back(); use[pos] = 0; } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); a = nums; vector<int> use(nums.size(), 0); vector<int> v; dfs(0, use, v); return ans; }};//algorithm 3class Solution {private: vector<vector<int>> ans;public: void dfs(vector<int>& v, vector<int>& a, int pos) { ans.push_back(v); for (int i = pos; i < a.size(); i++) { v.push_back(a[i]); dfs(v, a, i + 1); v.pop_back(); while (a[i] == a[i + 1]) i++; } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<int> v; dfs(v, nums, 0); return ans; }};

上一篇：判斷n 是不是素數(shù)

下一篇：筆試題（帶答案）