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

0x01.问题

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

《程序员面试金典》01.02

0x02.简要分析

这是一个简单的问题，解决的办法比较多，比如双循环呀，利用C++的STL呀，或者使用各种标志容器记录呀，这里给出一种标志容器的方法：

bool isUnique(string astr) {
    vector<int> map(26,0);
    for(char a:astr){
        if(map[a-'a']==0) map[a-'a']++;
        else return false;
    }
    return true;
}

时间的维度应该没得说了，但是空间的维度仍然有优化的余地。

我们使用的标志数组大小是26，我们要想优化，就必须有26个记录的点，但我们仔细想想，这26个数据中是不是都只使用了0或者1，其他的数字无意义，所以，我们可以考虑使用一个int类型的数据来存储这些0 1信息，一个int类型的数据是32位，完全足够存储这些信息，我们理清一下思路，我们需要的是利用这32位来记录这些信息，所以我们肯定要使用位运算，具体的思路如下：

• 初始化一个标志变量flag为0。
• 计算出每一个字符与‘a’的偏移量。
• 对数字1进行左移，左移的大小为偏移量。
• 这样我们就得到了一个只有相应位数上为1的二进制。
• 我们将这个左移后的数字与falg进行与操作。
• 这样，这个结果是否为0就由对应位数上的值是否为1决定，如果对应位数上不是1，说明这个字符是第一次操作，与操作的结果为0，此时将flag和偏移后的值进行或操作，就可以将对应位上的值置为1。
• 如果与操作结果不为0，说明之前这个位已经是1了，这个字符已经出现过，所以字符不唯一，直接返回false。

0x03.解决代码–位运算

 bool isUnique(string astr) {
    int flag=0;
    for(char a:astr){
        int m=a-'a';
        if((flag & (1 << m))==0) flag |= (1 << m);
        else return false;
    }
    return true;
}

ATFWUS --Writing By 2020–03–30