学后余生
最新的主题!owo
这里可以看到最新发布的主题呢QAQ
Java获取数组中的所有子集,并返回List
2022 / October 16
[Asp.net]注册控件CreateUserWizard移除外部表table
2022 / June 7
[Bukkit]利用反射序列化/反序列化ItemStack
2022 / June 1
ForgeGradle 配置离线的MDK构建环境
2020 / August 26
划水
2020 / August 26
这是测试文章
2020 / August 25
favorite_border
主题分类
所有文章的分类都在这啦
arrow_forward
日常 ( 2 个主题 )
arrow_forward
Bukkit 插件 ( 1 个主题 )
arrow_forward
Forge模组 ( 1 个主题 )
arrow_forward
杂物柜 ( 1 个主题 )
arrow_forward
日常分享 ( 1 个主题 )
标签云☁
会有些什么标签呢?
测试
七夕
难受
文档
hhhhh
看见
文章
实际上
构建
mdk
forge
环境
bukkit
反射
NMS
OBC
序列化
ItemStack
反序列化
控件
table
渲染
login
模版
list
集合
子集
int
array
支持一下,来发点电呗~
owo
爱发电
上一篇 :
[Asp.net]注册控件CreateUserWizard移除外部表table
下一篇 :没啦
Java获取数组中的所有子集,并返回List
日常
0
face
starorbb
·
date_range
2022-10-16
·
people
浏览: 1705
loyalty
标签:
list
集合
子集
int
array
例子: > 输入: S = {a, b, c, d} 输出: {a} , {b}, {c}, {d}, {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}, {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d} 任何给定集合的子集总数等于2^n(n=集合中的元素数)。如果我们仔细观察,上方例子具有的子集总数为2^4=16(包含空子集),它只不过是从0到15的二进制数,如下所示: > 0000 {} 0001 {a} 0010 {b} 0011 {a, b} 0100 {c} 0101 {a, c} 0110 {b, c} 0111 {a, b, c} 1000 {d} 1001 {a, d} 1010 {b, d} 1011 {a, b, d} 1100 {c, d} 1101 {a, c, d} 1110 {b, c, d} 1111 {a, b, c, d} 从最右边开始,第i个位置的1表示集合的第i个元素存在,而0表示元素不存在。因此,我们要做的只是生成从0到2^n –1(上述例子为2^4-1=15)的二进制数,其中n是集合的长度。 此方式使用了位运算的方式,以二进制数来表示元素的存在与否。该算法时间复杂度:O(n*(2^n)),外部循环 O(2^n),内部循环 O(n)。 算法代码(使用泛型): ```java public static
List
> getSubsets(E[] array) { int n = array.length; List
> list = new ArrayList<>(); for (int i = 0; i < (1 << n); i++) { List
temp = new ArrayList<>(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) > 0) { temp.add(array[j]); } } if (temp.size() != 0) { list.add(temp); } } return list; } ``` 算法代码(仅整型数组): ```java public static List
> getSubsets(int[] array) { int n = array.length; List
> list = new ArrayList<>(); for (int i = 0; i < (1 << n); i++) { List
temp = new ArrayList<>(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) > 0) { temp.add(array[j]); } } if (temp.size() != 0) { list.add(temp); } } return list; } ``` 通过主类调用方法并输出全部子集(不包含空子集): ```java public static void main(String[] args) { List
> list = getSubsets(new int[] {2, 6, 8, 1}); for (List
l : list) { System.out.print("{ "); for (int i : l) { System.out.print(i + " "); } System.out.println("}"); } } ``` #### 回顾Java位运算符: | 运算符 | 描述 | 例子 | 等同于 | 结果 | 十进制 | | :------------: | :------------: | :------------: | :------------: | :------------: | :------------: | | & | AND - 如果两个位都为 1,则将每个位设置为 1 | 5 & 1 | 0101 & 0001 | 0001 | 1 | | 丨 | OR - 如果两个位中的任何一个为 1,则将每个位设置为 1 | 5丨1 | 0101丨0001 | 0101 | 5 | | ~ | NOT - 反转所有位 | ~5 | ~0101 | 1010 | 5 | | ^ | XOR - 如果两个位中只有一个为 1,则将每个位设置为 1 | 5^1 | 0101^0001 | 0100 | 4 | | << | Zero-fill left shift - 通过从右侧推入零并让最左边的位脱落来向左移动 |9 << 1 | 1001 << 1 | 0010 | 2 | | >> | Signed right shift - 通过从左侧推入最左侧位的副本并让最右侧位脱落来右移 | 9 >> 1 | 1001 >> 1 | 1100 | 12 | | >>> | Zero-fill right shift - 通过从左边推入零并让最右边的位脱落来右移 | 9 >>> 1 | 1001 >>> 1 | 0100 | 4 | 参考内容:[w3schools](https://www.w3schools.cn/java/java_operators.asp "w3schools") [geeksforgeeks](https://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/ "geeksforgeeks")
explore
">
add
关于
所有主题
登陆