常用基础算法

gcd() 最大公约数 #

不管x,y谁大，都无所谓，如果x<y，则第一次就是交换两个元素的位置

public int gcd(int x, int y) { //// 欧几里得算法 辗轧相除法 O(log(a+b))
    return y > 0 ? gcd(y, x % y) : x;
}
int gcd(int a, int b) { // 更相减损法
    while (true) {
        if (a > b) a -= b;
        else if (a < b) b -= a;
        else return a;
    }
}

class Solution {
public:
    int ArrayGcd(vector<int>& array) //多个数的最大公约数
    {
        int temp = array[0];

        for (int i = 1; i < array.size(); ++i)
        {
            temp = gcd(temp, array[i]);
        }

        return temp;
    }

    int ArrayLcm(vector<int>& array) //多个数的最小公倍数
    {
        int temp = lcm(array[0], array[1]);

        for (int i = 2; i < array.size(); ++i)
        {
            temp = lcm(array[i], temp);
        }

        return temp;
    }
private:
    int gcd(int a, int b) //最大公约数
    {
        if（b == 0) {
            return a;
        }

        return gcd(b, a % b);
    }

    int lcm(int a, int b) //最小公倍数:两数乘积=最小公倍数与最大公约数乘积
    {
        return a * b / gcd(a, b);
    }
};

快速幂 取模 #

如何快速计算 x8x^8 ？

x→x2→x4→x8x \rightarrow x^2 \rightarrow x^4 \rightarrow x^8

从 xx 开始，不断地对自身平方，重复三次即可得到 x8x^8 。

如何快速计算 x15x^{15} ？

x⋅x2⋅x4⋅x8=x15x \cdot x^2 \cdot x^4 \cdot x^8 = x^{15}

在 x→x2→x4→x8x \rightarrow x^2 \rightarrow x^4 \rightarrow x^8 的过程中，把这些数全部相乘，即可得到 x15x^{15} 。

如何快速计算 x13x^{13} ？

x⋅x4⋅x8=x13x \cdot x^4 \cdot x^8 = x^{13}

在 x→x2→x4→x8x \rightarrow x^2 \rightarrow x^4 \rightarrow x^8 的过程中，把 x,x4,x8x, x^4, x^8 相乘，即可得到 x13x^{13} 。

如何知道要把哪些数相乘？

13=1101(2)13 = 1101_{(2)}

把 nn 看成二进制数，从低到高遍历二进制数，遇到 1 就和 xx 的幂相乘。

如何遍历二进制数中的 1？

1101→110→11→11101 \rightarrow 110 \rightarrow 11 \rightarrow 1

不断右移二进制数，右移前看最低位是否为 1。

如何处理 n<0n < 0 的情况？

x−n=(1x)nx^{-n} = (\frac{1}{x})^n

把 nn 变成 −n-n ，把 xx 变成 1/x1/x ，就转换成了 n≥0n \ge 0 的情况。

算法1：

private static long modQpow(long a, long n, int mod) {
        if (n == 0)
            return 1;
        else if ((n & 1) == 1)
            return (modQpow(a, n - 1, mod) * a) % mod;
        else {
            long dom = modQpow(a, n >> 1, mod);
            return (dom * dom) % mod;
        }
    }

算法2：

private long pow(long x, long n) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) > 0) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }

为什么可以边计算幂边取模？ #

这是基于同余运算的性质：

  1. 如果 a ≡ b (mod m) 且 c ≡ d (mod m)，那么 a×c ≡ b×d (mod m)
  2. (a × b) mod m = ((a mod m) × (b mod m)) mod m

在代码中的体现：

  • 奇数情况：(modQpow(a, n - 1, mod) * a) % mod
    • 先递归计算a^(n-1) mod m
    • 然后乘以a并再次取模
  • 偶数情况：(dom * dom) % mod
    • 先递归计算a^(n/2) mod m
    • 然后平方并再次取模

这样每一步都保证结果在模m的范围内，避免了溢出，同时最终结果也等价于a^n mod m。

优势 #

  1. 效率高：时间复杂度为O(log n)，远优于朴素算法的O(n)
  2. 避免溢出：通过每步取模，防止中间结果溢出
  3. 适用于大数计算：特别适合计算大幂次的模运算，如密码学应用

笔试中的基础问题 #

  1. 使用String[] items = input.split(" ")，用空格作为分隔符将字符串分割成数组。这里需要注意的是，如果输入中有多个连续的 空格，split方法可能会产生空字符串。如果这种情况，我们可以使用正则表达式split("\\s+")来分割一个或多个空格。
  2. 使用Scanner的时候，nextLine()方法可以读取整行输入，包括空格，而next()方法只读取下一个单词（以空格为分隔符）。如果需要读取一行输入并处理，可以使用nextLine()。但是如果先读取了一个单词，再使用nextLine()，可能会出现读取不到预期内容的问题，因为nextLine()会读取到上一个next()调用后的换行符。解决方法是先使用next()读取单词，然后再使用nextLine()读取剩余内容。
顶部 首页 下一篇