java是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台(即JavaEE, JavaME, JavaSE)的总称。本站提供基于Java框架struts,spring,hibernate等的桌面应用、web交互及移动终端的开发技巧与资料

保持永久学习的心态,将成就一个优秀的你,来 继续搞起java知识。

请编写一个方法,返回某集合的所有非空子集。

给定一个int数组A和数组的大小int n,请返回A的所有非空子集。保证A的元素个数小于等于20,且元素互异。各子集内部从大到小排序,子集之间字典逆序排序,见样例。

[123,456,789]

子集:{[789,456,123],[789,456],[789,123],[789],[456 123],[456],[123]}

集合的每个元素都可以通过bit来表示

1表示有这个数 0表示没有这个数

子集可以通过二进制的方式表示

1 1 1 7 789,456,123

1 1 0 6 789,456

1 0 1 5 789,123

1 0 0 4 789

0 1 1 3 456 123

0 1 0 2 456

0 0 1 1 123

0 0 0 0 空集

所以这个问题可以转化为:怎样可以从大到小的遍历二进制?

int i=(1<

for(int i=i;i>=0;i-—){

for(int j=n-1;j>=0;j-—){

if((i&1<0){

集合里面有这个数 加入进去

}}

}

完整代码:

import java.util.*;

public class Subset {

public ArrayList> getSubsets(int[] A, int n) {

ArrayList> res = new ArrayList>();

if(n==0){//合法性检测

return res;

}

Arrays.sort(A);//排序从小到大

swap(A,0,n-1);//排序从大到小

int start = (1<

for(int i=start;i>0;i--){//遍历二进制的方法

ArrayList item = new ArrayList();

for(int j=n-1;j>=0;j--){//保证从大到小序列间有序

if((i&(1<0){

item.add(A[n-1-j]);

}

}

res.add(item);

}

return res;

}

public void swap(int[] A,int start,int end){

while(start

if(A[start]

A[start] = A[start]^A[end];

A[end] = A[start]^A[end];

A[start] = A[start]^A[end];

}

start++;

end--;

}

}

}

题目链接:http://www.nowcoder.com/practice/1f2700e2b1904254b55765479e9b8766?rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

java集合的子集

因为水平有限,难免有疏忽或者不准确的地方,希望大家能够直接指出来,我会及时改正。一切为了知识的分享。

后续会有更多的精彩的内容分享给大家。