题目描述

解题思路

1. 拿到题目的第一件事是判断题目的考察类型，可以看出来本题考查字符串内字符查重
2. 首先想到了使用map数据结构，遍历字符串中的每一个字符，如果存在第二次遍历，则返回false
3. 在此基础上考虑使用set数据结构，完美使用set不重复的特性
4. 题目中提到不使用额外的数据结构，因此考虑使用位运算解决

解题代码

• 使用map

class Solution {
public:
    bool isUnique(string astr) {
        map<char, bool> recoder;
        int length = astr.length();
        map<char, bool>::iterator iter;
        for (int i = 0; i < length; i++) {
            iter = recoder.find(astr[i]);
            // map中存在这个字符
            if (iter != recoder.end()) {
                return false;
            }
            else
            {
                recoder[astr[i]] = true;
            }
        }
        return true;
    }
};

• 使用set

class Solution {
public:
   bool isUnique(string astr) {
        set<char> recoder;
        int length = astr.length();
        set<char>::iterator iter;
        for (int i = 0; i < length; i++) {
            iter = recoder.find(astr[i]);
            // map中存在这个字符
            if (iter != recoder.end()) {
                return false;
            }
            else
            {
                recoder.emplace(astr[i]);
            }
        }
        return true;
    }
};

• 位运算

class Solution {
public:
  bool isUnique(string astr) {
    // 使用位运算解决【根据题中描述默认字符串中只会出现a-z 26个 小写字母】
    // 一个int类型的数据一般为4字节32bit 因此可以完全表示26个字母
        int mark = 0;//mark作为出现的记录
        for (int i = astr.length()-1; i >= 0; i--) {
            // 遍历字符串

            //首先计算需要位移的距离
            
            int move_bit = astr[i] - 'a';
            // 对1 进行左移 并进行与操作
            if ((mark & (1 << move_bit)) != 0) {
                // 之出现过 再次出现
                return false;
            }
            else {
                //没有出现过 
                mark = mark | (1 << move_bit);
            }
        }
        return true;
    }
};

沉淀

1. 位运算的基本操作