当前位置:   article > 正文

算法——位运算_算法运算实现位运算

算法运算实现位运算
1.二进制加法

https://leetcode.cn/problems/JFETK5/
思路一 (模拟):

#include<iostream>
#include<algorithm>

using namespace std;
/*
给定两个 01 字符串 a 和 b ,请计算它们的和,并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字 1 和 0。

 
示例 1:

输入: a = "11", b = "10"
输出: "101"
示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

思路之:模拟
(1)翻转字符串使低位对其
 (2)创建结果字符串
(3)s1.at(i)按位判断 加到临时变量上
(4)% /作进位和该位的结果计算
(5)超出a b长度的部分算0 结果最高位的0去除 然后翻转回来
时间复杂度:O(n),这里的时间复杂度来源于顺序遍历 a和 b。
空间复杂度:O(1),定义的一些变量
*/

/*
class Solution {
public:
    string addBinary(string a, string b) {
        int lengtha = a.size();
        int lengthb = b.size();
        int n = max(lengtha, lengthb);
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int temp = 0;
        string res(n + 1, '0');
        for (int i = 0; i < n+1; i++) {
            if (i < a.size())
            {
                temp += (a.at(i) == '1') ? 1 : 0;

            }
            else {
                temp += 0;
            }
            if (i < b.size())
            {
                temp += (b.at(i) == '1') ? 1 : 0;
            }
            else {
                temp += 0;
            }

            res = (temp%2 == 1) ? res.replace(i, 1, "1") : res.replace(i, 1, "0");

            temp = temp / 2;


        }
        
        if (res.at(n) == '0')
            res = res.substr(0, n);

          reverse(res.begin(), res.end());

        return res;

    }
};
*/
/*
int main() {

    Solution sol;
    //string s1(sol.addBinary("0", "0"));
    string s1(sol.addBinary("1010", "10111"));

    cout << s1 << endl;
	return 0;
}*/
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
模拟思路的参考答案
class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int n = max(a.size(), b.size()), carry = 0;
        for (size_t i = 0; i < n; ++i) {
            carry += i < a.size() ? (a.at(i) == '1') : 0;
            carry += i < b.size() ? (b.at(i) == '1') : 0;
            ans.push_back((carry % 2) ? '1' : '0');
            carry /= 2;
        }

        if (carry) {
            ans.push_back('1');
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

思路二(位运算):
如果不允许加减乘除可以用位运算的思路
看一眼即可
首先转换成二进制数字 不太明白
在这里插入图片描述

2.前 n 个数字二进制中 1 的个数
给定一个非负整数 n ,请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数,并输出一个数组。

示例 1:

输入: n = 2
输出: [0,1,1]
解释: 
0 --> 0
1 --> 1
2 --> 10
示例 2:

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

我的思路 模拟运算。。。

class Solution {
public:
    int number1(int n){
        int cnt=0;
        while(1)
        {
            
            cnt+=(n%2==1)?1:0;
            n=n/2;
            if(n==0||n==1)
           {
               if(n==1)
               cnt+=1;

            break;
           }


        }
        return cnt;
    }
    vector<int> countBits(int n) {
        vector<int> a;
        int i=0;
       
            for(int i=0;i<=n;i++)
            a.push_back(number1(i));
        
        return a;

    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

思路二:一比特数算法

方法一:
Brian Kernighan 算法
最直观的做法是对从 0 到 n 的每个整数直接计算「一比特数」。
每个 int 型的数都可以用 32 位二进制数表示,
只要遍历其二进制表示的每一位即可得到 11 的数目。

利用 Brian Kernighan 算法,可以在一定程度上进一步提升计算速度。
Brian Kernighan 算法的原理是:对于任意整数 x,
令 x=x & (x−1),该运算将 xx 的二进制表示的最后一个 1 变成 0。
因此,对 x 重复该操作,直到 x 变成 0,则操作次数即为 x 的「一比特数」。

对于给定的 n,计算从 00 到 nn 的每个整数的「一比特数」的时间都不会超过 O(logn),因此总时间复杂度为
O(nlogn)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
class Solution {
public:
    int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }

    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        for (int i = 0; i <= n; i++) {
            bits[i] = countOnes(i);
        }
        return bits;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
3.剑指 Offer II 005. 单词长度的最大乘积

给定一个字符串数组 words,请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时,它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串,返回 0。

示例 1:

输入: words = [“abcw”,“baz”,“foo”,“bar”,“fxyz”,“abcdef”]
输出: 16
解释: 这两个单词为 “abcw”, “fxyz”。它们不包含相同字符,且长度的乘积最大。
示例 2:

输入: words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
输出: 4
解释: 这两个单词为 “ab”, “cd”。

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int length = words.size();
        vector<int> masks(length);
        for (int i = 0; i < length; i++) {
            string word = words[i];
            int wordLength = word.size();
            for (int j = 0; j < wordLength; j++) {
                masks[i] |= 1 << (word[j] - 'a');
            }
        }
        int maxProd = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxProd = max(maxProd, int(words[i].size() * words[j].size()));
                }
            }
        }
        return maxProd;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/在线问答5/article/detail/780987
推荐阅读
相关标签
  

闽ICP备14008679号