LeetCode题解——位运算

发表于 | | 阅读次数:
字数统计: 765

JavaScript解答LeetCode，位运算分类。陆续更新。

78 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

关于使用位运算来解：
首先，先理解用位串来表示子集。
如题目中的，nums=[1,2,3]，我们可以用三位二进制数来表示它的子集：

二进制位串 对应子集
00000 000 []
00000 001 [1]
00000 010 [2]
00000 011 [1,2]
00000 100 [3]
00000 101 [1,3]
00000 110 [2,3]
00000 111 [1,2,3]

这里的空格没有什么啥意思，就是为了看起来比较方便。【因为一般存储8位，我们这里只用了三位怕看不清楚。
那么我们在计算机中如何存储这些二进制位串呢，我们可以用直接用十进制数字表示，比如1-8.
可以看出来，每一位代表了一个集合的元素。也就是说，我们只要比较1-8的8个数字中哪些位为1，就可以知道这个子集是什么了。
所以解答为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var subsets = function(nums)
{
    var list=[];  //定义结果数组
    var n=nums.length;      //n存储集合长度
    var l=Math.pow(2,n);    //用1-l期间的数的二进制表示的位串，来表示该全集所有的子集
    
    var array=[];//这里设置array作为子集的元素，因为结果数组的元素还是数组
    for(let i=1;i<l;i++)    //总共有l个子集
    {
        for(let j=0;j<n;j++)    //每个子集的二进制位串有几位有效数字
        {
            if((1<<j)&i)    //查看i的哪些位为1
            {
                array.push(nums[j]);    //i为1的位对应的元素加入子集
                list[i]=array;          
            }
        }
        array=[];
    }

    return list;
}

参考文章：
LeetCode 每日一题 78. 子集

136 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例1：

1
2
输入：[2,2,1]
输出：1

示例2：

1
2
输入：[4,1,2,1,2]
输出：4

这里我们主要使用异或的方法来进行查找。
异或运算法则：

  1. a ⊕ a = 0 ；0⊕a=a；
  2. a ⊕ b = b ⊕ a；
  3. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c；

第一条可以看出来，只要出现两次的元素，进行异或可以使其结果为0。【题目中的条件粗体标出来了】
所以举例来说：
[4,1,2,1,2]这个数组，我们对它进行全部异或运算。
即

1
2
3
    4⊕1⊕2⊕1⊕2
= 4⊕（1⊕1）⊕（2⊕2）
=4

所以对于这一题，我们只要让数组内所有的元素都进行异或运算就可以得出只出现一次的数字。

解决方案：

1
2
3
4
5
6
7
8
9
var singleNumber = function(nums) 
{
    var n=0;
    for(let i=0;i<nums.length;i++)
    {
        n ^=nums[i];
    }
    return n;
};

0%