位运算的惯用套路，都在这儿！（算法 NO.2）-轻识

本文所列题目来自 LeetCode 中国网站，属于算法面试中关于位运算的经典高频考题。题解由 Doocs 开源社区 leetcode 项目维护者提供。

目前已经有超过 50 位开发者参与了此项目，期待你的加入！

项目地址：https://github.com/doocs/leetcode

题目1

题目描述

一个整型数组 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 <= 10000

解法

异或运算求解。

首先明确，两个相同的数异或之后的结果为 0。对该数组所有元素进行异或运算，结果就是两个只出现一次的数字异或的结果。找出这个结果中某个二进制位为 1 的位置，之后对数组所有元素进行分类，二进制位为 0 的异或到 a，二进制位为 1 的异或到 b，结果就是 a，b。

Python3

class Solution:    def singleNumbers(self, nums: List[int]) -> List[int]:        xor_res = 0        for num in nums:            xor_res ^= num        pos = 0        while (xor_res & 1) == 0:            pos += 1            xor_res >>= 1        a = b = 0        for num in nums:            t = num >> pos            if (t & 1) == 0:                a ^= num            else:                b ^= num        return [a, b]

Java

class Solution {    public int[] singleNumbers(int[] nums) {        int xor = 0;        for (int num : nums) {            xor ^= num;        }        int pos = 0;        while ((xor & 1) == 0) {            ++pos;            xor >>= 1;        }        int a = 0, b = 0;        for (int num : nums) {            int t = num >> pos;            if ((t & 1) == 0) {                a ^= num;            } else {                b ^= num;            }        }        return new int[] {a, b};    }}

题目2

题目描述

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

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

示例 2：

输入：nums = [9,1,7,9,7,9,7]输出：1

限制：

•1 <= nums.length <= 10000•1 <= nums[i] < 2^31

解法

统计所有数字每个位中 1 出现的次数，对于某个位，1 出现的次数一定是 3 的倍数 +1 或 0。对这个数 %3 得到的结果就是那个出现一次的数字在该位上的值。

Python3

class Solution:    def singleNumber(self, nums: List[int]) -> int:        bits = [0 for _ in range(32)]        for num in nums:            for i in range(32):                bits[i] += (num & 1)                num >>= 1        res = 0        for i in range(32):            if bits[i] % 3 == 1:                res += (1 << i)        return res

Java

class Solution {    public int singleNumber(int[] nums) {        int[] bits = new int[32];        for (int num : nums) {            for (int i = 0; i < 32; ++i) {                bits[i] += (num & 1);                num >>= 1;            }        }        int res = 0;        for (int i = 0; i < 32; ++i) {            if (bits[i] % 3 == 1) {                res += (1 << i);            }        }        return res;    }}

题目3

题目描述

集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1:

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

注意:

1.给定数组的长度范围是[2, 10000]。2.给定的数组是无序的。

解法

首先使用 1 到 n 的所有数字做异或运算，然后再与数组中的所有数字异或，得到的值就是缺失数字与重复的数字异或的结果。

接着计算中这个值中其中一个非零的位 pos。然后 pos 位是否为 1，将 nums 数组的元素分成两部分，分别异或；接着将 1~n 的元素也分成两部分，分别异或。得到的两部分结果分别为 a,b，即是缺失数字与重复数字。

最后判断数组中是否存在 a 或 b，若存在 a，说明重复数字是 a，返回 [a,b]，否则返回 [b,a]。

Python3

class Solution:    def findErrorNums(self, nums: List[int]) -> List[int]:        res = 0        for num in nums:            res ^= num        for i in range(1, len(nums) + 1):            res ^= i        pos = 0        while (res & 1) == 0:            res >>= 1            pos += 1        a = b = 0        for num in nums:            if ((num >> pos) & 1) == 0:                a ^= num            else:                b ^= num        for i in range(1, len(nums) + 1):            if ((i >> pos) & 1) == 0:                a ^= i            else:                b ^= i        for num in nums:            if num == a:                return [a, b]        return [b, a]

Java

class Solution {    public int[] findErrorNums(int[] nums) {        int res = 0;        for (int num : nums) {            res ^= num;        }        for (int i = 1, n = nums.length; i < n + 1; ++i) {            res ^= i;        }        int pos = 0;        while ((res & 1) == 0) {            res >>= 1;            ++pos;        }        int a = 0, b = 0;        for (int num : nums) {            if (((num >> pos) & 1) == 0) {                a ^= num;            } else {                b ^= num;            }        }        for (int i = 1, n = nums.length; i < n + 1; ++i) {            if (((i >> pos) & 1) == 0) {                a ^= i;            } else {                b ^= i;            }        }        for (int num : nums) {            if (num == a) {                return new int[]{a, b};            }        }        return new int[]{b, a};    }}

题目4

题目描述

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

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

示例 2：

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

示例 3：

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

解法

n & (n - 1) 会消除 n 中最后一位中的 1。

Python3

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

Java

public class Solution {    // you need to treat n as an unsigned value    public int hammingWeight(int n) {        int res = 0;        while (n != 0) {            n &= (n - 1);            ++res;        }        return res;    }}

长按识别下图二维码，关注公众号「Doocs开源社区」，第一时间跟你们分享好玩、实用的技术文章与业内最新资讯。