数学题：其他

0060. 排列序列 (opens new window)

题目

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

给定 n 和 k，返回第 k 个排列。

解析

从前向后每次从小到大进行尝试，选择一个数字后，此时的排列总数为 (n - i - 1)!，这样可以通过与 k 进行比较逐渐缩小问题的规模，直到选择至最后一个位置。

由于每次尝试都需要计算 (n - i - 1)!，因此可以提前计算好，降低时间复杂度。

代码

class Solution {
public:
    string getPermutation(int n, int k) {
        // 提前计算 1 ~ n 的阶乘
        vector<int> fact(n + 1, 1);
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }

        string ans;
        vector<bool> used(n + 1);
        for (int i = 0; i < n; i++) {
            // 计算当前位置选择后的排列数量：(n - i - 1)!
            int cnt = fact[n - i - 1];

            // 选择一个当前位置的元素
            for (int j = 1; j <= n; j++) {
                if (used[j]) continue;
                if (cnt < k) k -= cnt;
                else {
                    ans += j + '0';
                    used[j] = true;
                    break;
                }
            }
        }
        return ans;
    }
};

0062. 不同路径 (opens new window)

题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

解析

从左上角到右下角的过程中，我们需要移动 $m+n-2$ 次，其中有 $m-1$ 次向下移动, $n-1$ 次向右移动。因此路径的总数，就等于从 $m+n-2$ 次移动中选择 $m-1$ 次向下移动或 $n-1$ 次向右移动的方案数，即组合数 $C_{m+n-2}^{\min\{m,n\}-1}$。

代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long ans = 1;
        for (int i = max(m, n), j = 1; i <= m + n - 2; i++, j++) {
            ans = ans * i / j;
        }
        return ans;
    }
};

0065. 有效数字 (opens new window)

题目

判断一个字符串是否是一个有效数字。

解析

将字符串以 e/E 进行分割后分别判断，规则如下：

• 如果存在 e/E ：左侧可以「整数」或「浮点数」，右侧必须是「整数」；
• 如果不存在 e/E ：整段可以是「整数」或「浮点数」。

关键在于如何实现一个 check 函数用于判断「整数」或「浮点数」：

• +/- 只能出现在头部；
• . 最多出现一次；
• 至少存在一个数字。

代码

class Solution {
public:
    bool isNumber(string s) {
        int idx = -1;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == 'e' || s[i] == 'E') {
                if (idx == -1) idx = i;
                else return false;
            }
        }
        if (idx == -1) {
            return check(s, 0, s.length() - 1, false);
        }
        return check(s, 0, idx - 1, false) && check(s, idx + 1, s.length() - 1, true);
    }

    bool check(string& s, int start, int end, bool mustInt) {
        if (s[start] == '+' || s[start] == '-') start++;
        bool point = false, digit = false;
        for (int i = start; i <= end; i++) {
            if (s[i] == '.') {
                if (point || mustInt) return false;
                point = true;
            } else if (isdigit(s[i])) {
                digit = true;
            } else {
                return false;
            }
        }
        return digit;
    }
};

0166. 分数到小数 (opens new window)

题目

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数 。

如果小数部分为循环小数，则将循环的部分括在括号内。

解析

• 处理正负号，类型转换防止越界
• 处理整数部分
• 处理小数部分，使用 map 记录重复数下标，得到循环小数起始位置

代码

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        string ans = "";

        // 处理正负号，一正一负取负号
        ans.append(((numerator > 0) ^ (denominator > 0)) ? "-" : "");

        // 转换为 long long 防止溢出
        long long num = llabs((long long)numerator);
        long long den = llabs((long long)denominator);

        // 处理整数部分
        ans.append(to_string(num / den));
        num %= den;
        if (num == 0) {
            return ans;
        }

        ans.append(".");

        // 记录出现重复数的下标，将 "(" 插入到重复数前面
        unordered_map<int, int> record;
        record[num] = ans.length();

        while (num) {
            num *= 10;
            ans.append(to_string(num / den));
            num %= den;
            if (record.find(num) != record.end()) {
                int idx = record[num];
                ans.insert(idx, "(");
                ans.append(")");
                break;
            } else {
                record[num] = ans.length();
            }
        }

        return ans;
    }
};

0172. 阶乘后的零 (opens new window)

题目

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

解析

尾数中的 $0$ 是由因子的 $10 = 2 \times 5$ 构成，由于因子 $2$ 的数量一定会比 $5$ 多，因此只需统计 $1$ 到 $n$ 中因子 $5$ 的数量即可。

以 $100!$ 为例，$100 / 5 = 20$ 个因子，分别是 $5,10,15,20,25, \dots ,95,100$。

但由于其中有四个因子 $25 = 5 \times 5, 50 = 2 \times 5 \times 5, 75 = 3 \times 5 \times 5, 100 = 4 \times 5 \times 5$，会存在额外的因子 $5$。

故 $100!$ 中因子 $5$ 的数量的计算公式为：

$100 / 5 + 100 / 25 = 20 + 4 = 24$

可通过递归简化代码：

$100 / 5 = 20, 20 + 20 / 5 = 24$

代码

class Solution {
public:
    int trailingZeroes(int n) {
        return n < 5 ? 0 : n / 5 + trailingZeroes(n / 5);
    }
};

0483. 最小好进制 (opens new window)

题目

对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。

以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。

解析

假设正整数 $n$ 在 $k(k \geq 2)$ 进制下的所有数位都为 1, 且位数为 $m+1$, 那么有：

$n=k^{0}+k^{1}+k^{2}+\cdots+k^{m}$

我们首先讨论两种特殊情况：

• $m=0$，此时 $n=1$，而题目保证 $n \geq 3$，所以本题中 $m>0$。
• $m=1$，此时 $n=(11)_k$，即 $k=n-1 \geq 2$，这保证了本题有解。

然后我们分别证明一般情况下的两个结论，以帮助解决本题。

结论一：$m<\log _{k} n$

注意到等式右侧是一个首项为 1、公比为 $k$ 的等比数列，利用等比数列求和公式，我们可以得到：

$n=\frac{1-k^{m+1}}{1-k}$

对公式进行变换可得:

$k^{m+1}=k n-n+1<k n$

移项并化简可得：

$m<\log _{k} n$

这个结论帮助我们限制了 $m$ 的范围, 本题中 $3 \leq n \leq 10^{18}$ 且 $k \geq 2$，所以 $m<\log _{2} 10^{18}<60$。

结论二：$k=\lfloor\sqrt[m]{n}\rfloor$

依据等式，可知：

$n=k^{0}+k^{1}+k^{2}+\cdots+k^{m}>k^{m}$

依据二项式定理可知：

$(k+1)^{m}=C_{m}^{0}k^{0}+C_{m}^{1}k^{1}+C_{m}^{2}k^{2}+\cdots+C_{m}^{m}k^{m}$

因为当 $m>1$ 时，$\forall i \in[1, m-1],C_{m}^{i}>1$，所以有

$\begin{aligned} (k+1)^{m} &=C_{m}^{0}k^{0}+C_{m}^{1}k^{1}+C_{m}^{2}k^{2}+\cdots+C_{m}^{m}k^{m} \\ &>k^{0}+k^{1}+k^{2}+\cdots+k^{m}=n \end{aligned}$

结合两不等式可知，当 $m>1$ 时, 有 $k^{m}<n<(k+1)^{m}$，两边同时开方得：

$k<\sqrt[m]{n}<k+1$

依据这个公式我们知道，$\sqrt[m]{n}$ 必然为一个小数，且 $k$ 为 $\sqrt[m]{n}$ 的整数部分，即 $k=\lfloor\sqrt[m]{n}\rfloor$。

这个结论帮助我们在 $n$ 和 $m$ 已知的情况下快速确定 $k$ 的值。

综合上述两个结论，依据结论一，我们知道 $m$ 的取值范围为 $\left[1, \log _{k} n\right)$，且 $m=1$ 时必然有解。因为随着 $m$ 的增大，$k$ 不断减小，所以我们只需要从大到小检查每一个 $m$ 可能的取值，利用结论二快速算出对应的 $k$ 值，然后校验计算出的 $k$ 值是否有效即可。

代码

class Solution {
public:
    string smallestGoodBase(string n) {
        long num = stol(n);
        int maxM = floor(log(num) / log(2));
        for (int m = maxM; m >= 2; m --) {
            int k = pow(num, 1.0 / m);
            long sum = 1, cur = 1;
            for (int i = 0; i < m; i ++) {
                cur *= k;
                sum += cur;
            }
            if (sum == num) {
                return to_string(k);
            }
        }
        return to_string(num - 1);
    }
};