和算法渣一起练习–利用位运算，轻轻松松就能解决数学里的子集问题

• 2020 年 9 月 27 日
• 笔记
• 渣渣的算法之旅

前言

为什么要说算法？老实说，算法的重要性其实是毋庸置疑的，当然了，平时做CURD工作的时候，其实数据结构其实更重要一些，比如表的设计，以及部分场景下，比如秒杀这类，一般是需要在redis等内存中去维护一些数据结构，方便我们提升性能。

但基本来说，部分场景下，定下了数据结构，也就间接地定下了对应的算法；对于一个数组，要写一个算法，支持随机读取，就很简单；对于一个链表，要写一个算法，支持随机读取，那就得遍历。

个人觉得，算法和数据结构是一个并重的关系，数据结构的学习还是相对容易的，算法嘛，就，啊哈，你懂的。

毕业多年来，也曾经尝试过多次算法方面的学习，每次都是不了了之，我觉得，有可能是学习的方式不太对。以前看算法，要么拿本书在那看；要么弄不出来，就把答案找出来看一遍，看了就算完了，有时候呢，会把答案的代码debug一遍。

总的来说，学习效果真的太差了。

写这个系列（我也不知道能不能坚持，至少先开一个头），就是这么想的，学一个东西，不管是啥，不仅要有输入，也要有输出，输出是什么呢，就是把我觉得已经会了的东西，讲给大家听，大家能学到一点，我也高兴；学不到，那就倾听并改进。

也鼓励大家去输出，不管是笔记，脑图，还是博客，都是一个沉淀的方式，大家可以自由选择。

好了，大家就跟着我这个算法渣一起，学一点算法吧。

题目描述及解析

原题链接：//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表示选中。

上面的表格中，我们罗列了全部的组合，注意倒数第二列，我们使用二进制数来表达这个选项，比如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]

小结

这个题还有很多其他思路，什么回溯之类的，鉴于我也还没搞懂，就先不写了（写不出来啊。。。）。

算法渣渣的算法之旅，希望能坚持下去！