LeetCode-题目详解：位运算

「爱情、让人受尽委屈。」 2023-10-03 09:58 35阅读 0赞

### 136. 只出现一次的数字 ###

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

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

示例 2:

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

--------------------

#### 方法一：位运算 ####

异或运算 ⊕。异或运算有以下三个性质：

1.  任何数和 00 做异或运算，结果仍然是原来的数，即 a⊕0=a。
2.  任何数和其自身做异或运算，结果是 00，即 a⊕a=0。
3.  异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]

class Solution:
        def singleNumber(self, nums: List[int]) -> int:
            result = nums[0]
            for i in range(1, len(nums)):
                result = result ^ nums[i]
    
            return result

class Solution:
        def singleNumber(self, nums: List[int]) -> int:
            return reduce(lambda x, y: x ^ y, nums)

### 剑指 Offer 56 - I. 数组中数字出现的次数 ###

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
    输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
    输出：[2,10] 或 [10,2]

限制：2 <= nums.length <= 10000

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]  
设 nums = \[3, 3, 4, 4, 1, 6\]，以上计算流程如下图所示:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]

class Solution:
        def singleNumbers(self, nums: List[int]) -> List[int]:
            x = 0   # 待寻找数1
            y = 0   # 待寻找数2
            n = 0   # 数组所有数异或结果
            m = 1   # 分组依据
    
            for num in nums:         # 1. 遍历异或
                n ^= num
            
            while n & m == 0:        # 2. 寻找 n 中的1的最低位，记录于m中
                m <<= 1       
            
            print("m = ", m)
    
            for num in nums:         # 3. 遍历 nums 分组
                if num & m == 0:     # 4. 当 num & m == 0，num属于一组
                    x ^= num 
                else:                # 4. 当 num & m != 0，num属于二组
                    y ^= num       
            
            return x, y              # 5. 返回出现一次的数字

### 137. 只出现一次的数字 II ###

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 1：

输入：nums = [2,2,3,2]
    输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
    输出：99

提示：

*  1 <= nums.length <=  3 ∗ 1 0 4 3 \* 10^4 3∗104
 *  \- 2 31 < = n u m s \[ i \] < = 2 31 − 1 2^\{31\} <= nums\[i\] <= 2^\{31\} - 1 231<=nums\[i\]<=231−1
 *  nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

--------------------

### 191. 位1的个数 ###

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

提示：

*  请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。  
    在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：00000000000000000000000000001011
    输出：3
    解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：00000000000000000000000010000000
    输出：1
    解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：11111111111111111111111111111101
    输出：31
    解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

*  输入必须是长度为 32 的 二进制串 。

进阶：

*  如果多次调用这个函数，你将如何优化你的算法？

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmluamF3ZWk_size_20_color_FFFFFF_t_70_g_se_x_16]

class Solution:
        def hammingWeight(self, n: int) -> int:
            result = 0
            while n:
                result += n & 1
                n = n >> 1
            return result

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210703162017716.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210703163107239.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/202107031633053.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210703163042534.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmluamF3ZWk_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/147cdeed1c4a4fa382fb8baf29d008f0.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAbmluamF3ZWk=,size_20,color_FFFFFF,t_70,g_se,x_16