关于位运算那点事儿(⊙o⊙)

• • 前言
  • 第一题 [蓝桥杯 2013 省] 买不到的数目
  • • 题目描述
    • 解题报告
    • 参考代码(C++版本)
  • 第二题 P3951 [NOIP2017 提高组] 小凯的疑惑
  • • 题目描述
    • 解题报告
    • 参考代码(C++版本)
  • 第三题 191. 位1的个数
  • • 题目描述
    • 解题报告
    • 参考代码(C++版本)
  • 第四题 461. 汉明距离
  • • 题目描述
    • 解题报告
    • 参考代码(C++版本)
  • 第五题 136. 只出现一次的数字
  • • 题目描述
    • 解题报告
    • 参考代码(C++版本)
  • 第六题 137. 只出现一次的数字 II
  • • 题目描述
    • 解题报告
    • 参考代码(C++版本)
  •  总结

每日算法练习，千锤百炼，静待花开。


现在的单片机是会持续更的，因为我要靠它去捣腾暑假实习的事儿：十四天学会51单片机；
Leetcode的专栏会持续更，因为在跟着英雄哥做知识星球的事儿：在lc被欺负的这些年；
对英雄哥的知识星球有兴趣的可以看看他这篇文章喔： 英雄算法联盟 | 31天让你的算法与众不同
但是英雄哥这儿了，五月不再招人啦，得等待六月嗷~

至于现在这个专栏只会记录全部是每日的算法题：知识星球每天的习题，以及在咱高校算法学习社区中，泡泡和p佬普及组和提高组的题目，一般是当天写当天更吧。现在优先写泡泡的题，p佬的有点把握不住


好朋友执梗正在带新星计划，有想法的小伙伴不要犹豫嗷
点击查看详情

昨天泡泡放的这个题了（因为昨天弄某些申报，耽搁了…），应该是类似于蓝桥杯的买不到的数目，因为蓝桥的买不到的数目的数据范围可以使用数论也可以动态规划，但是洛谷的小凯的疑惑，应该只能使用数论的知识了（假如有其他方法做出来的小伙伴，可以分享一下思路的）

第一题 [蓝桥杯 2013 省] 买不到的数目 题目描述

原题传送门

解题报告

解法一是一种数学知识的积累吧。
两个互质的数x,y不能组成的最大整数为x*y-x-y，如果题目给定的两个数不互质的话，那么任何数都能组成，所以给定的数一定是互质的。


解法二是动态规划。
这个动态规划不用闫式DP分析了。直接可以从递推的想法来实现。
bool数组 bool f[i]来记录是否能组成当前这个数字i
状态转移就十分简单了，倘若能够从f[i-n]转移过来或者能从f[i-m]转移过来，就是能够组成，否则就记录答案，表示不能组成当前的数字（从两个数字中最小的开始枚举，就能够递推找到最大的数字了）

参考代码(C++版本)

解法一：

#include 
using namespace std;
typedef long long LL;
LL n,m;

int main() 
{
    scanf("%lld %lld",&n,&m);
    printf("%lld",n*m - n -m);
    return 0;
}

解法二：

#include 
using namespace std;
typedef long long LL;
bool f[1000010];
int n,m;

int main() 
{
    cin >> n >>m;
    int maxv = max(n,m);
    int minv = min(n,m);
    f[0] = true;
    int ans = 0;
    for(int i = minv; i <= n * m;i++)
    {
        if(f[i-minv]) f[i] = true;
        else if(i >= maxv && f[i-maxv]) f[i] = true;
        else ans = i;
    }
    
    cout << ans;
    return 0;
}

第二题 P3951 [NOIP2017 提高组] 小凯的疑惑 题目描述

原题传送门

解题报告 参考代码(C++版本)

#include 

using namespace std;
typedef long long LL; 
LL n, m; //2,147,483,648

int main()
{
	scanf("%lld %lld",&n,&m);
	printf("%lldn",n*m-n-m);
	return 0;
} 

第三题 191. 位1的个数

积累lowbit运算

题目描述

原题传送门

解题报告

lowbit运算——这东西是板子，背着就好
关于lowbit运算的知识点：

根据图片中对lowbit运算的定义，对于非负整数10，其二进制表示为 ( 1010 ) 2 (1010)_2 (1010)2​，那么lowbit(n) = ( 10 ) 2 (10)_2 (10)2​ = 2


lowbit运算的证明/推导
关于运算的证明可以权当了解，现阶段会用，能Ac就好，以后学习更深入了再搞定原理也不迟的。

lowbit运算的作用
① 可以配合哈希表找出整除二进制表示下的所有是1的位数
② lowbit运算是树状数组的一个基本运算

参考代码(C++版本)

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ans = 0;
         
         while(n)
         {
             n -= (n & (-n));
             ans ++;
         }
        return ans;
    }
};

第四题 461. 汉明距离 题目描述

原题传送门

解题报告

使用右移运算符一位一位的移动，比较

参考代码(C++版本)

class Solution {
public:
    int hammingDistance(int x, int y) {
        //一位一位的移动，比较
        int ans = 0;
        while(x || y)
        {
            if((x&1) != (y&1)) ans ++;
            x >>= 1;
            y >>= 1;
        }
        return ans;
    }
};

解法二：
学习一下英雄哥的玩法

class Solution {
public:
    int hanmingWeight(uint32_t n)
    {
        int ans = 0;
        while(n)
        {
            ans += (n & 1);
            n >>= 1;
        }
        return ans;
    }
    int hammingDistance(int x, int y) {
        return hanmingWeight(x^y);
    }
};

第五题 136. 只出现一次的数字

异或运算积累

题目描述

原题传送门

解题报告

解法一：哈希表
解法二：任意两个相同的数字(2的倍数同样成立哦)异或结果为0，那么把所有的数字全部异或之后，最后得到的结果就0 ^ 只出现一次的数字。因为异或运算有时候也称我不进位加法，0 ^ 只出现一次的数字 = 0 + 只出现一次的数字

参考代码(C++版本)

解法一：

class Solution {
public:
    int singleNumber(vector& nums) {
        //哈希表的思想
        unordered_map  mp;
        int n = nums.size();
        for(int i = 0; i < n;i++)
            mp[nums[i]] ++;
            
        int ans = 0;
        for(int i = 0; i < n;i++)
            if(mp[nums[i]] == 1) 
                ans = nums[i];
        
        return ans;

    }
}; 

解法二：
这个解法的效率，嘎嘎提升了

class Solution {
public:
    int singleNumber(vector& nums) {
        int n = nums.size();

        int ans = nums[0];
        for(int i = 1; i < n;i++)
            ans ^= nums[i];
        
        return ans;

    }
};

第六题 137. 只出现一次的数字 II

数位统计——为状态压缩动态规划做铺垫了

题目描述

原题传送门

解题报告

老规矩，也是可以直接哈希表
解法二：数位统计

参考代码(C++版本)

解法一：

class Solution {
public:
    int singleNumber(vector& nums) {
        unordered_map  mp;
        int n = nums.size();
        for(int i = 0; i < n;i++)
            mp[nums[i]] ++;
            
        int ans = 0;
        for(int i = 0; i < n;i++)
            if(mp[nums[i]] == 1) 
                ans = nums[i];
        
        return ans;
    }
};

解法二：
数位统计的思想
看到这个题的数据范围了，其实就可以向着位运算的方向思考了。
现在了，其实可以使用一个32位的二进制来表示咱们要进行计算的十进制数字，然后对用于表示的32位的二进制进行求和，因为除了咱们需要的答案，其他的结果都是三的倍数，那么可以将求和的结果的每一位和3进行取模，最后得到的结果就是咱们需要的答案了，再把其从二进制转换为十进制就好。

样例演示：
nums = [2,2,3,2]
将这四个数字转换为32位的二进制：
[00000000000000000000000000000010, 00000000000000000000000000000010, 00000000000000000000000000000011, 00000000000000000000000000000010]；

对这四个二进制的每一位进行求和：
[00000000000000000000000000000041]
将求和结果的每一位进行3的取模运算：
[00000000000000000000000000000011]
将得到的结果[00000000000000000000000000000011]从二进制转换成十进制就是3

class Solution {
public:
    int singleNumber(vector& nums) {
        int ans = 0;
        int n = nums.size();

        for(int i = 0; i < 32;i++)
        {
            int sum = 0;
            for(int j = 0;j < n;j++)
                sum += ((nums[j] >> i) & 1);
            
            if(sum%3) //将得到的二进制转十进制
                ans |= (1 << i);
        }
        return ans;
    }
};

① 积累买不到数目的数学想法，我记得是使用裴蜀定理来证明的，后续补上吧
② 积累lowbit运算
③ 数位统计的想法