跳到主要内容

数学题

问题​

Java 面试中常见的数学相关算法题有哪些？

答案​

最大公约数（GCD）​

辗转相除法
public int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 最小公倍数
public int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // 先除再乘防溢出
}

判断质数 / 埃氏筛​

统计质数（LeetCode 204）
public int countPrimes(int n) {
    boolean[] notPrime = new boolean[n];
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (!notPrime[i]) {
            count++;
            // 从 i*i 开始标记（之前的已被更小的质数标记过）
            for (long j = (long) i * i; j < n; j += i) {
                notPrime[(int) j] = true;
            }
        }
    }
    return count;
}

阶乘后的零（LeetCode 172）​

统计因子 5 的个数
public int trailingZeroes(int n) {
    int count = 0;
    while (n >= 5) {
        n /= 5;
        count += n;  // 5 的倍数、25 的倍数、125 的倍数...
    }
    return count;
}

快速幂（LeetCode 50）​

O(log n) 幂运算
public long quickPow(long base, long exp, long mod) {
    long result = 1;
    base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

整数反转（LeetCode 7）​

数学方法反转，注意溢出
public int reverse(int x) {
    int result = 0;
    while (x != 0) {
        int digit = x % 10;
        // 溢出检查
        if (result > Integer.MAX_VALUE / 10 || result < Integer.MIN_VALUE / 10) return 0;
        result = result * 10 + digit;
        x /= 10;
    }
    return result;
}

回文数（LeetCode 9）​

反转一半数字
public boolean isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    int reversed = 0;
    while (x > reversed) {
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }
    return x == reversed || x == reversed / 10;
}

丑数（LeetCode 264）​

三指针归并
public int nthUglyNumber(int n) {
    int[] dp = new int[n];
    dp[0] = 1;
    int i2 = 0, i3 = 0, i5 = 0;
    for (int i = 1; i < n; i++) {
        int next = Math.min(dp[i2] * 2, Math.min(dp[i3] * 3, dp[i5] * 5));
        dp[i] = next;
        if (next == dp[i2] * 2) i2++;
        if (next == dp[i3] * 3) i3++;
        if (next == dp[i5] * 5) i5++;
    }
    return dp[n - 1];
}

常见面试问题​

Q1: Java 整数溢出怎么处理？​

答案：

  • 提前判断：result > Integer.MAX_VALUE / 10 则溢出
  • 用 long 临时存储再判断
  • 用 Math.addExact() / Math.multiplyExact() 抛异常

Q2: 取模运算的性质？​

答案：

  • (a + b) % m = ((a % m) + (b % m)) % m
  • (a * b) % m = ((a % m) * (b % m)) % m
  • 快速幂中每步取模，防止 long 溢出

相关链接​