剑指offer -- 位运算

发表于 | 分类于
字数统计: 1.4k | 阅读时长 ≈ 6
《功夫熊猫3》

剑指offer – 位运算

剑指 Offer 15. 二进制中1的个数

Difficulty: 简单

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

1
2
3
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

1
2
3
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

1
2
3
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

  • 输入必须是长度为 32 的 二进制串 。

Solution

方法一：逐位运算

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int sum = 0;  
        while (n) {
            sum += n % 2;
            n = n >> 1;
        }
        return sum;
    }
};

时间复杂度： $O(log_2n)$

空间复杂度： $O(1)$

方法二：n & n - 1

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int sum = 0;  
        while (n) {
            sum++;
            n &= n - 1;
        }
        return sum;
    }
};

时间复杂度： $O(M)$ ，M 为二进制数字 n 中 1 的个数

空间复杂度： $O(1)$

剑指 Offer 56 - I. 数组中数字出现的次数

Difficulty: 中等

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

1
2
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

1
2
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：

  • 2 <= nums.length <= 10000

Solution

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
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int n = 0;
        // 获得两个只出现一次数字的异或值
        for (const auto num : nums) {
            n ^= num;
        }
        // 通过该异或值，求出其最后一个位数 1 所在位置，以此对数组分组
        int c = 1;
        // ！特别需要注意的是 & 操作时需要加 (), 其优先级小于 == ， 下同
        while ((n & c) == 0) {
            c <<= 1;
        }
        // 将数组中的数字分组, 
        // a 中存 c 位置，二进制为 1 的所有数异或和
        // b 中则存相反情况
        // 这样这两个只出现一次的数字被分开
        int a = 0, b = 0;
        for (const auto& num : nums) {
            // 注意 ()
            if ((c & num) == 0) a ^= num;
            else b ^= num;
        }   
        return vector<int>{a, b};
    }
};

时间复杂度： $O(N)$

空间复杂度： $O(1)$

剑指 Offer 56 - II. 数组中数字出现的次数 II

Difficulty: 中等

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

1
2
输入：nums = [3,4,3,3]
输出：4

示例 2：

1
2
输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：

  • 1 <= nums.length <= 10000
  • 1 <= nums[i] < 2^31

Solution

方法一：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> hashmap;
        for (const auto& num : nums) {
            hashmap[num]++;
        }
        for (const auto& [r, t] : hashmap) {
            if (t == 1) return r;
        }
        return -1;
    }
};

时间复杂度： $O(N)$，遍历一次数组，一次哈希表即可，$O(N + (N - 1) / 3 + 1) \approx O(N)$。

空间复杂度： $O(N)$，哈希表需要空间 $O((N - 1) / 3 + 1) \approx O(N)$。

方法二：遍历统计，该方法可以通用 m > 1 的所有情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 方法可以通用 m > 1 的所有情况
        int m = 3;
        // 记录结果
        int res = 0;
        for (int i = 0; i < 32; i++) {
            // 用来记录当前位 1 的个数之和
            int count = 0;
            for (const auto& num : nums) {
                // 当前位置是 1 时，count++;
                if ((num & (1 << i))) count++;
            }
            // 如果统计结果 mod m == 1，则说明当前 1 多余，
            // 也就是所求数字 1 的相应位置
            if (count % m == 1) {
                res |= (1 << i);
            }
        }
        return res;
    }
};

时间复杂度： $O(N)$

空间复杂度： $O(1)$

方法三：有限状态机，数字电路方法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        // 真值表 表头 n a b
        for (const auto& n : nums) {
            b = ~a & (b ^ n);
            // a = (~a & b & n) | (a & ~b & ~n) 经过优化
            a = ~b & (a ^ n);
        }
        return b;
    }
};

优化方式：只出现一次的数字 II

时间复杂度： $O(N)$

空间复杂度： $O(1)$

剑指 Offer 65. 不用加减乘除做加法

Difficulty: 简单

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

1
2
输入: a = 1, b = 1
输出: 2

提示：

  • a, b 均可能是负数或 0
  • 结果不会溢出 32 位整数

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int add(int a, int b) {
        // 主要思想就是将带进位的加法，转变成无进位加法 + 进位值，两个部分分开计算
        while (b) {
            // c 代表进位，只有 a b 当前位皆为 1 才会进位
            // 每一位可能的进位，左移 1 位来实现
            int c = (unsigned int) (a & b) << 1;
            // 二进制无进位加法就是异或操作
            a ^= b;
            // 将进位情况变成下一次的加数
            b = c;
        }
        return a;
    }
};

时间复杂度： $O(1)$，最大情况 32 次循环

空间复杂度： $O(1)$

参考资料

图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com) 官方题解



----------- 本文结束 -----------




0%