扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
面试中有一道笔试题,大概意思如下:
创新互联是一家集网站建设,萝北企业网站建设,萝北品牌网站建设,网站定制,萝北网站建设报价,网络营销,网络优化,萝北网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。
输入一个集合,输出这个集合的所有子集。例如输入: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) { ArrayListlist = new ArrayList (); 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 > allsubsets = getSubsets(list); for(ArrayList subList : allsubsets) { System.out.println(subList); } } } public static ArrayList > getSubsets(ArrayList subList) { ArrayList > allsubsets = new ArrayList >(); int max = 1 << subList.size(); for(int loop = 0; loop < max; loop++) { int index = 0; int temp = loop; ArrayList currentCharList = new ArrayList (); 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)
代码下载地址:
https://github.com/liang68/interview
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持创新互联!
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流