78. Subsets
Given a set of distinct integers, nums, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3]
, a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
问题: 给定一个集合,求集合元素的所有组合的情况。
实际上就是一题求全组合的题目。
nums[i...n) 的所有组合情况可以分为两种:包含nums[i] 的 和 不包含 nums[i] 的。
- 包含 nums[i] 的:nums[i] 依次加到 nums[i+1...n) 的全部情况即可。
- 不包含 nums[i] 的 :就是 nums[i+1...n) 的全部情况。
上面的递推关系,实际上就是 DP 思路。
vector<vector<int>> theset; void regardValue(int value){ if (theset.size() == ) {
vector<int> tmp0;
vector<int> tmp1 = {value};
theset.push_back(tmp0);
theset.push_back(tmp1);
return;
} int LofPre = (int)theset.size(); for (int i = ; i < LofPre; i++) {
vector<int> tmp = theset[i];
tmp.push_back(value);
theset.push_back(tmp);
}
} vector<vector<int>> subsets(vector<int>& nums) { std::sort(nums.begin(), nums.end()); for (int i = ; i < nums.size(); i++) {
regardValue(nums[i]);
} return theset;
}
90. Subsets II
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2]
, a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
问题:若集合中包含重复值,求所有的可能组合,即子集合。
要求:子集合内可以有重复值,但是子集合之间不可以有重复的子集合。
同样采用原来的思路,用 unordered_set<vector<int>> 代替 vector<vector<int>> ,就得最后结果后,再转为 vector<vector<int>> 即可。
在实现过程中发现 unordered_set<vector<int>> 不能直接使用。在 * 看到解法方法,增加对 vector<int> 结构进行 hash 即可使用。修改后,算法实现并通过。
struct VectorHash {
size_t operator()(const vector<int>& v) const {
hash<int> hasher;
size_t seed = ;
for (int i : v) {
seed ^= hasher(i) + 0x9e3779b9 + (seed<<) + (seed>>);
}
return seed;
}
}; vector<vector<int>> theset; unordered_set<vector<int>, VectorHash> uniSet; void regardValue(int value){ if (uniSet.size() == ) {
vector<int> tmp0;
vector<int> tmp1 = {value};
uniSet.insert(tmp0);
uniSet.insert(tmp1);
return;
} unordered_set<vector<int>, VectorHash> cpSet = uniSet; unordered_set<vector<int>, VectorHash>::iterator t_iter; for (t_iter = cpSet.begin(); t_iter != cpSet.end(); t_iter++) {
vector<int> tmp = *t_iter; tmp.push_back(value);
uniSet.insert(tmp);
}
} vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); for (int i = ; i < nums.size(); i++) {
regardValue(nums[i]);
} unordered_set<vector<int>, VectorHash>::iterator t_iter; for (t_iter = uniSet.begin(); t_iter != uniSet.end(); t_iter++) {
vector<int> tmp = *t_iter;
theset.push_back(tmp);
} return theset; }
[LeetCode] Subsets I (78) & II (90) 解题思路,即全组合算法的更多相关文章
-
leetCode 90.Subsets II(子集II) 解题思路和方法
Given a collection of integers that might contain duplicates, nums, return all possible subsets. Not ...
-
[LeetCode] Course Schedule I (207) &; II (210) 解题思路
207. Course Schedule There are a total of n courses you have to take, labeled from 0 to n - 1. Some ...
-
[LeetCode] Search in Rotated Sorted Array I (33) &;&; II (81) 解题思路
33. Search in Rotated Sorted Array Suppose a sorted array is rotated at some pivot unknown to you be ...
-
leetCode 81.Search in Rotated Sorted Array II (旋转数组的搜索II) 解题思路和方法
Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would this ...
-
leetCode 82.Remove Duplicates from Sorted List II (删除排序链表的反复II) 解题思路和方法
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numb ...
-
[LeetCode] 74. Search a 2D Matrix 解题思路
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the follo ...
-
[LeetCode] 347. Top K Frequent Elements 解题思路 - Java
Given a non-empty array of integers, return the k most frequent elements. For example,Given [1,1,1,2 ...
-
[LeetCode] 307. Range Sum Query - Mutable 解题思路
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive ...
-
leetCode 86.Partition List(分区链表) 解题思路和方法
Given a linked list and a value x, partition it such that all nodes less than x come before nodes gr ...
随机推荐
-
ue4 UE4Editor.lib找不到
PublicDependencyModuleNames里加了Launch后,会导致链接UE4Editor.lib, 但这个文件在预编版的引擎里是没有的(奇怪的是自己编译引擎的话会有) 如果只是要头文件 ...
-
Test Android with QTP
by Yaron Assa I have recently come across a plug-in to QTP that enables to automate tests on Android ...
-
编译android程序时DEX过程出现错误
今天编译高级设置时出现了错误,这好坑爹啊~ 于是我开始检查代码,发现代码没有错误啊,然后观察MAKE的步骤才发现是DEX时出现了问题!! 下面是错误的LOG: Information:Using ja ...
-
Codeforces Beta Round #80 (Div. 1 Only) D. Time to Raid Cowavans 离线+分块
题目链接: http://codeforces.com/contest/103/problem/D D. Time to Raid Cowavans time limit per test:4 sec ...
-
poj 2479 (DP)
求一个区间内连续两段不相交区间最大和. // File Name: 2479.cpp // Author: Missa_Chen // Created Time: 2013年06月22日 星期六 16 ...
-
Elasticsearch升级至1.x后API的变化-三
请支持原创:http://www.cnblogs.com/donlianli/p/3841762.html 1.索引格式 1.x之前的版本,被索引的文档type会同时出现在url和传输的数据格式中 ...
-
WildMagic 简单图元(一)
#include <Wm5WindowApplication3.h> #include <Wm5VisualEffectInstance.h> using namespace ...
-
JS的DOM操作及动画
JS的DOM操作DOM:Document Object ModelBOM:Bowers(浏览器) Object Model找到元素:var a=document.getElementById(&quo ...
-
层居中绝对定位的div的居中方法,下面的写法兼容IE系列浏览器和火狐浏览器
详细解说,直接看样式:#dingwei{padding:10px;background-color:#003300;color:#FFFFFF; width:600px;height:300px; d ...
-
WEB站点服务器安全配置
WEB站点服务器安全配置 本文转自:i春秋社区 // 概述 // 熟悉网站程序 // 更改默认设置的必要性 // 目录分析与权限设置技巧 // 防止攻击其他要素 // 公司官网不可忽视的安全性 ...