面试金典0101 判定字符是否唯一

题目：判定字符是否唯一

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

  # 样例1
  输入: s = "leetcode"
  输出: false
      
  # 样例2
  输入: s = "abc"
  输出: true

解题方法：

1. 用哈希表unordered_map，记录目前为止出现的字符
2. 用bool数组来完成记录功能（桶计数）
3. 用位运算代替bool数组的记录功能

以上三种算法的时间复杂度均为\(O(n)\)，差别在于空间利用的大小，其实量级也都是\(O(1)\)，但是实际利用的比特数不同

解法一：

用到了C++ std中的unordered_map类，需要注意如何插入和查找

class Solution {
public:
    bool isUnique(string astr) {
        unordered_map<char, bool> map;
        unordered_map<char, bool>::iterator it;
        bool flag = true;
        for(int i=0; i<astr.size(); ++i)
        {
            if((it = map.find(astr[i])) != map.end()) // delete 'it' will get the same result.
            {
                flag = false;
                break;
            }
            map.insert(make_pair(astr[i], true));
        }
        return flag;
        // 赋值语句返回值为所赋的值，这也是连等的合法性
        // int a=3, b=2;
        // if((a=2) == b)
        // {
        //     cout << (a = b = 3) << endl;
        // }
    }
};

解法二：

ASCII码表原本是只有128个字符的（对应7bits的空间 \(2^7=128\)），但为了有更多的字符而扩充到了256个字符（对应8bits空间 \(2^8=256\)）

class Solution {
public:
    bool isUnique(string astr) {
        bool A[256]; // record; ASCII augmentation includes 256 characters
        bool flag = true;
        memset(A, false, sizeof(A));
        for(int i=0; i<astr.size(); ++i)
        {
            if(!A[int(astr[i])]) // current character has not appeared
            {
                A[int(astr[i])] = true;
            }
            else
            {
                flag = false;
                break;
            }
        }
        return flag;
    }
};

解法三：

解题参考 注意原作者只考虑小写字母的情况，如果是整个ASCII表的话，有128个字符，需要两个long int型来存储（32位机上int型是4字节32bits，long int是8字节64bits），每部分的逻辑一样，只是外层加入是否大于64而已

class Solution {
public:
    bool isUnique(string astr) {
        long int left = 0, right = 0; // noticed 'left' should be equal to 0
        bool flag = true;
        for(int i=0; i<astr.size(); ++i)
        {
            int cur_num = int(astr[i]);
            if(cur_num >= 64)
            {
                long int cur = long(1) << (cur_num - 64); // noticed '1' should be the type of 'long int'
                if((left & cur) == 0) // noticed the priority of the '&' and '=='
                {
                    left = left | cur;
                }
                else
                {
                    flag = false;
                    break;
                }
            }
            else
            {
                long int cur = long(1) << cur_num;
                if((right & cur) == 0) // noticed the priority of the '&' and '=='
                {
                    right = right | cur;
                }
                else
                {
                    flag = false;
                    break;
                }
            }
            
        }
        return flag;
    }
};