和算法渣一起练习--利用位运算，轻轻松松就能解决数学里的子集问题
和算法渣一起练习--利用位运算，轻轻松松就能解决数学里的子集问题
前言
为什么要说算法？老实说，算法的重要性其实是毋庸置疑的，当然了，平时做CURD工作的时候，其实数据结构其实更重要一些，比如表的设计，以及部分场景下，比如秒杀这类，一般是需要在redis等内存中去维护一些数据结构，方便我们提升性能。
但基本来说，部分场景下，定下了数据结构，也就间接地定下了对应的算法；对于一个数组，要写一个算法，支持随机读取，就很简单；对于一个链表，要写一个算法，支持随机读取，那就得遍历。
个人觉得，算法和数据结构是一个并重的关系，数据结构的学习还是相对容易的，算法嘛，就，啊哈，你懂的。
毕业多年来，也曾经尝试过多次算法方面的学习，每次都是不了了之，我觉得，有可能是学习的方式不太对。以前看算法，要么拿本书在那看；要么弄不出来，就把答案找出来看一遍，看了就算完了，有时候呢，会把答案的代码debug一遍。
总的来说，学习效果真的太差了。
写这个系列（我也不知道能不能坚持，至少先开一个头），就是这么想的，学一个东西，不管是啥，不仅要有输入，也要有输出，输出是什么呢，就是把我觉得已经会了的东西，讲给大家听，大家能学到一点，我也高兴；学不到，那就倾听并改进。
也鼓励大家去输出，不管是笔记，脑图，还是博客，都是一个沉淀的方式，大家可以自由选择。
好了，大家就跟着我这个算法渣一起，学一点算法吧。
题目描述及解析
原题链接：https://leetcode-cn.com/problems/subsets/
这个题目，大家看上面的示例部分可以知道，就是给你一个整数集合，返回它的全部子集，比如给你一个集合[1,2],那它的子集就有：
[],[1],[2],[1,2]
我们再来看看，最终的子集的数量，和集合中元素的个数，似乎有关系，比如，集合[1,2]中包含2个元素，最终结果是4个子集，正好是2的2次方；集合[1,2,3]中包含3个元素，最终结果是8个子集，则是2的3次方。
总结下来就是，集合中有n个元素，则最终子集个数为2的n次方。
这难道是巧合吗，我觉得不是，大家可以思考下，这个题，像不像是从一堆球中，选择其中的一部分球。对于每一个球来说，只有两种结果：被选中或者没被选中。
针对每个球，有2种选法，那n个球，是不是就是2的n次方种选法呢？
如果用true，false来表达被选中和没被选中，那么，针对[1,2,3]这个集合来说，可能的子集，可以如下表示：
1被选中 2被选中 3被选中
false false false
false false true
false true false
false true true
true false false
true false true
true true false
true true true
但是，我发现，用程序来生成这样一个集合，并不容易，具体怎么不容易，可以自行试试哈。
我们转换下思路，采用0表示没被选中，1表示选中。
1被选中 | 2被选中 | 3被选中 | 子集 | 二进制数 | 十进制数 |
|---|---|---|---|---|---|
0 | 0 | 0 | [] | 000 | 0 |
0 | 0 | 1 | [3] | 001 | 1 |
0 | 1 | 0 | [2] | 010 | 2 |
0 | 1 | 1 | [2,3] | 011 | 3 |
1 | 0 | 0 | [1] | 100 | 4 |
1 | 0 | 1 | [1,3] | 101 | 5 |
1 | 1 | 0 | [1,2] | 110 | 6 |
1 | 1 | 1 | [1,2,3] | 111 | 7 |
上面的表格中，我们罗列了全部的组合，注意倒数第二列，我们使用二进制数来表达这个选项，比如001，表示只选中了3.
那么，我们应该就可以遍历000到111，就得到了所有的子集，而转换为十进制，就是从000遍历到(2的n次方-1)。
大体的逻辑就是这样：
int resultLength = 1 << 3; (即2的3次方)
for(int i = 0; i < resultLength; i++){
// 使用java.lang.Integer#toBinaryString，可直观看到该int对应的二进制位
System.out.println(Integer.toBinaryString(i));
// todo 根据当前二进制，来选择对应的元素
}
下边的代码比较直观：
int resultLength = 1 << 3;
for (int i = 0; i < resultLength; i++) {
System.out.println(Integer.toBinaryString(i));
}
输出如下：
0
1
10
11
100
101
110
111
通过位运算，来选择出对应的元素
现在的问题变成了，假设当前遍历到6，即110这个选项时，我们人类，可以知道该选项对应了[1,2].
但是计算机要怎么来对应呢？我们可以遍历我们的数组，来依次检查每个元素对应的二进制bit是否为1，如果为1，说明该元素被选中了，加到结果集中，比如遍历到1这个元素的时候，它在数组中的下标为0（数组下标从0开始别忘）。
那么，那么它在110这个二进制中，它是存储在哪个bit呢？是存储在最高位的bit的。
所以，对于数组[1,2,3]中的第一个值1，其对应了二进制中的高位，需要右移n-1（n为数组长度，这里为3），即右移2位后进行计算；
对于数组[1,2,3]中的第二个值2，其对应了二进制中的第1位，需要右移3-2位，即右移1位。
对于数组中第三个值3，其对应了二进制中的第0位，需要右移3-3位，即不需移位。
好了，接下来，我们转换为代码：
class Solution {
public static void main(String[] args) {
List<List<Integer>> set = subsets(new int[]{1, 2, 3});
for (List<Integer> integers : set) {
// System.out.println(integers);
}
}
public List<List<Integer>> subsets(int[] nums) {
if (nums == null || nums.length == 0){
List<Integer> list = new ArrayList<Integer>();
List<List<Integer>> result = new ArrayList<List<Integer>>();
result.add(list);
return result;
}
int arraySize = 1 << nums.length;
List<List<Integer>> result = new ArrayList<List<Integer>>(arraySize);
for (int i = 0; i < arraySize; i++){
// leetcode提交时，记得注释掉，打印比较费时间
System.out.println(Integer.toBinaryString(i));
// 用来存放当前选项下的结果集
List<Integer> list = new ArrayList<Integer>();
// 遍历数组
for (int j = 0; j < nums.length; j++){
// 找到要右移的位数; 假设为第一个数，则需要右移2位
int moveStep = nums.length - j - 1;
// 判断该bit是否为1，为1表示该数被选中
if (((i >> moveStep) & 1) == 1){
list.add(nums[j]);
}
}
// 打印本选项下的结果，leetcode提交时，记得注释掉，打印比较费时间
System.out.println("选中的子集为：" + list);
result.add(list);
}
return result;
}
}
执行结果如下：
0
选中的子集为：[]
1
选中的子集为：[3]
10
选中的子集为：[2]
11
选中的子集为：[2, 3]
100
选中的子集为：[1]
101
选中的子集为：[1, 3]
110
选中的子集为：[1, 2]
111
选中的子集为：[1, 2, 3]
小结
这个题还有很多其他思路，什么回溯之类的，鉴于我也还没搞懂，就先不写了（写不出来啊。。。）。
算法渣渣的算法之旅，希望能坚持下去！
腾讯云开发者
