算法专题五:位运算
2024-01-01 16:03:05
算法专题五:位运算
一.常见位运算总结:
1.位1的个数
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
for(int i=0;i<32;i++)
{
if((n>>i)&1)
count++;
//按位与& 有0就是0
//按位或| 有1就是1
//按位异或^ 相同为0相异为1
}
return count;
}
};
2.比特位记数
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans(n+1);
//1.考虑一趟扫描!
int hightbit = 0;
for(int i=1;i<=n;i++)
{
//1.判断是否需要更新数据:
if((i&(i-1)) == 0)
{
hightbit = i;
}
ans[i] = ans[i - hightbit]+1;
}
return ans;
}
};
3.汉明距离
1.通过提出每一位然后于1按位与提出x或者y的每一位数值。
2.进行判断是否相等不相等就count++;
class Solution {
public:
int hammingDistance(int x, int y) {
int count = 0;
for(int i=0 ; i<32 ; i++)
{
if (((x>>i) & 1) != ((y>>i) & 1))
count++;
}
return count;
}
};
4.只出现一次的数字
1.一组数按位在一起按照题目意思只有一个数只有自己。
2.其他数值都是一对一对。
3.两个相同的数按位异或在一起结果是0
4.0和所有数按位异或在一起结果为那个数本身。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int value = 0;
for(auto num:nums)
{
value^=num;
}
return value;
}
};
5.只出现一次的数字三
1.考虑特殊情况数组中只有两个元素直接返回这个数组。
2.排序:相同的数值一定相邻并且数组元素的个数为偶数。
3-1:特殊的两个数是相邻的–>指针移动长度
3-2:特殊的两个数是不是相邻的–>指针移动长度和边界控制问题!
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
//0.特殊情况:
int n = nums.size();
if(n==2)
return nums;
//1.排序
sort(nums.begin(),nums.end());
//2.创建双指针分析各种情况解决方案:
int left = 0;
int right = 1;
vector<int> vv ;
while(left<n && right<=n)
{
//情况1: 1 1 2 3 3 4 4 5
if(right == n)
{
vv.push_back(nums[left]);
break;
}
if(nums[left]==nums[right])
{
left+=2;
right+=2;
}
else
{
vv.push_back(nums[left]);
left+=1;
right+=1;
}
}
return vv;
}
};
二.判断字符是否为一
1.思路一:位运算思路
class Solution {
public:
bool isUnique(string astr) {
int n = astr.size();
if(n > 26)
return false;
int bitmap = 0;
for(auto ch : astr)
{
int count = ch - 'a';
if(((bitmap>>count) & 1) == 1)
return false;
bitmap |= (1<<count);
}
return true;
}
};
GIF题目解析
三.丢失的数字
1.思路一:暴力思路
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
if(n == 1)
{
if(nums[0] == 1) return 0;
if(nums[0] == 0) return 1;
}
//1.排序:
sort(nums.begin() , nums.end());
//2.遍历找数:
for(int i=0 ; i < n ; i++)
{
if(i != nums[i])
return i;
}
return n;
}
};
//时间复杂度 1.排序:n*long^n 2. 遍历o(n)
//空间复杂度 O(1)
2.思路二:高斯求和思路:
class Solution {
public:
int missingNumber(vector<int>& nums) {
//1.求数组个数:
int n = nums.size();
//2.求从0到n的和
long long sum_1 = ((0+n)*(n+1))/2;
//3.遍历数组求和
long long sum_2 = 0;
for(auto num : nums)
{
sum_2 += num;
}
//4.计算结果:
return (sum_1 - sum_2);
}
};
//1.时间复杂度:O(n)
//2.空间复杂度为:O(1)
3.思路三:哈希思路
class Solution {
public:
int missingNumber(vector<int>& nums) {
//1.计算数组长度:
int n = nums.size();
//2.开一个哈希表
vector<int> hash(n+1);
//3.遍历数组第一遍给hash赋值:
for(auto num_1 : nums)
{
hash[num_1]++;
}
//4.遍历hash第一遍判断没有的返回出来:
for(int i=0 ; i < n+1 ;i++)
{
if (hash[i] == 0)
return i;
}
//照顾leetcode
return 0;
}
};
//时间复杂度:O(n)
//空间复杂度:O(n)
4.思路四:位运算思路优化
class Solution {
public:
int missingNumber(vector<int>& nums) {
//1.计算长度
int n = nums.size();
//2.异或所有数据:
int ret = 0;
for(int i=0 ; i<n ; i++)
{
ret^=nums[i];
}
for(int i=0 ; i<=n ;i++)
{
ret^=i;
}
return ret;
}
};
//时间复杂度:O(n)
//空间复杂度:O(1)
四.两整数之和
1.思路一:按位异或+无进位相加
class Solution {
public:
int getSum(int a, int b) {
while(((a&b)<<1)!=0)
{
//0.保存数据
int tmp = a;
//1.a的更新:
tmp = a^b;
//2.b的更新
b = ((a&b)<<1);
//3.数据归还
a = tmp;
}
return a^b;
}
};
五.只出现一次的数字二
1.思路一:暴力思路+排序
class Solution {
public:
int singleNumber(vector<int>& nums) {
if(nums.size()==1)
return nums[0];
//1.排序
sort(nums.begin(),nums.end());
//2.三指针遍历数据:
int l = 0;
int m = 1;
int r = 2;
while(l < nums.size())
{
if( m >= nums.size() && r >= nums.size())
{
return nums[l];
}
if(nums[m] == nums[r] && nums[m] != nums[l])
{
return nums[l];
}
else
{
l+=3;
m+=3;
r+=3;
}
}
return 0;
}
};
2.思路二:异或思路:
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for(int i=0;i<32;i++)
{
int sum = 0;
for(int x:nums)
{
if(((x>>i)&1) == 1)
sum++;
}
//推广到只出现n次的数组!
sum%=3;//3改变为n
if(sum == 1) ret |= (1<<i);
}
return ret;
}
};
//时间复杂度是:O(n)
//空间复杂度是:O(1)
六.消失的两个数字
1.思路一
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
//1.异或所有数值:
int tmp = 0;
for(auto num:nums) tmp^=num;
for(int i=1 ; i<=nums.size()+2 ; i++) tmp ^=i;
//2.tmp==a^b;找出a,b中比特位不同的哪一位
int diff = 0;
while(1)
{
if(((tmp>>diff)&1) == 1) break;
else diff++;
}
//3.根据diff位置的不同把所有数据划分为两类去处理
int a = 0 , b = 0;
for(int x:nums)
if(((x>>diff) & 1) ==1 ) b^=x;
else a^=x;
for(int i=1;i<=nums.size()+2;i++)
if(((i>>diff)&1) == 1) b^=i;
else a^=i;
return {a,b};
}
};
文章来源:https://blog.csdn.net/2201_75943325/article/details/135322177
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!