算法实战：位运算与字符唯一性判断

算法实战：位运算与字符唯一性判断

在常见的位运算应用场景中，利用位图思想可以极大地优化空间复杂度。我们来看一个经典的面试题：如何判断一个字符串中的字符是否全部唯一。

问题背景

以 LeetCode 面试题 01.01 为例，要求根据所给字符串，判断其中的字符是否唯一。例如'leetcode'中存在重复的 'e'，不满足条件；而'abc'则每个字符均唯一。

核心思路

题目限定了字符串中均为小写字母，这意味着字符种类最多只有 26 种。我们可以利用一个整型变量作为位图，每一位代表一个字母是否出现过。

遍历字符串时，计算字符对应的偏移量（例如 'a' 对应 0，'b' 对应 1）。如果该位已经是 1，说明重复，直接返回 false；否则将该位置为 1。遍历结束后若未发现问题，则返回 true。

这种方法避免了使用额外的哈希表或数组，将空间复杂度降到了 O(1)，非常适合对内存敏感的场景。

代码实现

bool isUnique(string astr) {
    int checker = 0;
    for (char c : astr) {
        int val = c - 'a';
        // 检查第 val 位是否已为 1
        if ((checker & (1 << val)) > 0) return false;
        // 将第 val 位设为 1
        checker |= (1 << val);
    }
    return true;
}

注意这里使用了位与 & 和位或 | 操作来检查并设置状态。实际运行时会遇到大端序或小端序的问题吗？其实不用担心，因为整数在内存中的存储顺序不影响位运算的逻辑结果，只要编译器支持标准的移位操作即可。

其他解法

如果不允许修改输入字符串且不能使用额外空间，上述位图法是最佳选择。当然，也可以使用排序法（时间复杂度 O(n log n)）或者双重循环（O(n^2)），但在处理大规模数据时，位运算方案的性能优势非常明显。