位运算的惯用套路,都在这儿!(算法 NO.2)

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

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


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


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


16.png


题目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;    }}
目录
相关文章
|
3月前
|
算法
【算法】位运算算法——消失的两个数字(困难)
【算法】位运算算法——消失的两个数字(困难)
|
3月前
|
算法
【算法】位运算算法——只出现一次的数字Ⅱ
【算法】位运算算法——只出现一次的数字Ⅱ
|
3月前
|
算法
【算法】位运算算法——判断字符是否唯一
【算法】位运算算法——判断字符是否唯一
|
3月前
|
算法
【算法】位运算算法——两整数之和
【算法】位运算算法——两整数之和
|
3月前
|
算法
【算法】位运算算法——丢失的数字
【算法】位运算算法——丢失的数字
|
3月前
|
算法
算法】位运算——常见位运算基础操作总结
算法】位运算——常见位运算基础操作总结
算法】位运算——常见位运算基础操作总结
|
5月前
|
存储 自然语言处理 算法
位运算入门及简单算法题的应用
位运算入门及简单算法题的应用
45 1
|
5月前
|
算法 Java
Java数据结构与算法:位运算之位移操作
Java数据结构与算法:位运算之位移操作
|
5月前
|
算法 Java
Java数据结构与算法:位运算之与、或、异或运算
Java数据结构与算法:位运算之与、或、异或运算
|
6月前
|
算法 C++
c++算法学习笔记 (10) 位运算
c++算法学习笔记 (10) 位运算