一.题目面试题 01.01. 判定字符是否唯一 - 力扣LeetCode二.思路关于这题有很多方法可以解决但是我们本章是位运算因此我们只用位运算进行讲解2.1 认识位图位图是一种非常高效的数据结构它的核心思想是利用二进制位来标记某个元素是否存在。与传统的数组不同数组每个元素通常占用4 字节如 int或1 字节如 char而位图只占用1 个比特位。也就是说1 字节可以记录 8 个元素的状态极大地节省了空间。在计算机中每个比特位只有0和1两种状态因此我们可以用0表示元素未出现用1表示元素已出现。这种紧凑的表示方式在处理大量“存在性”判断问题时非常有效。2.2 为什么可以使用位图本题限定字符集为小写字母一共只有26 个。这意味着我们只需要26 个比特位就能完整记录每个字符是否出现过。而在 C 中一个int 类型恰好占用32 位足够容纳这 26 个标记。因此我们完全可以用一个int 变量来充当位图而不必使用数组或哈希表。这样既节省了空间又能利用位运算进行快速操作。2.3 本题用的两个位运算公式在处理位图时我们需要两个核心操作检查某一位是否为 1和将某一位设置为 1。这两个操作可以通过位运算高效实现判断某一位是否为 1公式(n x) 1含义将数字n的二进制表示向右移动x位使第x位移动到最低位然后与1进行按位与运算。如果结果为1说明原第x位是1否则为0。 用途当我们要添加一个新字符时先检查该字符对应的位是否已经为1如果是则说明该字符重复出现可以直接返回结果。将某一位修改为 1公式n | (1 x)含义先将1左移x位得到只有第x位为1的数值然后与n进行按位或运算。由于或运算的特性n中其他位保持不变而第x位无论原来是0还是1都会变成1。 用途当一个新字符第一次出现时我们用它将该字符对应的位标记为已存在即把该位设为1这样后续就可以通过第一个公式来检查重复。三.代码演示class Solution { public: bool isUnique(string astr) { int b 0; int n astr.size(); //位图使用 for(int i 0;i n;i) { //获取元素 int ch astr[i] - a; //判断这个元素是否存在 if((b ch) 1) return false; //添加这个元素到位图 b | (1 ch); } return true; } };四.代码讲解一、初始化位图变量为了标记字符串中每个字符是否出现过我们使用一个整型变量b来充当位图。由于题目限定字符为小写字母共26个而int类型有32位足够容纳所有标记。初始时b的所有位都是0表示没有任何字符出现过。二、遍历字符串并操作接下来我们遍历字符串中的每一个字符。对于每个字符执行以下三个步骤计算字符对应的位偏移将当前字符astr[i]减去字符a得到一个0 到 25之间的整数ch这个整数就是该字符在位图中对应的比特位位置。检查该位是否已存在使用位运算公式(b ch) 1来判断位图中第ch位是否为1。如果结果为1说明该字符之前已经出现过即字符串中存在重复字符此时直接返回false。如果结果为0说明该字符是首次出现继续下一步。将该位标记为已存在使用位运算公式b | (1 ch)将位图中第ch位设置为1。这样后续再遇到相同字符时就能通过上一步检查出来。遍历结束后如果没有发现任何重复字符则返回true表示字符串中所有字符都是唯一的。三、关键细节位图的选择因为字符集只有小写字母所以用一个int变量就足够无需使用数组或哈希表既节省空间又提高效率。位运算的巧妙两个核心公式(b ch) 1和b | (1 ch)分别实现了查询和设置操作时间复杂度均为O(1)。字符映射通过astr[i] - a将字符映射到 0~25 的索引确保每个字符对应唯一的比特位。提前返回一旦发现重复立即返回false无需继续遍历提高效率。