Just for Life.

明月更几时

0%

算法系列：数学运算与位运算

发表于 更新于
本文字数： 6.4k 阅读时长 ≈ 6 分钟

之前从未意识到位运算的强大威力，认为与或非只存在大一 C 语言的考试或单片机的设计中，直到今天才发现我错了。做一个常用的位运算和数学运算的整理。

与运算

与运算我们都知道，1 与 1 为 1，其他的与运算结果都是 0。那这有什么用呢？如果一个数用二进制表示，不断的进行 n = n & (n-1) 运算，可以知道这个数的二进制有多少个 1。

191. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数

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

这个题就是上面说的与运算的经典例子，直接写出程序：

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

231. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。如果存在一个整数 x 使得 $n == 2^x$ ，则认为 n 是 2 的幂次方。

不要急，我们脑部一下 2 的幂那些数，比如 4，8，16 有什么显著特点，答案是他们的二进制只有一个 1，那么就很简单了。利用上一题的结论，直接判断输入的数字二进制中是否有一个 1 即可。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        int a = n & (n-1);
        return a == 0 ? true : false;
    }
};

异或

如果不出意外的话，这个运算只会在考试前一周牢牢记住，考试完彻底忘记。今天来补充一下，异或运算是指：当两数相同时，输出为 false，不同时，输出为 true。异或具有以下性质：

  1. 交换率：$p \circ q = q \circ p$
  2. 结合率：$p \circ (a \circ b) = p \circ a \circ b$
  3. 恒等率：$p \circ 0 = p$
  4. 归零率：$p \circ p = 0$
  5. 自反率：$p \circ q \circ q = 0$

其实自反率就是交换率的延伸，而用的最多的也是自反，用于判断数组中只出现一次的元素。只需要异或数组内的全部元素，由于其他元素均重复出现。因此结果只保留只出现一次的元素。

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？示例:

1
2
输入: [2,2,1]
输出: 1

注意，初始化为 0，因为任何数异或 0 都是它自己。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (auto i : nums) {
            res ^= i;
        }
        return res;
    }
};

268. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。示例：

1
2
3
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

因为数字的范围是 [0,n] 且丢失了其中一个，那么我们直接异或 [0,...,n]，再去异或输入的数组，结果就是缺失的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        for (int i = 0; i <= n; i++) {
            res ^= i;
        }
        for (auto i : nums) {
            res ^= i;
        }
        return res;
    }
};

阶乘问题

阶乘或数学运算等问题只需要记住一点，不用真的去算，因为结果一定会越界。

172. 阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。示例：

1
2
3
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

我们首先来分析，阶乘的时候只有出现 5 或 5 的倍数时，阶乘才能出现 0。因此，如果阶乘的数字小于 5，可以直接返回 0。而 19 这样的数字能提供 5，10，15 一共 3 个 5，因此末尾 0 的数量就是 3。

此外，对于 25，125 等 5 的幂次方，25，50，75，100 能提供两个 5。也就是说，针对这种情况需要额外的处理，处理完 5 后要处理 25，然后 125，直到遇到 0 结束。 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
        while (n) {
            res += n / 5;
            n /= 5;
        }
        return res;
    }
};

793. 阶乘函数后 K 个零

f(x) 是 x! 末尾是 0 的数量。例如，f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。示例：

1
2
3
输入：k = 0
输出：5
解释：0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。

分析题意：

  1. 如果末尾没有 0，那么一定是 0，1，2，3，4 这 5 个数
  2. 如果末尾有 0，利用 172 题的结论，二分查找即可。如果满足给定的 0 的个数，那么一定是 5 个数，因为，6 个数的情况下，一定会多出一个 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
class Solution {
public:

    // 计算 0 的数量
    lng find_(lng mid) {
        lng n = 0;
        while (mid) {
            n += mid / 5;
            mid /= 5;
        }
        return n;
    }

    int preimageSizeFZF(int k) {
        if (k < 5)
            return 5;
        lng l = 0, r = lNG_MAX;
        while (l <= r) {
            lng mid = l + (r - l) / 2;
            auto a = find_(mid);
            if (a == k)
                return 5;
            if (a < k) {
                l = mid + 1;
            }
            if (a > k) {
                r = mid - 1;
            }
        }
        return 0;
    }
};

素数

204. 计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。示例：

1
2
3
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

高效的计数素数。我理解的高效是，如果之前计算过，那么后续就不用计算了。如 2 是素数，那么 4，6，8，10 则都不是素数，如果遍历到 7，那么 14，21 也不是素数。

按照想法写出程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countPrimes(int n) {
        vector<bool> arr(n, true);
        // 素数常见处理，平方小于 n 即可
        for (int i = 2; i * i < n; i++) {
            if (arr[i]) {
                // 这个数的倍数都是素数
                for (int j = 2 * i; j < n; j += i) {
                    arr[j] = false;
                }
            }
        }
        int res = 0;
        // 剩下的都是素数
        for (int i = 2; i < n; i++) {
            if (arr[i])
                res ++;
        }
        return res;
    }
};

超级幂运算

372. 超级次方

你的任务是计算 $a^b$ 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。示例：

1
2
输入：a = 2, b = [3]
输出：8

如果要计算 $4^{1337}$ 次方，直接暴力计算是愚蠢的行为。我们对问题进行分解：$4^{1337} = 4^7 \times 4^{(133)10}$，分治这不就来了。

如果说，之前需要运算 1337 次，那么分治后，只需要运算 7 + 3 + 3 + 1 + 10 + 10 + 10 次，显著降低运算次数，算是一种空间换时间吧。

在补充一条数学运算：(a * b) % c = (a % c) * (b % c) % c。

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
class Solution {
public:

    const int mod = 1337;

    int _pow(int a, int b) {
        if (b == 0)
            return 1;
        int s1 = a;
        int s2 = a;
        s2 %= mod;
        for (int i = 0; i < b - 1; i++) {
            s2 *= (s1 % mod);
            s2 %= mod;
        }
        return s2;
    }

    int superPow(int a, vector<int>& b) {
        if (b.size() == 0)
            return 1;
        int e = b.back();
        b.pop_back();
        // 递归
        int a1 = _pow(a, e);
        int a2 = _pow(superPow(a, b), 10);
        return (a1 % mod) * (a2 % mod) % mod;
    }
};

三数之和

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。示例 1：

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

在此之前，先来看两数之和。在数组中找到两个数，两数之和为 0。此时我们对数组进行排序，并使用两个指针，左指针从左向右移动，右指针从右向左移动，求两者之和，如果和大于 0，说明右指针指向的数据太大，需要将右指针左移，反之将左指针右移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> twoSumTarget(vector<int>& nums, int target) {
    // nums 数组必须有序
    sort(nums.begin(), nums.end());
    int l = 0, r = nums.size() - 1;
    vector<vector<int>> res;
    while (l < r) {
        int sum = nums[l] + nums[hi];
        int left = nums[l], right = nums[hi];
        if (sum < target) {
            l++;
        } else if (sum > target) {
            r--;
        } else {
            res.push_back({left, right});
            l++;
            r--;
        }
    }
    return res;
}

但是呢，对于 [-3, -3, 1, 2, 3] 这样的数组而言，第一个 -3 计算过之后，第二个 -3 就没必要计算了。因此，可以在数值相等的情况下省略一些情况，前提是数组必须有序。写出以下优化的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> twoSumTarget(vector<int>& nums, int target) {
    // nums 数组必须有序
    sort(nums.begin(), nums.end());
    int l = 0, r = nums.size() - 1;
    vector<vector<int>> res;
    while (l < r) {
        int sum = nums[l] + nums[r];
        int left = nums[l], right = nums[r];
        if (sum < target) {
            while (l < r && nums[l] == left) l++;
        } else if (sum > target) {
            while (l < r && nums[r] == right) r--;
        } else {
            res.push_back({left, right});
            while (l < r && nums[l] == left) l++;
            while (l < r && nums[r] == right) r--;
        }
    }
    return res;
}

至此，我们可以写出三数之和：

  • 遍历数组，得到第一个数 first，因为数组是有序的，如果 first>0 的情况就可以跳过
  • 那么另外两个数必须在 first 之后，且另外两数之和需要等于 -first，此时套用上面的两数之和的程序即可
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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> res;
        for (int first = 0; first < n; first++) {
            // 如果第一个 first 算过了，后面相等的值都可以忽略
            if (nums[first] > 0 || (first > 0 && nums[first-1] == nums[first])) {
                continue;
            }
            int target = -nums[first];
            // third 是双指针中的右指针
            int third = n - 1;
            for (int second = first + 1; second < n; second++) {
                // 忽略算过的值
                if (second > first + 1 && nums[second-1] == nums[second]) {
                    continue;
                }
                while (third > second && nums[third] + nums[second] > target) {
                    third--;
                }
                // 不能有相同的值
                if (third == second) {
                    break;
                }
                // 保留结果
                if (nums[third] + nums[second] == target) {
                    res.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return res;
    }
};
本文相关
感谢上学期间打赏我的朋友们。赛博乞讨：我，秦始皇，打钱。

欢迎订阅我的文章