1

「算法刷题」位运算专项汇总(力扣版)

 1 year ago
source link: https://magicdeveloperdrl.github.io/2022/06/13/%E7%AE%97%E6%B3%95%E5%88%B7%E9%A2%98-%E4%BD%8D%E8%BF%90%E7%AE%97%E4%B8%93%E9%A1%B9%E6%B1%87%E6%80%BB-%E5%8A%9B%E6%89%A3%E7%89%88.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

「算法刷题」位运算专项汇总(力扣版)

Jun 13, 2022 • MRL Liu

本文主要记录二进制的相关LeetCode题目的实现代码,直接给出本文各个题目的答案,供有需求的读者学习或复制。

一、二进制计数

461. 汉明距离(简单难度)

class Solution {
public:
    int hammingDistance(int x, int y) {
        // 方法一:进制转换
        // int count=0;
        // if(x==y)
        //     return 0;
        // // 同时取位
        // while(x!=0||y!=0){
        //     if(x%2!=y%2)
        //         count++;
        //     x=x/2;
        //     y=y/2;
        // }
        // return count;
        // 方法二:位运算
        int count=0;
        int a=x^y;// 异或运算,相同为0,不同为1
        while(a){
            count+=a&1;// 查看最后一位是否是1
            a>>=1;// 右移1位
        }
        return  count;
    }
};

191. 位1的个数(简单难度)

剑指 Offer 15. 二进制中1的个数(简单难度)

class Solution {
public:
    int hammingWeight(uint32_t n) {
        string res;
        if(n==0) res="0";
        while(n>0){
            res=to_string(n%2)+res;
            n=n/2;
        }
        int num=0;
        for(char c:res){
            if(c=='1') num++;
        }
        return num;
    }
};
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n) {
            count += n & 1;
            n>>=1;
        }
        return count;
    }
};

338. 比特位计数(简单难度)

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数(简单难度)

class Solution {
public:
    // 十进制转换为2二进制
    string ten2k(int num,int k=2){
        if(num==0) return "0";
        string ans;
        while(num){
            ans= to_string(num%k)+ans;
            num/=k;
        }
        return ans;
    }
    vector<int> countBits(int n) {
        vector<int> res;
        for(int i=0;i<=n;i++){
            string bits=ten2k(i);//二进制的字符串
            int num=0;//统计字符串中1的个数
            for(int j=0;j<bits.length();j++){
                if(bits[j]=='1') num++;
            }
            res.push_back(num);
        }
        return res;
    }
};

190. 颠倒二进制位(简单难度)

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t rev = 0;
        int power=31;
        while(n){
            rev+=(n&1)<<power;//左移32位
            n>>=1;
            power--;
        }
        return rev;
    }
};

二、二进制转换

1290. 二进制链表转整数(简单难度)

class Solution {
public:
    // 二进制转十进制
    int getDecimalValue(ListNode* head) {
        vector<int> arr;
        // 将链表元素加入数组中
        ListNode* p=head;
        while(p){
            arr.push_back(p->val);
            p=p->next;
        }
        // 二进制转换为十进制
        int n=arr.size();
        int k=1;
        int sum=0;
        for(int i=n-1;i>=0;i--){
            sum+=arr[i]*k;
            k*=2;
        }
        return sum;
    }
};

693. 交替位二进制数(简单难度)

class Solution {
public:
    string ten2k(int n,int k=2){
        if(n==0) return "0";
        string res;
        while(n>0){
            res=to_string(n%k)+res;
            n=n/k;
        }
        return res;
    }
    bool hasAlternatingBits(int n) {
        string kbit=ten2k(n);
        char flag='0';
        for(int i=1;i<kbit.length();i++){
            if(kbit[i]==kbit[i-1]) return false;
        }
        return true;
    }
};

1009. 十进制整数的反码(简单难度)

476. 数字的补数(简单难度)

class Solution {
public:
    string ten2k(int n,int k=2){
        if(n==0) return "0";
        string res;
        while(n>0){
            res=to_string(n%k)+res;
            n=n/k;
        }
        return res;
    }
    int k2ten(string n,int k=2){
        int sum=0;
        long a=1;// 注意,必须为整型
        for(int i=n.length()-1;i>=0;i--){
            sum+=(n[i]-'0')*a;
            a*=k;
        }
        return sum;
    }
    int bitwiseComplement(int num) {
        string kbit = ten2k(num);//10进制转换为二进制
        string res="";
        for(char c:kbit){
            if(c=='1'){
                res+='0';
            }
            else {
                res+='1';
            }
        }
        int n=k2ten(res);
        return n;
    }
};

三、非二进制转换

504. 七进制数(简单难度)

class Solution {
public:
    string convertToBase7(int num) {
        if(num==0) return "0";
        string res;
        // 处理正数
        int tempNum=abs(num);//如果num为负数,变为正数
        while(tempNum>0){
            res=to_string(tempNum%7)+res;
            tempNum=tempNum/7;
        }
        if(num<0) res.insert(res.begin(),'-');
        return res;
    }
};

405. 数字转换为十六进制数(简单难度)

class Solution {
public:
    string toHex(int n) {
        if(n==0) return "0";
        unsigned num = n;//转换为无符号
        string res;
        while(num>0){
            int base=num%16;
            char c='0';
            if(base>9) {
                c=base-10+'a';
            }else{
                c=base+'0';
            }
            res+=c;
            num=num/16;
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

171. Excel 表列序号(简单难度)

​ 这道题要求将Excel 表中的26个的由大写字母组成的列名称转换成相对应的列序号,因此本质就是一道26进制转换为10进制的题目,但是这道题与标准的进制转换(0-25)不同,因为Excel表的列序号是1到26,需要特殊处理。

class Solution {
public:
    int titleToNumber(string columnTitle) {
        int sum=0;
        long k=1;//幂,幂要设置为long
        for(int i=columnTitle.length()-1;i>=0;i--){
            sum+=(columnTitle[i]-'A'+1)*k;
            k*=26;
        }
        return sum;
    }
};

168. Excel表列名称(简单难度)

class Solution {
public:
    string convertToTitle(int n) {
        // 10进制转26进制的模板,正常26进制是0-25,该题是1-26,
        string res="";
        while(n>0){
            --n;//每一位都多了1,此处-1使其可以用正常的26进制代码处理
            res+=n%26+'A';//将数字字符转换为大写字母字符,'A'是65,'0'是48
            n=n/26;
        } 
        reverse(res.begin(),res.end());//反转序列
        return res;
    }
};

四、数位分离

1281. 整数的各位积和之差(简单难度)

class Solution {
public:
    int subtractProductAndSum(int n) {
        int sum=0;
        int x=1;
        while(n>0){
            sum+=n%10;
            x*=n%10;
            n=n/10;
        }
        return x-sum;
    }
};

258. 各位相加(简单难度)

class Solution {
public:
    int addDigits(int num) {
        while(num>=10)// 大于等于1位数
        {
            int sum=0;
            while(num>0){
                sum+=num%10;
                num=num/10;
            };
            num=sum;
        }
        return num;
    }
};

1945. 字符串转化后的各位数字之和(简单难度)

class Solution {
public:
    int getLucky(string s, int k) {
        // 转换成数字
        string str="";
        for(int i=0;i<s.length();i++){
            int num=s[i]-'0'-48;
            str+=to_string(num);
        }
        // 重复转换操作k次
        int sum=0;
        while(k)// 
        {
            sum=0;
            for(int i=0;i<str.length();i++){
                sum+=str[i]-'0';
            }
            str=to_string(sum);
            k--;
        }
        return sum;
    }
};

1837. K 进制表示下的各位数字总和(简单难度)

class Solution {
public:
    int sumBase(int n, int k) {
        // 从10进制转换为k进制
        string kbits="";
        if(n==0) kbits="0";
        while(n>0){
            kbits=to_string(n%k)+kbits;
            n=n/k;
        }
        // 各位累和
        int sum=0;
        for(char c:kbits) sum+=c-'0';
        return sum;
    }
};

五、数组中元素出现的次数

1、一个数出现1次,其余数都出现2次

136. 只出现一次的数字(简单难度)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 方法一:位运算
        // 数组中一定有奇数个元素,数组中的全部元素进行异或运算,结果即为只出现一次的数字
        // int res=0;
        // for(int num:nums) res^=num;
        // return res;
        // 方法二:位运算
        int res=0;
        for(int i=0;i<32;i++){
            int mask=1<<i;//从右向左取第i位
            int cnt = 0;//第i位出现的次数
            // 遍历整个数组后的第i位出现了几次1
            for (int num:nums) {
                if ((num & mask) != 0) {
                    cnt++;
                }
            }
            // 如果第i位没有出现3次则保留
            if (cnt % 2 != 0) {
                res |= mask;
            }
        }
        return res;
        // // 方法二:哈希法
        // unordered_map<int,int> map;// 数字和出现次数
        // // 遍历数组一遍统计频率
        // for(int num:nums){
        //     map[num]++;
        // }
        // // 遍历哈希表
        // for(auto it=map.begin();it!=map.end();++it){
        //     if(it->second==1)
        //         return it->first;
        // }
        // return -1;
    }
};

2、一个数出现1次,其余数都出现3次

137. 只出现一次的数字 II(中等难度)

剑指 Offer 56 - II. 数组中数字出现的次数 II(中等难度)

剑指 Offer II 004. 只出现一次的数字(中等难度)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 方法一:位运算(异或)
        // int ones=0;twos=0;
        // for(int num:nums){
        //     ones=ones^num&(~twos);//x & ~x = 0;// num,0,0
        //     twos=twos^num&(~ones);//x & ~0 = x;// 0,num,0
        // }
        // return ones;
        // 方法二:位运算
        int res=0;
        for(int i=0;i<32;i++){
            int mask=1<<i;//从右向左取第i位
            int cnt = 0;//第i位出现的次数
            // 遍历整个数组后的第i位出现了几次1
            for (int num:nums) {
                if ((num & mask) != 0) {
                    cnt++;
                }
            }
            // 如果第i位没有出现3次则保留
            if (cnt % 3 != 0) {
                res |= mask;
            }
        }
        return res;
        // 方法二:哈希法
        // unordered_map<int,int> map;// 数字和出现次数
        // // 遍历数组一遍统计频率
        // for(int num:nums){
        //     map[num]++;
        // }
        // // 再次遍历遍历字符串
        // for(int num:nums){
        //     if(map[num]==1)
        //         return num;
        // }
        // return -1;
    }
};

3、两个数出现1次,其余数都出现2次

260. 只出现一次的数字 III(中等难度)

剑指 Offer 56 - I. 数组中数字出现的次数(中等难度)

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res(2,0);
        int aob=0;
        for(int num:nums){
            aob^=num;
        }
        // 取出最后一位
        int lastBit = (aob == INT_MIN ? aob : aob & (-aob));// 防止溢出
        for (int num : nums) {
            // 分成2个数
            if ((lastBit & num) != 0) 
                res[0] ^= num;
            else 
                res[1] ^= num;
            
        }
        return res;
    }
};

六、四则运算

1、两数加法

剑指 Offer 64. 求1+2+…+n

class Solution {
public:
    int sumNums(int n) {
        if(n==0) return 0;
        return n+sumNums(n-1);
    }
};

371. 两整数之和(简单难度)

剑指 Offer 65. 不用加减乘除做加法(简单难度)

面试题 17.01. 不用加号的加法(简单难度)

class Solution {
public:
    int getSum(int a, int b) {
        // 当进位部分不为0,说明需要继续加
        while (a != 0) {
            int temp = a ^ b;//非进位部分(没有添加进位部分),按位异或,
            //异或这里可看做是相加但是不显现进位,比如5 ^ 3
                 /*0 1 0 1
                   0 0 1 1
                 ------------
                   0 1 1 0   */
            a = ((unsigned int)a & b) << 1; //进位部分,都是1是发生进位,对有符号左移的溢出保护处理
            //相与为了让进位显现出来,比如5 & 3
                /* 0 1 0 1
                   0 0 1 1
                 ------------
                   0 0 0 1
              上面的最低位1和1相与得1*/
            b = temp;
        }
        return b;
    }
};

67. 二进制求和(简单难度)

剑指 Offer II 002. 二进制加法(简单难度)

class Solution {
public:
    string addBinary(string a, string b) {
        string res;
        // 从右向左同时遍历2个可能不等长的字符串
        int i=a.length()-1;
        int j=b.length()-1;
        bool carry=false;
        int sum=0;
        while(i>=0||j>=0){
            sum=0;
            if(i>=0) sum+=a[i--]-'0';
            if(j>=0) sum+=b[j--]-'0';
            if(carry) sum+=1;
            res =to_string(sum%2)+res;
            carry=sum>=2?true:false;
        }
        // 如果有多余的进位
        if(carry) res =to_string(1)+res;
        return res;
    }
};

2、两数除法

29. 两数相除(中等难度)

剑指 Offer II 001. 整数除法(简单难度)

class Solution {
public:
    /* 被除数÷除数=商...余数,进而推导得出:商×除数+余数=被除数
    思路:找到一个足够大的数x,x足够接近商,使得x*除数<=被除数,即(被除数/x)>=除数(x必须为正数)
    因为不可以使用*和/,就只可使用位移,计算机在做位移时效率特别高,向左移1相当于乘以2,向右位移1相当于除以2
    (被除数/x)>=除数(x必须为正数),可以表示为(被除数>>i)>=除数,x=2^i,因为x足够大,所以i应该从最大值不断减少
    i的取值范围为[0,31],注意:被除数和除数都需要转换为unsigned int
    以100/3为例,x=2^n是1,2,4,8...2^31这种数
    当n=31时,x特别大,100/2^n是一个很小的数,肯定是小于3的,所以循环下来,
    当n=5时,x=32,100/32=3, 刚好是大于等于3的,说明真正的商res>=x,我们可以先res+=x;
    将100-32*3=4,此时被除数变为了4,接下来继续处理4:
    当n=0时,x=1,4/1=4,刚好大于等于3,说明res+=1,被除数4-1*3=1,此时n已到最小值,结束商res=33
    这其中得处理一些特殊的数,比如divisor是不能为0的,INT_MIN和INT_MAX*/
    int divide(int dividend, int divisor) {
        if(dividend==0) return 0;// 被除数为0,直接返回0
        if (dividend==INT_MIN &&divisor==-1) return INT_MAX;// 被除数是最小值,除数是-1,返回最大值
        bool negative=(dividend^divisor)<0;//用异或来计算是否符号相异
        // 将有符号整数转为无符号整数
        unsigned int t = abs(dividend);//被除数
        unsigned int d = abs(divisor);// 除数
        unsigned int res = 0;// 商
        // i从大到小,商从小到大
        for (int i = 31; i >= 0; i--) {
            // 计算t除于2^i的商
            if((t>>i)>=d) {//找出足够大的数2^n*divisor
                res+=((unsigned int)1)<<i;//商>=1*2^n
                t-= d<<i;//将被除数-2^n*divisor
            }
        }
        //特殊数不能将unsigned int转为int
        if(res == INT_MIN) return INT_MIN;
        else return negative?-(int)res:(int)res;//符号相异取反
    }
};

「算法刷题」数组之滑动窗口专项汇总(力扣版)

「算法刷题」数学情景专项汇总(力扣版)


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK