面試中有一道筆試題，大概意思如下：
輸入一個集合，輸出這個集合的所有子集。例如輸入：1，2，4 輸出結(jié)果如下所示：
[1]
[2]
[4]
[1, 2]
[1, 4]
[2, 4]
[1, 2, 4]
需要認識的：空集是任何集合的子集；真子集為不包含子集的集合；非空真子集即不包含子集與空集合
解題思路：
這道題可以使用“按位對應(yīng)法”進行計算
如集合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)->@(@表示空集)
觀察以上規(guī)律，與計算機中數(shù)據(jù)存儲方式相似，故可以通過一個整型數(shù)與集合映射...000 ~ 111...111（表示有，表示無，反之亦可），通過該整型數(shù)逐次增可遍歷獲取所有的數(shù)，即獲取集合的相應(yīng)子集。
主要考察的是位移運算以及邏輯思維能力，具體代碼如下（經(jīng)過本機真實認證，絕對可靠）：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
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("請輸入一串整數(shù)并在輸入時用英文逗號隔開："); 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 上述代碼有一定的漏洞即當輸入有重復(fù)數(shù)字的時候，結(jié)果會有重復(fù)子集輸出，并不能滿足題目要求，需要在算出子集的時候加入HashSet進行排重，最終打印結(jié)果從sets中獲取即可，具體修改詳情如下圖所示：
1. 在主函數(shù)打印的地方修改接受的返回值為HashSet類型
2. 在函數(shù)部分需要修改封裝列表有l(wèi)ist改為set
至此修改完成，測試運行結(jié)果如下所示：
分析代碼可以得出它的時間復(fù)雜度是：O(n*log2n)
代碼下載地址:
https://github.com/liang68/interview
以上就是本文的全部內(nèi)容，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作能帶來一定的幫助，同時也希望多多支持服務(wù)器之家！
原文鏈接：http://www.cnblogs.com/liang1101/p/6372115.html
