面试中有一道笔试题,大概意思如下:
输入一个集合,输出这个集合的所有子集。例如输入:1,2,4输出结果如下所示:
[1]
[2]
[4]
[1,2]
[1,4]
(2、4)
(1、2、4)
<强>需要认识的:空集是任何集合的子集;真子集为不包含子集的集合;非空真子集即不包含子集与空集合
<>强解题思路:
这道题可以使用“按位对应法”进行计算
如集合={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年(表示有,表示无,反之亦可),通过该整型数逐次增可遍历获取所有的数,即获取集合的相应子集。
主要考察的是位移运算以及逻辑思维能力,具体代码如下(经过本机真实认证,绝对可靠):
进口java.util.ArrayList;
进口java.util.Scanner;
进口org.apache.commons.collections.CollectionUtils;/* *
*输入一个集合,输出这个集合的所有子集
* @author liangyongxing
* @time 2017-02-06
*/公开课SubListExport {
公共静态void main (String [] args) {
ArrayList列表=new ArrayList ();
System.out.println(“请输入一串整数并在输入时用英文逗号隔开:");
字符串inputString=new扫描仪(系统). next () .toString ();
如果(inputString !=零,,! inputString.isEmpty ()) {
String [] strArray=inputString.split (", ");
(字符串str: strArray) {
list.add (Integer.parseInt (str));
}
ArrayList比;allsubsets=getSubsets(列表);
(ArrayList子列表:allsubsets) {
System.out.println(子表);
}
}
}
公共静态ArrayList比;getSubsets (ArrayList分表){
ArrayList比;allsubsets=new ArrayList在();
int max=1 & lt; & lt;subList.size ();
for (int循环=0;循环& lt;马克思;循环+ +){
int指数=0;
int temp=循环;
ArrayListcurrentCharList=new ArrayList ();
而(临时比;0){
如果(temp,1)比;0){
currentCharList.add (subList.get(指数));
}
temp>祝辞=1;
指数+ +;
}42 allsubsets.add (currentCharList); 44}
返回allsubsets;
}
}
之前
注:2017-02-08 10:01:32 上述代码有一定的漏洞即当输入有重复数字的时候,结果会有重复子集输出,并不能满足题目要求,需要在算出子集的时候加入HashSet进行排重,最终打印结果从集合中获取即可,具体修改详情如下图所示:
至此修改完成,测试运行结果如下所示:
<强>代码下载地址:
https://github.com/liang68/interview
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持!
