优选算法——位运算（1）：判定字符是否唯一
🔥近津薪荼： [个人主页]🎬个人专栏： 《近津薪荼的算法日迹》《Linux操作系统及网络基础知识分享》《c++基础知识详解》《c语言基础知识详解》✨不要物化，矮化，弱化，钝化自己，保持锋芒，不要停止学习这个世界上只有两个人真正在注意着你八岁的你，和八十岁的你，他们此刻正在注视着你，一个希望你 勇敢开始，一个希望你 不留遗憾
1.上期参考代码
classSolution{public:intfindMaxLength(vector<int>& nums){ unordered_map<int,int>hash; hash[0]=-1;int sum=0,ret=0;for(int i=0;i<nums.size();i++){if(!nums[i])nums[i]=-1; sum+=nums[i];if(hash.count(sum))ret=max(ret,i-hash[sum]);//判断sum是否存在else hash[sum]=i;}return ret;}};2.本期知识点导图
3.本期要讲解的题目是
判定字符是否唯一
要点：
- 只有小写字母
4.解题
4.1 使用数据结构
使用哈希表hash[26]来统计字母出现的次数。
4.2使用位图
什么是位图
当我们用数组模拟哈希表，只统计元素是否存在的时候，使用的及时位图的思想
概念：位图（BitMap）就是：用 1 个 bit（0/1）来表示某个数是否存在，用极小空间存大量整数的存在状态。
我们对每一个比特位0和1的修改，就可以统计较短数组中元素的存在与否。
优势：位图最大的价值是用极致的空间效率，实现对整数存在性的快速判断和操作
我们之前的算法已知都是强调时间复杂度，且由于空间资源变得越来越易获取，我们一度使用空间来换时间，但是这并不意味着空间就不重要，它同样很重要，特别是对于嵌入式开发，空间的资源还是很紧张的。
对于位图的使用，
常见的位运算
必不可少：
- 基础位运算操作符：<< >> & | ^
- 给一个数n，确定它的二进制中表示中的第x位是0还是1：(n>>x) & 1
- 将它的第x位改成1：n |=(1<<x)
- 将它的第x位改成0: n &= (~(1<<x))
- 提取二进制表示中的最右侧的1：n&(-n)
- 干掉二进制表示中的最右侧的1 ：n&（n-1）
- 异或的运算规律：
- a^a=0
- a^0=a
- a^ b^ = a ^ ( c^b)(交换律）
代码逻辑
- 使用位图
5.下期要讲解的题目是：
消失的两个数字
6.嗟食
如果小编写的内容对佬有帮助，还请大佬点点三连加关注哦
佬的支持就是我前进的最大动力~
期待与佬的再次相遇~
