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

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