当前位置：首页 > article >正文

位运算_判定字符是否唯一

article 2024/11/14 3:48:37

面试题 01.01. 判定字符是否唯一

判断字符串是否有重复的字符

1.我们可以用哈希表，没有就插入，有就false。

2.因为只有小写字母最多26种，可以用数组来代替

3.因为不需要统计出现的次数，只关心是否存在，并且<48。我们可以用位图的思想，每一个bit位代表是否出现过，出现置1。

4.因为只有小写字母最多26种，如果字符串字符数>26说明必定有重复的。

class Solution {
public:
    bool isUnique(string astr) {
        //字符数>26 一定有重复的
        if(astr.size()>26) return false;
        int map=0;
        for(auto &o:astr)
        {
            //找映射位置
            int i=o-97;//'a'==97
            //查看是否出现过
            if((map>>i)&1) return false;
            //没有出现过就置1
            else map|=(1<<i);
        }
        return true;
    }
};

268. 丢失的数字

找出0~n中缺失的一个数

1.先用求和公式算出0~n所有数的和，再减去数组中数的和，剩下的就是缺失的数。
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n=nums.size();
        int sum=(0+n)*(n+1)/2;//求和公式 (首项+末项)(项数)/2
        for(auto&o:nums)
            sum-=o;
        return sum;
    }
};
2.位运算。a^0=a a^a=0

0~n和数组的数异或剩下的数就是缺失的数
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (int i=1;i<=n;i++)
            sum ^= i;
        for (auto& o : nums)
            sum ^= o;
        return sum;
    }
};

371. 两整数之和

1.a^b 无进位相加

0 1为1 0 0为0 1 1为0 和二进制满2进1一样
  0101  (a = 5)
^ 0011  (b = 3)
------
  0110  (结果 = 6)
2.a&b 计算进位

全1为1 a&b算出来的数因为是在当前位置变1 左移一位<<1才是实际的进位

class Solution {
public:
    int getSum(int a, int b) {
        while(b!=0)
        {
            int x=a^b;//无进位相加
            int carry=(a&b)<<1;//进位
            a=x;
            b=carry;
        }
        return a;
    }
};

137. 只出现一次的数字 II

数组只有一个数是单个的，其它都是3个3个成对的

如果是3个相同的数，它们bit位肯定都相同。把它们第n个bit位上的数相加，再把该数%3结果肯定为0，因为bit位不是1就是0。

所有把数组每个数对应bit位上的数相加%3，余下的数就是单个数的bit位大小
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int re = 0;
        for (int j = 0; j < 32; j++) {
            int sum=0;
            //数组每个bit位之和
            for (auto& o : nums)
                sum += (o >> j) & 1;
            //%3有1置1 
            if (sum % 3)
                re |= (1 << j);
            else
                re &= ~(1 << j);
        }
        return re;
    }
};