面试中有一道笔试题，大概意思如下：
输入一个集合，输出这个集合的所有子集。例如输入：1，2，4 输出结果如下所示：
[1]
[2]
[4]
[1, 2]
[1, 4]
[2, 4]
[1, 2, 4]
需要认识的：空集是任何集合的子集；真子集为不包含子集的集合；非空真子集即不包含子集与空集合
解题思路：
这道题可以使用“按位对应法”进行计算
如集合a={a,b,c},对于任意一个元素，在每个子集中，要么存在，要么不存在。 映射为子集：
(a,b,c)
(1,1,1)->(a,b,c)
(1,1,0)->(a,b)
(1,0,1)->(a,c)
(1,0,0)->(a)
(0,1,1)->(b,c)
(0,1,0)->(b)
(0,0,1)->(c)
(0,0,0)->@(@表示空集)
观察以上规律，与计算机中数据存储方式相似，故可以通过一个整型数与集合映射...000 ~ 111...111（表示有，表示无，反之亦可），通过该整型数逐次增可遍历获取所有的数，即获取集合的相应子集。
主要考察的是位移运算以及逻辑思维能力，具体代码如下（经过本机真实认证，绝对可靠）：
我要评论
import java.util.arraylist;
import java.util.scanner;
import org.apache.commons.collections.collectionutils;
/**
* 输入一个集合，输出这个集合的所有子集
* @author liangyongxing
* @time 2017-02-06
*/
public class sublistexport {
public static void main(string[] args) {
arraylist<integer> list = new arraylist<integer>();
system.out.println("请输入一串整数并在输入时用英文逗号隔开：");
string inputstring = new scanner(system.in).next().tostring();
if (inputstring != null && !inputstring.isempty()) {
string[] strarray = inputstring.split(",");
for (string str : strarray) {
list.add(integer.parseint(str));
}
arraylist<arraylist<integer>> allsubsets = getsubsets(list);
for(arraylist<integer> sublist : allsubsets) {
system.out.println(sublist);
}
}
}
public static arraylist<arraylist<integer>> getsubsets(arraylist<integer> sublist) {
arraylist<arraylist<integer>> allsubsets = new arraylist<arraylist<integer>>();
int max = 1 << sublist.size();
for(int loop = 0; loop < max; loop++) {
int index = 0;
int temp = loop;
arraylist<integer> currentcharlist = new arraylist<integer>();
while(temp > 0) {
if((temp & 1) > 0) {
currentcharlist.add(sublist.get(index));
}
temp>>=1;
index++;
}42 allsubsets.add(currentcharlist);44 }
return allsubsets;
}
}
注：2017-02-08 10:01:32 上述代码有一定的漏洞即当输入有重复数字的时候，结果会有重复子集输出，并不能满足题目要求，需要在算出子集的时候加入hashset进行排重，最终打印结果从sets中获取即可，具体修改详情如下图所示：
1. 在主函数打印的地方修改接受的返回值为hashset类型
2. 在函数部分需要修改封装列表有list改为set
至此修改完成，测试运行结果如下所示：
分析代码可以得出它的时间复杂度是：o(n*log2n)
代码下载地址:
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持移动技术网！
如对本文有疑问， 点击进行留言回复！！
Mybatis PersistenceException异常：Error building SqlSession The error may exist in SQL Mapper Configur
MyBatis——动态SQL语句——if标签和where标签复合使用
网友评论