L56.【LeetCode题解】位运算习题集1(只出现一次的数字 III、判定字符是否唯一、两整数之和)-CSDN博客

1.知识回顾

参见CC55.【C++ Cont】位运算的最终总结(含比特位计数、汉明距离)文章

2.只出现一次的数字 III

https://leetcode.cn/problems/single-number-iii/description/

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。
示例 2：
输入：nums = [-1,0]
输出：[-1,0]
示例 3：
输入：nums = [0,1]
输出：[1,0]
提示：

2 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次

分析

以nums = [1,2,1,3,2,5]为例分析,

1^2^1^3^2^5==(1^1)^(2^2)^(3^5)==3^5,那就要分析如何将3和5从数组中提取出来

1.恰好有两个元素只出现一次的含义

说明两个数字a和b一定不同,必然异或的结果一定含1

unsigned int res=0;
for (auto a:nums)
    res^=a;

2.找出异或结果含1的是第几位

可能异或的结果含多个1,这里只使用其中一个1,使用lowbit算法:提取最右侧的1

unsigned int classify_num=res & (-res);

classify_num为下面分组的依据

3.分两组

要求数字a和b要分到两个不同的组中,显然使用classify_num分组,各组内做运算,最后留下的肯定是a和b

unsigned int group1=0,group2=0;
for (auto a:nums)  
{
    if (a&classify_num)
        group1^=a;
    else
        group2^=a;
}

4.尾插分组运算后的结果

vector<int> ret;
ret.push_back(group1);
ret.push_back(group2);

代码

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) 
    {
        unsigned int res=0;
        for (auto a:nums)
            res^=a;
        unsigned int classify_num=res & (-res);  
        unsigned int group1=0,group2=0;
        for (auto a:nums)  
        {
            if (a&classify_num)
                group1^=a;
            else
                group2^=a;
        }
        vector<int> ret;
        ret.push_back(group1);
        ret.push_back(group2);
        return ret;
    }
};

注意要使用unsigned int存储,如果使用int会报错

因为n&(-n)中的-n会溢出,‌int类型存储范围为-2,147,483,648到2,147,483,647

-(-2,147,483,648)为2,147,483,648>2,147,483,647

提交结果

3.判定字符是否唯一

https://leetcode.cn/problems/is-unique-lcci/description/

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：
输入: s = "leetcode"
输出: false 
示例 2：
输入: s = "abc"
输出: true
限制：

0 <= len(s) <= 100
s[i]仅包含小写字母
如果你不使用额外的数据结构，会很加分。

分析

方法1:查表

发现s[i]仅包含小写字母'a'~'z',因此不用真的创建哈希表,可以使用哈希数组

遍历字符串,将字符串的出现次数存入数组中,之后遍历数组,如果元素代值大于1,返回false;如果全部小于等于1,返回true

class Solution {
public:
    bool isUnique(string astr) 
    {
        int arr[26];//26个小写字母,从'a'~'z'
        for (auto a:astr)
            arr[a-'a']++;
        for (auto b:arr)
        {
            if (b>1)
                return false;
        }
        return true;
    }
};

提交结果:

或者将次数存入数组的过程中,检查次数是否大于1,如果大于返回false

class Solution {
public:
    bool isUnique(string astr) 
    {
        int arr[26];
        for (auto a:astr)
        {
            arr[a-'a']++;
            if (arr[a-'a']>1)
                return false;
        }
        return true;
    }
};

提交结果:

方法2:位图

之前在CC55.【C++ Cont】位运算的最终总结(含比特位计数、汉明距离)提到过位图的思想,即使用比特位来存储信息,s[i]仅包含小写字母'a'~'z',一共26个,可以使用一个int类型的变量val来存储,

对于字符变量ch,其对应val的第ch-'a'位,值表示字符的出现次数(0表示没有出现过,1表示出现过),如果第ch-'a'位为0,就将第ch-'a'位置为1;如果第ch-'a'位为1,即之前已经出现过,重复出现返回false

修改第i位为1的方法

val |= 1<<i;

查看第i位是0还是1的方法

第i位为 (val>>i) & 1

代码

class Solution {
public:
    bool isUnique(string astr) 
    {
        int val=0;
        for (auto ch:astr)
        {
            if ((val>>(ch-'a')) & 1)//第ch-'a'位如果为1
                return false;
            val|=1<<(ch-'a');
        }
        return true;
    }
};

提交结果:

方法2改进:使用鸽巢原理

当字符串的字符个数大于26时,则字符串中至少有两个字符是相等的,直接返回false,用不上位图

(鸽巢原理参见L37.【LeetCode题解】快乐数(双指针思想)文章)

提交结果:

4.两整数之和

https://leetcode.cn/problems/sum-of-two-integers/description/

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

示例 1：
输入：a = 1, b = 2
输出：3
示例 2：
输入：a = 2, b = 3
输出：5
提示：

-1000 <= a, b <= 1000

分析

此题考察加法的原理,如果学过数字电路的话,其实和加法器有关系.

(全加器, $C_{in}$ 代表输入进位, $C_{out}$ 代表输出进位,图片来自https://www.build-electronic-circuits.com/full-adder/)

发现和两个逻辑门有关系:

异或门、与门

则对于二进制位a和b,有以下运算表

a	b	XOR	AND	ADD
0	0	0	0	00
0	1	1	0	01
1	0	1	0	01
1	1	0	1	10

异或又叫无进位相加,而与运算后左移移位的结果可以存储进位

不断让无进位相加的结果和进位异或,直到进位为0,就能得出加法的值

循环中止条件:进位为0

class Solution {
public:
    int getSum(int a, int b) 
    {
        while(b)
        {
            int tmp1=a^b;
            int tmp2=(a&b)<<1;
            a=tmp1;
            b=tmp2;
        }
       return a;
    }
};

提交结果:

注意: -1000 <= a, b <= 1000不存在移位溢出的情况,因此不需要将移位后的结果强转为unsigned int

如果a和b在int范围内取,那就要考虑移位溢出的情况

a            = 0111 1111 1111 1111 1111 1111 1111 1111  最高位为0
b            = 0111 1111 1111 1111 1111 1111 1111 1111  最高位为0
a & b        = 0111 1111 1111 1111 1111 1111 1111 1111  最高位为0
(a & b) << 1 = 1111 1111 1111 1111 1111 1111 1111 1110  此时就是溢出了,最高位为1,变成负数

稍微修改下代码即可:

class Solution {
public:
    int getSum(int a, int b) 
    {
        while(b)
        {
            int tmp1=a^b;
            int tmp2=(unsigned int)((a&b)<<1);
            a=tmp1;
            b=tmp2;
        }
       return a;
    }
};