[LeetCode]78. 子集(位运算;回溯法待做)
2024-08-29 11:18:00
题目
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
方法一 位运算
- 此方法仅限nums的长度为32以下,否则溢出。
- 对于长度为len的数组nums={2,3,4,5},掩码范围[0,2^4),有
2^4==1<<len
。 - 对于每个掩码,掩码为1的位的nums元素加入当前所求子集中,
((bitMask >> i) & 1)
可以判断掩码的哪些位为1。故每条掩码对应一个子集。
方法二 枚举
- 遍历数组,每次,将当前所有子集都加上当前元素构成新的一些子集,加入当前子集集合中。
方法三 回溯
todo
回溯法待做。
代码
方法一 位运算
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> subSetList = new LinkedList<>();
int len = nums.length;
int subSetCnt = 1 << len;// 子集数目
for (int bitMask = 0; bitMask < subSetCnt; ++bitMask) {
List<Integer> subSet = new LinkedList<>();
for (int i = 0; i < len; ++i) {
if (((bitMask >> i) & 1) == 1) { // 如果掩码第(低)i位为1
subSet.add(nums[i]);
}
}
subSetList.add(subSet);
}
return subSetList;
}
方法二 枚举
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> subSetList = new LinkedList<>();
int len = nums.length;
subSetList.add(new LinkedList<>());
for (int i = 0; i < len; ++i) {
int curSubSetCnt = subSetList.size();
for (int j = 0; j < curSubSetCnt; ++j) { // 注意这里用常数curSubSetCnt,保证只遍历列表未加入这个元素之前的所有子集
List<Integer> newSebSet = new LinkedList<>(subSetList.get(j));
newSebSet.add(nums[i]);
subSetList.add(newSebSet);
}
}
return subSetList;
}
最新文章
- Atitit onvif 协议截图 getSnapshotUri&#160;使用java
- 将SHP导入MySQL中
- leetcode 189
- Visual C++ 中的重大更改
- MySQL安装及主从配置
- Java设计模式-享元模式(Flyweight)
- ASP.NET页面刷新的实现方法总结
- javascript-函数进阶
- Objective c 自动释放池
- k近邻法(KNN)知识点概括
- 学习如何看懂SQL Server执行计划——基本知识篇
- Java面向对象 String 基本数据类型对象包装类
- Django开发基础----操作数据库
- JAVA经典算法40题(原题+分析)之分析
- 我的工具:Ping工具
- LeetCode 791. Custom Sort String
- DICOM医学图像处理:WEB PACS初谈四,PHP DICOM Class
- Https协议报错:com.sun.net.ssl.internal.www.protocol.https.HttpsURLConnectionOldImpl解决方法
- 谷歌浏览器把网页打印成pdf
- SSM框架搭建教程(从零开始,图文结合)
热门文章
- 日记——递归or搜索?
- Disruptor极速队列
- Android Studio 代码回退
- JavaScript学习系列博客_22_JavaScript this(上下文对象)
- cpu相关信息(进程、线程、核...)
- [Warning] TIMESTAMP with implicit DEFAULT value is deprecated. Please use --explicit_defaults_for_timestamp server option (see documentation for more details).
- 0基础算法基础学算法 第八弹 递归进阶,dfs第一讲
- lombook插件的说明
- 操作系统-I/O(4)I/O控制方式
- 第六篇Scrum冲刺博客--Interesting-Corps