【位运算】--- 初阶题目赏析
Welcome to 9ilk's Code World
(๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏： 算法Journey
根据上一篇位运算的总结，我们来体会几道初阶题目。
🏠 判定字符是否唯一
📌 题目解析
判定字符是否唯一
- s[i]中只包含小写字母。
📌 算法原理
✏️ 思路一:哈希表
利用哈希表对小写字母进行映射,如果遍历过程中出现已经映射的直接返回false,若遍历完之后都没有出现映射两次的则返回true。
时间复杂度：O（N）
空间复杂度：O（N）
class Solution {
public:
bool isUnique(string astr)
{
bool flag = true;
int arr[27] = { 0 };//数组模拟哈希表
for (int i = 0; i < astr.size(); i++)
{
char ch = astr[i];
int pos = ch - 'a' + 1;
arr[pos] ^= pos;
if (!arr[pos])
{
flag = false;
break;
}
}
return flag;
}
};✏️ 思路二:位图思想
一个int有4个字节，也就是有32个bit。我们这里都是小写字母，只需要利用26个bit位进行映射就能判断是否出现过。利用位运算判断映射位置是否为1，为1则出现过返回false；为0则没出现过，将该位设置为1。
优化： 抽屉原理
桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的"抽屉原理"。抽屉原理的一般含义为:"如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到到n个集合中去,其中必定有一个集合里至少有两个元素。"抽屉原理有时也被称为鸽巢原理。
由此我们可以得到,当字符串长度大于26时,一定会出现重复,字符串长度相当于抽屉,字符相当于苹果!
class Solution {
public:
bool isUnique(string astr)
{
if(astr.size()>26) //抽屉原理
return false;
int bitset = 0;
for(auto& e : astr )
{
int pos = e - 'a';
if((bitset >> pos )&1) //判断该位是否为1
return false;
bitset |= (1 << pos);//设置为1
}
return true;
}
};🏠 丢失的数字
📌 题目解析
丢失的数字
📌 算法原理
✏️ 思路一 : 高斯求和公式
知道了数组长度n,则原本数字总个数应该为n+1个.遍历一遍数组求和sum,由于高斯求和公式(等差数列公式),则我们可以求原本未缺失数字时的总和,减去sum就是缺失的数字。
参考代码：
class Solution {
public:
int missingNumber(vector<int>& nums)
{
int size = nums.size() + 1;
int count = (size*(size - 1)) / 2;
cout << count <<endl;
int sum = 0;
for(auto e :nums)
{
sum += e;
}
return count - sum;
}
};✏️ 思路二 : 异或运算
我们知道异或其中两条运算律是a^a=0和结合率,因此我们遍历一遍原来的数字,再遍历一遍缺失数组,最后得到的数就是缺失的数字,因为未缺失的在两次过程相当于出现两次,也就是会异或为0,最后只剩缺失的没有配对.
参考代码:
class Solution {
public:
int missingNumber(vector<int>& nums)
{ //思路：我们先将范围内的数异或再异或数组每一个数 最后得到的就是丢失的
int ret = 0;
int n = nums.size();
for(int i = 0 ; i <= n ; i++)
{
ret ^= i;
}
for(const auto& e : nums)
{
ret ^= e;
}
return ret;
}
};🏠 两整数之和
📌 题目解析
两整数之和
📌 算法原理
我们前面说过按位与本质上是无进位相加。那多出来的进位信息在哪呢？其实按位与就能保存进位信息。那是因为如果两个数某个位上的数字都是1话，就需要进位，此时按位与得到的还是1，而如果两个数中有一位是0的话按位与就是0，因此通过按位与能很好的知道那一位进位，那一位不进位。
注：由于仅仅一次按位与只是提取到进位信息，重要的是不断地将进位信息用完，直到进位信息为0(进位信息用完)。因此我们需要不断地用进位信息进行无进位相加直到用完进位信息。同时要注意在进位的过程中也会产生进位。
参考代码：
class Solution {
public:
int getSum(int a, int b)
{
int next = (a & b) << 1; //进位信息 按位与之后再左移一位才是进位信息 因为进的位是给下一位的
int ret = a ^ b;//无进位相加
while (next)
{
int del = next;
next = (next & ret) << 1;
ret ^= del; //用进位信息进行无进位相加
}
return ret;
}
};完。