数学

数学题目涉及进位模拟、回文判断、质因数分解、对数等。

9. 回文数 (Palindrome Number)

题目描述

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数 是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

• 例如，121 是回文，而 123 不是。

解题思路

数字反转对比。

1. 边界：负数一定不回文；以 0 结尾（除 0 外）一定不回文。
2. 将 x 后半部分反转。
3. 如果 x == revertedNumber 或 x == revertedNumber / 10。

Java 代码实现

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int rev = 0;
        while (x > rev) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return x == rev || x == rev / 10;
    }
}

---

66. 加一 (Plus One)

题目描述

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

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

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

解题思路

倒序处理进位。

1. 从后往前遍历。
2. 如果 digits[i] < 9，则 digits[i]++ 并立即返回 digits（无进位）。
3. 否则 digits[i] = 0，继续循环处理高位。
4. 如果遍历结束仍有进位（如 99 -> 100），新建长度 +1 数组，首位设为 1。

Java 代码实现

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        int[] res = new int[digits.length + 1];
        res[0] = 1;
        return res;
    }
}

---

172. 阶乘后的零 (Factorial Trailing Zeroes)

题目描述

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

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

解题思路

统计因子 5 的个数。

1. 乘积中 0 的来源是 $2 \times 5$。
2. 在阶乘中因子 2 的数量远多于因子 5。
3. 统计 $1 \dots n$ 中因子 5 的总个数。
4. 即 $n/5 + n/25 + n/125 \dots$。

Java 代码实现

class Solution {
    public int trailingZeroes(int n) {
        int cnt = 0;
        while (n > 0) {
            n /= 5;
            cnt += n;
        }
        return cnt;
    }
}

---

69. x 的平方根 (Sqrt(x))

题目描述

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者角标符号 x ^ 0.5 。

解题思路

二分查找 / 牛顿迭代法。

1. $L = 0, R = x$。
2. 循环 while (L <= R)。
3. mid = (L + R) / 2。
4. 检查 mid * mid <= x（为防溢出用 mid <= x / mid）。

Java 代码实现

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int l = 1, r = x;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (mid <= x / mid) l = mid + 1;
            else r = mid - 1;
        }
        return l - 1;
    }
}

---

50. Pow(x, n)

题目描述

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

解题思路

快速幂 (Divide and Conquer)。

1. 如果 $n$ 为负数，转为 $1/x$ 且 $n$ 转为正数（注意 Integer.MIN_VALUE 溢出）。
2. $pow(x, n) = pow(x, n/2) \dots$。

Java 代码实现

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) { x = 1 / x; N = -N; }
        double res = 1;
        while (N > 0) {
            if (N % 2 == 1) res *= x;
            x *= x;
            N /= 2;
        }
        return res;
    }
}

---

149. 直线上最多的点数 (Max Points on a Line)

题目描述

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

解题思路

枚举起点 + 斜率统计。

1. 任意两点确定一条直线。
2. 固定一个点 i，枚举之后的所有点 j。
3. 计算 i 和 j 之间的斜率。
4. 斜率可以用 (xi - xj) / (yi - yj) 表示，但为了避免浮点精度问题，通常用 约分后的分数对 (dx, dy) 作为哈希表的 Key。
   • gcd = GCD(dx, dy)，斜率特征为 (dx/gcd, dy/gcd)。
5. 哈希表统计每种斜率出现的次数，取最大值加 1（即点 i 本身）。

Java 代码实现

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) return n;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (res >= n - i || res > n / 2) break; // 优化
            Map<String, Integer> map = new HashMap<>();
            for (int j = i + 1; j < n; j++) {
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                int g = gcd(x, y);
                String key = (x / g) + "_" + (y / g);
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
            int max = 0;
            for (int val : map.values()) max = Math.max(max, val);
            res = Math.max(res, max + 1);
        }
        return res;
    }
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}