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

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

排序

class Solution {
public:
    bool isUnique(string astr) {
        sort(astr.begin(), astr.end());
        for(int i = 1; i < astr.size(); ++i)
            if(astr[i] == astr[i - 1])
                return false;
        return true;
    }
};

位运算

由题意，可能这个字符串所有字母是a~z之间，本来想到用一个26大小的数组来记录。但是可以通过一个26位的二进制中的每个位是否为1来表示这个位对应的字母是否出现过，由此就可以呃不用其他的数据结构

class Solution {
public:
    bool isUnique(string astr) {
        int a = 0;
        for(auto& ch : astr)
        {
            int i = ch - 'a';
            if(a & (1 << i)) // 如果a这个位为1，那么结果为1，表示重复了
                return false;
            else
                a |= 1 << i; // 记录这个位
        }
        return true;
    }
};