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

一、题目描述

二、解题思路

整体思路

由于向量中只包含小写字母(最多26种)，且希望不使用额外的数据结构，所以我们可以用位运算(位图)的思想来解决这个问题。

具体思路

(1)首先，依据鸽巢原理我们可以对算法进行优化，由于均为小写字母，所以，当字符串的长度大于26时，一定存在字母重复，返回false;

(2)定义bitmap变量，在C++中，int占4个字节，32位，我们可以用其中的32位来记录字符出现的次数，为了从0开始计数，我们计算r-'a'，即偏移量来对应编号；

(3)如果bitmap&(1<<r)为1，代表字母已经出现了一次，返回false。否则，则bitmap|=(1<<r)，将位图中的对应二进制位修改成1;

三、代码实现

时间复杂度：T(n)=O(n)

空间复杂度：S(n)=O(1)

class Solution {
public:bool isUnique(string astr) {//鸽巢原理优化if(astr.size()>26) return false;//位图int bitmap=0;for(auto x:astr){int r=x-'a';if(bitmap&(1<<r)) return false;else bitmap|=(1<<r);}return true;}
};