位运算(3)_判定字符是否唯一_面试题
个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创位运算(3)_判定字符是否唯一_面试题
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
温馨提示:
1. 题目链接 :
2. 题目描述 :
3. 解法 :
解法一(哈希表):
算法思路 :
代码展示:
结果分析:
解法二(位图):
算法思路 :
代码展示:
结果分析:
温馨提示:
本文的算法题需要一些位运算知识的基础,如果大家还不是很了解的话,可以先去看下面的博客:
位运算(1)_常见位运算总结-CSDN博客
1. 题目链接 :
OJ链接: 判定字符是否唯一
2. 题目描述 :
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：
输入: s = "leetcode" 输出: false
示例 2：
输入: s = "abc" 输出: true
限制：
0 <= len(s) <= 100s[i]仅包含小写字母- 如果你不使用额外的数据结构，会很加分。
3. 解法 :
解法一(哈希表):
算法思路 :
1. 字符计数：
使用一个长度为 26 的整数数组 hash，用于记录每个字母出现的次数。数组的每个索引对应字母 'a' 到 'z'。
字母 'a' 的 ASCII 值是 97，'a' - 'a' 的结果是 0，因此可以用 ch - 'a' 的方式来映射字符到 hash 数组的索引。
2. 提前检查长度：在判断字符唯一性之前，首先检查字符串的长度。如果字符串的长度超过 26，则返回 false，因为英文字母只有 26 个，不可能有超过 26 个唯一字符。
3. 更新字符计数：遍历字符串 astr 中的每个字符，更新 hash 数组。对于每个字符 ch，通过 hash[ch - 'a']++来增加对应的计数。
4. 检查字符频率：再次遍历 hash 数组，检查每个索引的值。如果有任何一个索引的值大于 1，说明有重复的字符，返回 false。
如果所有的计数都不大于 1，则说明所有字符都是唯一的，返回 true。
代码展示:
class Solution {
public:bool isUnique(string astr) {int hash[26];if(astr.size() > 26) return false;for(auto ch : astr) hash[ch - 'a']++;for(int i = 0; i < 26; i++)if(hash[i] > 1) return false;return true;}
};
结果分析:
时间复杂度和空间复杂度
时间复杂度：O(n)，其中 n 是字符串 astr 的长度。需要遍历字符串一次来计数，另外再遍历一次 hash 数组来检查字符频率。
空间复杂度：O(1)，虽然使用了一个大小为 26 的数组来记录字符计数，但其大小是固定的，不随输入大小变化，因此是常数空间复杂度。
解法二(位图):
算法思路 :
利用[位图]的思想,每一个[比特位]代表一个[字符],一个int类型的变量的32位足够表示所有的小写字母.比特位里面如果是0,表示这个字符没有出现过.比特位里面的值是1,表示该字符出现过.
那么我们就可以用一个[整数]来充当[哈希表].
代码展示:
class Solution {
public:bool isUnique(string astr) {int bitmap = 0;if(astr.size() > 26) return false;for(auto ch : astr){int i = ch - 'a';//位运算如果你不知道优先级的话,能写尽写if((bitmap & (1 << i)) != 0) return false;bitmap |= (1 << i);}return true;}
};关键点分析:
1. 位图（bitmap）使用：bitmap 是一个整数，用于表示字符的出现情况。因为字符是小写字母 a - z，总共26个字母，可以用26个二进制位来表示。
每个字母对应一个二进制位，a 对应位 0，b 对应位 1，以此类推。
2. 字符串长度检查：if (astr.size() > 26) return false; 这一行代码确保了如果字符串的长度超过26，那么必定存在重复字符（因为只有26个小写字母）。
3. 位运算：int i = ch - 'a'; 计算出当前字符在字母表中的位置。
bitmap& (1 << i) 用于检查第 i 位是否已被设置。如果已设置（不等于0），表示该字符之前已经出现过，因此返回 false。
bitmap |= (1 << i); 将第 i 位设置为1，表示该字符已出现。
4. 返回结果：如果没有发现重复字符，则返回 true，表示所有字符都是唯一的。
结果分析:
时间复杂度和空间复杂度
时间复杂度：O(n)，其中 n 是字符串 astr 的长度。代码遍历字符串一次，进行位运算和条件判断。
空间复杂度：O(1)，因为 bitmap 是一个固定大小的整数，只占用常量空间。优点
高效性：使用位运算可以快速判断字符是否出现，并且时间复杂度为O(n)。
空间利用：只使用一个整型变量来保存所有字符的状态，节省了空间。