数论

Tips

数论的题目一般都比较恶心

• 加减乘都可以在计算过程中取模, 除法要用逆元

进制

66. 加一 easy

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        int rem = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (rem + digits[i] > 9) {
                digits[i] = (rem + digits[i]) % 10;
            } else {
                digits[i] += rem;
                return digits;
            }
        }

        int[] arr = new int[n + 1];
        arr[0] = rem;
        System.arraycopy(digits, 0, arr, 1, n);
        return arr;
    }
}

67. 二进制求和 easy

LCR 002. 二进制求和

给你两个二进制字符串 a 和 b，以二进制字符串的形式返回它们的和。

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1;
        int z = 0;
        while (i >= 0 || j >= 0 || z > 0) {
            int x = 0, y = 0;
            if (i >= 0) x = a.charAt(i--) - '0';
            if (j >= 0) y = b.charAt(j--) - '0';
            sb.append((x + y + z) % 2);
            z = (x + y + z) >> 1;
        }
        return sb.reverse().toString();
    }
}

171. Excel 表列序号 easy

给你一个字符串 columnTitle，表示 Excel 表格中的列名称。返回 该列名称对应的列序号。

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...

26 进制

class Solution {
    public int titleToNumber(String columnTitle) {
        int res = 0;
        for (int i = 0; i < columnTitle.length(); i++) {
            res *= 26;
            res += columnTitle.charAt(i) - 'A' + 1;
        }
        return res;
    }
}

数字逆序

7. 整数反转 mid

给你一个 32 位的有符号整数 x，返回将 x 中的数字部分反转后的结果。
Given a signed 32-bit integer x, return x with its digits reversed.

如果反转后整数超过 32 位的有符号整数的范围 $ [−2^{31}, 2^{31}− 1] $，就返回 0。
If reversing x causes the value to go outside the signed 32-bit integer range $ [−2^{31}, 2^{31}− 1] $, then return 0.

假设环境不允许存储 64 位整数（有符号或无符号）。
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

超出范围的判定, 只要倒数第 2 次不溢出, 最后 1 次不会溢出

java

class Solution {
    public int reverse(int x) {
        int res = 0;

        while (x != 0) {
            // -2147483648 +2147483647
            // 负数:最后的余数(原最高位)范围是[-2,-1], 显然大于-8, 不会溢出; 正数:最后的余数(原最高位)范围是[1,2], 显然小于7, 不会溢出;
            // 所以只要倒数第2次不溢出, 最后1次不会溢出
            if (res < Integer.MIN_VALUE / 10 || res > Integer.MAX_VALUE / 10)
                return 0;

            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
}

go

func reverse(x int) int {
    // -2147483648～2147483647
    var res int = 0
    for ; x != 0; x /= 10 {
        if res < -214748364 || res > 214748364 {
            return 0
        }
        res = res * 10 + x % 10
    }
    return res
}

9. 回文数 easy

给你一个整数 x，如果 x 是一个回文整数，返回 true；否则，返回 false。
Given an integer x, return true if x is a palindrome, and false otherwise.

解法 1 使用字符串硬解

class Solution {
    public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        int p1 = 0, p2 = s.length() - 1;
        while (p1 < p2) {
            if (s.charAt(p1) != s.charAt(p2)) return false;
            p1++;
            p2--;
        }
        return true;
    }
}

解法 2 不使用字符串

可以将数字分成两半, 后半段逆置, 然后对比分成两半的数字是否相等
当数字的位数为奇数, 我们可以将长的前半段的末位截掉后, 再对比

java

class Solution {
    public boolean isPalindrome(int x) {
        // 如果数字的最后一位是 0，则其第一位数字也应该是 0; 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;

        int number = 0;
        // 后半截逆置
        while (x > number) {
            number = number * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 number/10 去除处于中位的数字。
        return x == number || x == number / 10;
    }
}

go

func isPalindrome(x int) bool {
    if x < 0 || x%10 == 0 && x != 0 {
        return false
    }
    num := 0
    for x > num {
        num = num*10 + x%10
        x /= 10
    }
    return x == num || x == num/10
}

罗马数字

13. 罗马数字转整数 easy

比较烂的一道题, 罗马数字前一个比后一个小的话, 表示要减掉前面的

class Solution {
    public int romanToInt(String s) {
        int i = 0;
        int res = 0;
        char[] arr = s.toCharArray();
        int n = arr.length;
        while (i < n) {
            int v = map(arr[i]);
            if (i < n - 1 && v < map(arr[i + 1]))
                res -= v;
            else
                res += v;
            i++;
        }
        return res;
    }

    private int map(char c) {
        return switch (c) {
            case 'I' -> 1;
            case 'V' -> 5;
            case 'X' -> 10;
            case 'L' -> 50;
            case 'C' -> 100;
            case 'D' -> 500;
            case 'M' -> 1000;
            default -> 0;
        };
    }
}

快速幂

50. Pow(x, n) mid

剑指 Offer 16. 数值的整数次方

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，$x^n$)。

指数可以用 2 进制表示
$x^n=x^{2^k+2^{k-1}+...+2^0}=x^{2^k}\ast x^{2^{k-1}}\ast ...\ast x^1$
有 $x^n=x^{\frac{n}{2}}\ast x^{\frac{n}{2}}$, 每次 n>>1 都会让幂的 2 进制表示变短

解法 1 递归

class Solution {
    public double myPow(double x, int n) {
        return n >= 0 ? pow(x, n) : 1 / pow(x, -(long) n);
    }

    private double pow(double x, long n) {
        if (n == 0) return 1;
        double y = pow(x, n >> 1);
        return n % 2 == 0 ? y * y : y * y * x;
    }
}

解法 2 迭代

class Solution {
    public double myPow(double x, int n) {
        return n >= 0 ? quickMul(x, n) : 1.0 / quickMul(x, -(long) n);
    }

    public double quickMul(double x, long n) {
        double res = 1.0;
        while (n > 0) {
            if (n % 2 == 1) res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
}

求数量

172. 阶乘后的零 mid

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

就是求因子 5 的个数 从 5 开始计数, count 5 的倍数中因子 5 的个数

class Solution {
    public int trailingZeroes(int n) {
        int res = 0;
        for (int num = 5; num <= n; num += 5) {
            int t = num;
            while (t % 5 == 0) {
                t /= 5;
                res++;
            }
        }
        return res;
    }
}

233. 数字 1 的个数 hard

剑指 Offer 43. 1 ～ n 整数中 1 出现的次数

例如，输入 12，1 ～ 12 这些整数中包含 1 的数字有 1,10,11,12, 1 一共出现了 5 次。

解法 1 按位处理

枚举每个位置
某个位置前面的数字与后面的数字组合的笛卡尔积
分两部分计算, 按前面最近的 1 位是否限制分类讨论, 然后相加
123?
12?4
1?34
?234

class Solution {
    public int countDigitOne(int n) {
        long res = 0;
        for (long mulk = 1; mulk <= n; mulk *= 10) {
            res += n / (mulk * 10) * mulk;
            // 某个位置的值
            long loc = n % (mulk * 10) / mulk;
            if (loc == 1) // 如果是1, 只加后面的
                res += n % mulk + 1;
            else if (loc > 1) // 如果比1大, 加10^k
                res += mulk;
        }
        return (int) res;
    }
}

解法 2 数位 dp

数位 dp 的状态表示: 在某一位, 前面选中了 mask 集合, 在受限或不受限的前提下, 共多少种可能
数位 dp 的 dfs()需要关注几个维度, 维度==参数:

1. 当前是哪一位
2. 前面选了什么
3. 前 1 位是否最大,导致当前位受限

java

class Solution {

    private char[] s;
    // cache 存的是不受限的数量
    private Integer[][] cache;

    public int countDigitOne(int x) {
        s = Integer.toString(x).toCharArray();
        int n = s.length;
        cache = new Integer[n][n];
        return dfs(0, 0, true);
    }

    // idx前填了cnt个1的前提下, 共出现多少次1
    private int dfs(int idx, int cnt1, boolean isLimit) {
        // 前面选了几个就是几个
        if (idx == s.length) return cnt1;
        // cache
        if (!isLimit && cache[idx][cnt1] != null) return cache[idx][cnt1];
        int res = 0;
        // 位可选的上界
        int up = isLimit ? s[idx] - '0' : 9;
        // 枚举要填入的数字
        for (int i = 0; i <= up; i++) {
            res += dfs(idx + 1,
                    cnt1 + (i == 1 ? 1 : 0),
                    isLimit && (i == up));
        }
        // cache
        if (!isLimit) cache[idx][cnt1] = res;
        return res;
    }
}

python

class Solution:
    def countDigitOne(self, n: int) -> int:
        s = str(n)

        @cache
        def dfs(idx: int, cnt1: int, is_limit: bool) -> int:
            if idx == len(s):
                return cnt1
            res = 0
            up = int(s[idx]) if is_limit else 9
            for i in range(up + 1):
                res += dfs(idx + 1, cnt1 + (i == 1), is_limit and i == up)
            return res

        return dfs(0, 0, True)

338. 比特位计数 easy

LCR 003. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

解法 DP

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}

拆分

343. 整数拆分 mid

剑指 Offer 14- I. 剪绳子

给定一个正整数 n，将其拆分为 k 个 正整数 的和(k >= 2)，并使这些整数的乘积最大化。

返回 你可以获得的最大乘积。

解法 1 数学$O(1)$

分为尽可能多的 3 如果余数为 1 则拆分 3+1 为 2+2

证明: 最优方案中:

1. 不会出现大于 4 的数
   $x>2\mathrm{时},2(x-2)>x$
2. 最优方案中 不会出现 4
   $4=2\ast 2$
3. n >= 4 时，不会出现 1
   $(x-1)\ast 1<(x-2)\ast 2$
4. 当 n ≥ 5 时，2 的个数不会超过 3 个
   $3\times 3>2\times 2\times 2$

class Solution {
    public int integerBreak(int n) {
        if (n <= 3) return n - 1;
        int mod = n % 3;
        int res = pow(3, n / 3);
        switch (mod) {
            case 0:
                break;
            case 2:
                res *= 2;
                break;
            case 1:
                res = res / 3 * 4;
        }
        return res;
    }

    private int pow(int x, int n) {
        if (n == 0) return 1;
        if (n == 1) return x;
        int y = pow(x, n / 2);
        return n % 2 == 0 ? y * y : y * y * x;
    }
}

解法 2 DP$O(n^2)$

记忆拆分后的最大积, 注意, 是拆分后的

class Solution {
    public int integerBreak(int n) {
        // 分拆, (1, n-1) -> (n-1, 1)
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            // 枚举 1 => n-1
            for (int j = i - 1; j >= 1; j--) {
                curMax = max(curMax,
                        j * (i - j),// 不拆
                        j * dp[i - j]);// 拆
            }
            dp[i] = curMax;
        }
        return dp[n];
    }

    private int max(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }
}