巧解数学问题

公倍数与公因数

辗转相除法

利用辗转相除法，我们可以很方便地求得两个数的最大公因数（greatest common divisor，gcd）；将两个数相乘再除以最大公因数即可得到最小公倍数（least common multiple, lcm）。

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a% b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

扩展欧几里得算法

进一步地，我们也可以通过扩展欧几里得算法（extended gcd）在求得 a 和 b 最大公因数的同时，也得到它们的系数 x 和 y，从而使 ax + by = gcd(a, b)。

int xGCD(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1, gcd = xGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}

质数

质数又称素数，指的是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。值得注意的是，由质因子分解定理，每一个数都可以分解成质数的乘积，且分解后形式唯一。

计数质数

• 题面
• 题解

给定整数 n，返回所有小于非负整数 n 的质数的数量。（n >= 0）

埃拉托斯特尼筛法（Sieve of Eratosthenes，简称埃氏筛法）是非常常用的，判断一个整数是否是质数的方法。并且它可以在判断一个整数 n 时，同时判断所有小于 n 的整数，因此非常适合这道题。其原理也十分易懂：从 1 到 n 遍历，假设当前遍历到 m，则把所有小于 n 的、且是 m 的倍数的整数标为和数；遍历完成后，没有被标为和数的数字即为质数。

代码

int countPrimes(int n) {
    if (n <= 2) 
        return 0;
    vector<bool> prime(n, true);
    int count = n - 2; // 去掉不是质数的1
    for (int i = 2; i < n; i++) {
        if (prime[i]) {	//若一个数已经标记过，则他的倍数肯定也被标记过了，可以跳过
            for (int j = 2 * i; j < n; j += i) {
                if (prime[j]) {
                    prime[j] = false;
                    count--;
                }
            }
        }
    }
    return count;
}

利用质数的一些性质，我们可以进一步优化该算法。对于一个质数 x，如果按上文说的我们从 2x 开始标记其实是冗余的，应该直接从 x⋅x 开始标记，因为 2x,3x,… 这些数一定在 x 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等。另外，偶数倍的 x 一定被 2 标记过了，所以 j 增量为 2*i；另外，若一个数有偶数因子，则这个数一定已经被 2 标记过了，所以 i 增量为 2

int countPrimes(int n) {
    if (n <= 2) 
        return 0;
    vector<bool> prime(n, true);
    int i = 3, sqrtn = sqrt(n), count = n / 2; // 偶数一定不是质数
    while (i <= sqrtn) { // 最小质因子一定小于等于开方数
        for (int j = i * i; j < n; j += 2 * i) { // 避免偶数和重复遍历
            if (prime[j]) {
                count--;
                prime[j] = false;
            }
        }
        do {
            i += 2;
        } while (i <= sqrtn && !prime[i]); // 避免偶数和重复遍历
    }
    return count;
}

数字处理

七进制数

• 题面
• 题解

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。

进制转换类型的题，通常是利用除法和取模（mod）来进行计算，同时也要注意一些细节，如负数和零。如果输出是数字类型而非字符串，则也需要考虑是否会超出整数上下界。

代码

string convertToBase7(int num) {
    if (num == 0) 
        return "0";
    bool is_negative = (num < 0);
    if (is_negative) 
        num = -num;
    string ans;
    while (num) {
        int a = num / 7, b = num % 7;
        ans = to_string(b) + ans;
        num = a;
    }
    return is_negative ? "-" + ans: ans;
}

阶乘后的零

• 题面
• 题解

给定一个整数 n ，返回 n! 结果中尾随零的数量。（n >= 0)

示例 1：

输入：n = 3
输出：0

示例 2：

输入：n = 5
输出：1

示例 3：

输入：n = 0
输出：0

每个尾部的 0 由 2 × 5 = 10 而来，因此我们可以把阶乘的每一个元素拆成质数相乘，统计有多少个 2 和 5，取最小值即可，明显的，质因子 2 的数量远多于质因子 5 的数量，因此我们可以只统计阶乘结果里有多少个质因子 5，即 1~n 的质因子中 5 的个数和

代码

int trailingZeroes(int n) {
    int ans = 0;
    for (int i = 5; i <= n; i += 5) {
        int temp = i;
        while(temp % 5 == 0) {
            temp /= 5;
            ans++;
        }
    }
    return ans;
}

可以用数学方法再优化，换个角度考虑 1~n 的质因子 p 的个数，首先 p 的倍数的个数为$n_1=[\frac{n}{p}]$，贡献了 $n_1$ 个 p，然后 $p^2$ 的倍数个数为 $n_2=[\frac{n}{p^2}]$，因为在 $n_1$ 中已经算过了一半，所以只多贡献了 $n_2$ 个 p，以此类推，

$$ans=\sum_{k=1}[\frac{n}{p^k}]=\sum_{k=1}[\frac{\frac{n}{p^{k-1}}}{p}]$$

因此我们可以通过不断将 n 除以 5，并累加每次除后的 n，来得到答案。

int trailingZeroes(int n) {
	return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}

多么简洁，优雅，美妙！数学真伟大！

字符串相加

• 题面
• 题解

给定两个字符串形式的非负整数 num1 和 num2，num1 和num2 都不包含任何前导零，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。num1 和num2 都不包含任何前导零

示例 1：

输入：num1 = “11”, num2 = “123”
输出：”134”

示例 2：

输入：num1 = “456”, num2 = “77”
输出：”533”

示例 3：

输入：num1 = “0”, num2 = “0”
输出：”0”

因为相加运算是从后往前进行的，所以可以先翻转字符串，再逐位计算。模拟人工手算法即可。

代码

string addStrings(string num1, string num2) {
    string output("");
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    int onelen = num1.length(), twolen = num2.length();
    if (onelen <= twolen){
        swap(num1, num2);
        swap(onelen, twolen);
    }
    int addbit = 0;
    for (int i = 0; i < twolen; i++){
        int cur_sum = (num1[i]-'0') + (num2[i]-'0') + addbit;
        output += to_string((cur_sum) % 10);
        addbit = cur_sum < 10 ? 0 : 1;
    }
    for (int i = twolen; i < onelen; i++){
        int cur_sum = (num1[i]-'0') + addbit;
        output += to_string((cur_sum) % 10);
        addbit = cur_sum < 10 ? 0 : 1;
    }
    if (addbit)
        output += "1";
    reverse(output.begin(), output.end());
    return output;
}

‘3’的幂次方

• 题面
• 题解

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true；否则，返回 false。(n为int类型)

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 45
输出：false

有两种方法，一种是利用对数。设 $log_3(n) = m$，如果 n 是 3 的整数次方，那么 m 一定是整数。

bool isPowerOfThree(int n) {
	return fmod(log10(n) / log10(3), 1) == 0;
}

另一种方法是，因为在 int 范围内 3 的最大次方是 $3^{19} = 1162261467$，如果 n 是 3 的整数次方，那么 1162261467 除以 n 的余数一定是零；反之亦然。

bool isPowerOfThree(int n) {
	return n > 0 && 1162261467 % n == 0;
}

随机与取样

打乱数组

• 题面
• 题解

给定一个数组，要求在类中实现两个指令函数。第一个函数“shuffle”可以随机打乱这个数组，第二个函数“reset”可以恢复原来的顺序。

输入是一个存有整数数字的数组，和一个包含指令函数名称的数组。输出是一个二维数组，表示每个指令生成的数组。

Input: nums = [1,2,3], actions: [“shuffle”,”shuffle”,”reset”]
Output: [[2,1,3],[3,2,1],[1,2,3]]
在这个样例中，前两次打乱的结果只要是随机生成即可。

我们采用经典的 Fisher-Yates 洗牌算法，原理是通过随机交换位置来实现随机打乱，有正向和反向两种写法，且实现非常方便。注意这里“reset”函数以及类的构造函数的实现细节。

class Solution {
    vector<int> origin;
    public:
    Solution(vector<int>& nums): origin(nums) {}
    vector<int> reset() {
        return origin;
    }
    vector<int> shuffle() {
        if (origin.empty()) return {};
        vector<int> shuffled(origin);
        int n = origin.size();
        // 反向洗牌：（正向效果相同
        for (int i = n - 1; i >= 0; i--)
            swap(shuffled[i], shuffled[rand() % (i + 1)]);
        return shuffled;
    }
};

或者直接使用random_shuffle()

vector<int> shuffle() {
    if (origin.empty()) return {};
    vector<int> shuffled = origin;
    random_shuffle(shuffled.begin(), shuffled.end());
    return shuffled;
}

按权重随机选择

• 题面
• 题解

给定一个数组，数组每个位置的值表示该位置的权重，要求按照权重的概率去随机采样。

Input: weights = [1,3], actions: [“pickIndex”,”pickIndex”,”pickIndex”]
Output: [0,1,1]

设数组 w 的权重之和为 total。根据题目的要求，我们可以看成将 [1,total] 范围内的所有整数分成 n 个部分（其中 n 是数组 w 的长度），第 i 个部分恰好包含 w[i] 个整数，并且这 n 个部分两两的交集为空。随后我们在 [1,total] 范围内随机选择一个整数 x，如果整数 x 被包含在第 i 个部分内，我们就返回 i。

一种较为简单的划分方法是按照从小到大的顺序依次划分每个部分。例如 w=[3,1,2,4] 时，权重之和 total=10，那么我们按照 [1,3],[4,4],[5,6],[7,10] 对 [1,10] 进行划分，使得它们的长度恰好依次为 3,1,2,4。可以发现，每个区间的左边界是在它之前出现的所有元素的和加上 1，右边界是到它为止的所有元素的和。因此，如果我们用 pre[i] 表示数组 w 的前缀和：

$$pre[i]=\sum_{k=0}^{i}w[k]\\ 第 i 个区间的左边界就是 pre[i]−w[i]+1，右边界为 pre[i]。$$

当划分完成后，假设我们随机到了整数 x，我们希望找到满足：$pre[i]−w[i]+1≤x≤pre[i]$ 的 i 并将其作为答案返回。由于 pre[i] 是单调递增的，因此我们可以使用二分查找快速找到 i，即找出最小的满足 x≤pre[i] 的下标 i。

代码

class Solution {
    vector<int> sums;
    public:
    Solution(vector<int> weights): sums(std::move(weights)) {
        partial_sum(sums.begin(), sums.end(), sums.begin());
    }
    int pickIndex() {
        int pos = (rand() % sums.back()) + 1;
        return lower_bound(sums.begin(), sums.end(), pos) - sums.begin();
    }
};

partial_sum用于计算局部和（start, end, storage)

lower_bound用于找出范围内不小于num的第一个元素（start, end, storage)

链表随机节点

• 题面
• 题解

给定一个单向链表，要求设计一个算法，可以随机取得其中的一个数字。

Input: 1->2->3->4->5
Output: 3

不同于数组，在未遍历完链表前，我们无法知道链表的总长度。这里我们就可以使用水库采样：遍历一次链表，在遍历到第 m 个节点时，有 1/m 的概率选择这个节点覆盖掉之前的节点选择。

我们提供一个简单的，对于水库算法随机性的证明。对于长度为 n 的链表的第 m 个节点，最后被采样的充要条件是它被选择，且之后的节点都没有被选择。这种情况发生的概率为 $\frac{1}{m}\times\frac{m}{m+1}\times\frac{m+1}{m+2}…=\frac{1}{n}$ 因此每个点都有均等的概率被选择。

代码

class Solution {
    ListNode* head;
    public:
    Solution(ListNode* n): head(n) {}
    int getRandom() {
        int ans = head->val;
        ListNode* node = head->next;
        int i = 2;
        while (node) {
            if ((rand() % i) == 0)
                ans = node->val;
            i++;
            node = node->next;
        }
        return ans;
    }
};

练习

Excel表列名称

• 题面
• 题解

给你一个整数 columnNumber，返回它在 Excel 表中相对应的列名称。

例如：

A -> 1
B -> 2
…
Z -> 26
AA -> 27
AB -> 28
…

示例 1：

输入：columnNumber = 1
输出：”A”

示例 2：

输入：columnNumber = 28
输出：”AB”

和正常 0~25 的 26 进制相比，本质上就是每一位多加了 1。假设 A = 0，B = 1，那么 AB = 26 * 0 + 1 * 1，而现在 AB = 26 * (0 + 1) + 1 * (1 + 1)，所以只要在处理每一位的时候减 1，就可以按照正常的 26 进制来处理

代码

string convertToTitle(int columnNumber) {
    string ans;
    while(columnNumber) {
        columnNumber--;
        int re = columnNumber % 26;
        ans.push_back('A' + re);
        columnNumber /= 26;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

二进制求和

• 题面
• 题解

给你两个二进制字符串，返回它们的和（用二进制表示）。输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = “11”, b = “1”
输出: “100”

示例 2:

输入: a = “1010”, b = “1011”
输出: “10101”

翻转，进位计算

代码

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

除自身以外数组的乘积

• 题面
• 题解

给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

L[i] 表示 nums[i] 左侧所有数字的乘积，R[i] 表示右侧，初始化后遍历数组即可

代码

vector<int> productExceptSelf(vector<int>& nums) {
    int length = nums.size();
    vector<int> L(length, 0), R(length, 0);
    vector<int> answer(length);
    L[0] = 1;
    for (int i = 1; i < length; i++)
        L[i] = nums[i - 1] * L[i - 1];
    R[length - 1] = 1;
    for (int i = length - 2; i >= 0; i--)
        R[i] = nums[i + 1] * R[i + 1];
    for (int i = 0; i < length; i++)
        answer[i] = L[i] * R[i];
    return answer;
}

最少移动次数使数组相等II

• 题面
• 题解

给你一个长度为 n 的整数数组 nums，返回使所有数组元素相等需要的最少移动数。在一步操作中，你可以使数组中的一个元素加 1 或者减 1。

示例 1：

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

示例 2：

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

很容易想到，都变成中位数所需移动次数较少，证明为什么用中位数，其实很简单，如果target往两侧偏移，如果一侧数字少一侧数字多，往多的一侧移动必然使得结果减少。直到target两侧的数字数量完全相等时，取得最小值。这里使用快速选择找到 target

代码

int minMoves2(vector<int>& nums) {
    nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
    int target = nums[nums.size()/2], ans = 0;
    for(int& x: nums) 
        ans += abs(x - target);
    return ans;
}

多数元素

• 题面
• 题解

给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 n/2 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

示例 2：

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

Boyer-Moore 投票算法：

1. 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
2. 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
   • 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
   • 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
3. 在遍历完成后，candidate 即为整个数组的众数（这里众数指个数 > n/2)。

这里提供一个比较好理解的证明：

首先遍历数组时，遍历到的人将有一次投票权，相同的数字代表同一个人，在投票中，所有人都是利己的，即只会给自己投支持票，给不是自己的候选人投反对票。对于第一个候选人来说，如果他不是 maj，count迟早会变为 0，因为他自己最多给自己投的票数不超过一半，而其他人都会投反对票；即使反对票全部是 maj 投的（这里是极端情况），那么以 count=0 为分界，前面一段数组中 maj 也只占了一半，所以后面一段数组中众数还是 maj。如果第一个候选人是 maj，若 count 到最后都没有变为 0，当然选出来的就是 maj，若 count 在中间变为 0 了，那么前面一段数组中 maj 没占到一半票数，所以后面一段众数还是 maj。把前面一段丢掉不考虑，继续在后面一段中投票，可以看出是重复上述过程，所以最终候选人一定是是 maj

代码

int majorityElement(vector<int>& nums) {
    int candidate = 0, count = 0;
    for (int num : nums) {
        if (num == candidate)
            count++;
        else if (--count < 0) {
                candidate = num;
                count = 1;
        }
    }
    return candidate;
}

用rand7()实现rand10()

• 题面
• 题解

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

输入: 3
输出: [3,8,10]

两个rand7()相乘，选择概率相等的一些数，映射到 [1,10] 即可；

代码

int rand10() {
    int row, col, idx;
    do {
        row = rand7();
        col = rand7();
        idx = col + (row - 1) * 7;
    } while (idx > 40);
    return 1 + (idx - 1) % 10;
}

快乐数

• 题面
• 题解

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是 无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true；不是，则返回 false。

示例 1：

输入：n = 19
输出：true
解释：
1^1^ + 9^2^ = 82
8^2^ + 2^2^ = 68
6^2^ + 8^2^ = 100
1^2^ + 0^2^ + 0^2^ = 1

对于 3 位数的数字，它不可能大于 $243(3×9^2)$。这意味着它要么被困在 243 以下的循环内，要么跌到 1。4 位或以上的数字在每一步都会丢失一位，直到降到 3 位为止。所以只有两种情况，一是进入循环，二是得到 1。把每个中间数字作为一个节点，可以使用前面章节讲过的快慢指针进行环路检测。如果 n 是一个快乐数，即没有循环，那么快跑者最终会比慢跑者先到达数字 1。如果 n 不是一个快乐的数字，那么最终快跑者和慢跑者将在同一个数字上相遇

代码

int bitSquareSum(int n) {
    int sum = 0;
    while(n > 0) {
        int bit = n % 10;
        sum += bit * bit;
        n = n / 10;
    }
    return sum;
}
bool isHappy(int n) {
    int slow = n, fast = n;
    do {
        slow = bitSquareSum(slow);
        fast = bitSquareSum(fast);
        fast = bitSquareSum(fast);
    } while(slow != fast);
    return slow == 1;
}