6

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

 2 years ago
source link: https://muyuuuu.github.io/2022/05/27/math-and-bit/
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.
neoserver,ios ssh client

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

2022-05-27

1 4k 4 分钟

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

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

191. 位1的个数

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

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

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

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==2x ，则认为 n 是 2 的幂次方。

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

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∘q=q∘p
  2. 结合率：p∘(a∘b)=p∘a∘b
  3. 恒等率：p∘0=p
  4. 归零率：p∘p=0
  5. 自反率：p∘q∘q=0

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

136. 只出现一次的数字

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

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

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

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] 这个范围内没有出现在数组中的那个数。示例：

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

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

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! 结果中尾随零的数量。示例：

输入：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 结束。 

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 的数量。示例：

输入：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。
class Solution {
public:

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

int preimageSizeFZF(int k) {
        if (k < 5)
            return 5;
        long l = 0, r = LONG_MAX;
        while (l <= r) {
            long 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 的质数的数量 。示例：

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

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

按照想法写出程序：

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. 超级次方

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

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

如果要计算 41337 次方，直接暴力计算是愚蠢的行为。我们对问题进行分解：41337=47×4(133)10，分治这不就来了。

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

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

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;
    }
};

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK