面试经典 150 题-数学

LeetCode 面试经典 150 题-数学

回文数

分析

反转整数，再进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isPalindrome(int x) {
        // 边界处理，负数一定不是回文数
        if (x < 0) {
            return false;
        }
        long ans = 0l;
        int cur = x;
        while (cur != 0) {
            ans = ans * 10 + cur % 10;
            cur = cur / 10;
        }
        return x == ans;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

反转一半数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isPalindrome(int x) {
        // 边界处理，负数一定不是回文数
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        int ans = 0;
        while (x > ans) {
            ans = ans * 10 + x % 10;
            x = x / 10;
        }
        return x == ans || x == ans / 10;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

加一

分析

先加到nums.length-1上，如果有进位产生再向前加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        if (digits[n - 1] != 9) {
            digits[n - 1]++;
            return digits;
        }
        // 对于有进位产生的情况
        List<Integer> ans = new ArrayList<>();
        int carry = 1;
        ans.add(0);
        for (int i = n - 2; i >= 0; i--) {
            int sum = digits[i] + carry;
            ans.add(0, sum % 10);
            carry = sum / 10;
        }
        if (carry != 0) {
            ans.add(0, carry);
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

学习一下别人的写法简洁高效

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;
            if (digits[i] != 0) return digits;  // 说明没有进位产生
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

阶乘后的零

数学

n! 尾零的数量即为 n! 中因子 10 的个数，而 10=2×5，因此转换成求 n! 中质因子 2 的个数和质因子 5 的个数的较小值。可以通过不断将 n 除以 5，并累加每次除后的 n，来得到答案。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int trailingZeroes(int n) {
        int ans = 0;
        while (n != 0) {
            n /= 5;
            ans += n;
        }
        return ans;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

x的平方根

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        
        int left = 1, right = x;
        
        // 使用二分查找法来找平方根
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long square = (long) mid * mid;  // 使用 long 来避免溢出
            
            if (square == x) {
                return mid;  // 找到精确的平方根
            } else if (square < x) {
                left = mid + 1;  // mid 太小，调整左边界
            } else {
                right = mid - 1;  // mid 太大，调整右边界
            }
        }
        
        return right;  // 当退出循环时，right 是最大的整数，满足 right^2 <= x
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

牛顿迭代法

逼近$f(x)=x^2 − n=0$这个方程的根。

  1. C 被初始化为 x，这是我们要计算平方根的数；x0 代表初始猜测的值，也设为 x。
  2. xi 是通过牛顿迭代公式计算得到的新猜测值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

POW(x,n)

暴力法

无法通过全部测试用例。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public double myPow(double x, int n) {
        double ans = 1;
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        for (int i = 0; i < n; i++) {
            ans *= x;
        }
        return ans;
    }
}

快速幂+递归

  • 当我们要计算$x^n$时，我们可以先递归地计算出 y=x ⌊n/2⌋，其中 ⌊a⌋ 表示对 a 进行下取整；
  • 根据递归计算的结果，如果 n 为偶数，那么$x^n = y^2$；如果 n 为奇数，那么$x^n = y^2*x$；
  • 递归的边界为 n=0，任意数的 0 次方均为 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, n) : 1.0 / quickMul(x, -n);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(logn)

快速幂 + 迭代

将 n 转换为 long 类型，这样做是为了处理 n 为 Integer.MIN_VALUE（即 -2147483648）的特殊情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        double ans = 1.0;
        double x_contribute = x;
        while (N > 0) {
            // 对n进行拆分同时计算答案
            if (N % 2 == 1) {
                ans *= x_contribute;
            }
            x_contribute *= x_contribute;
            N /= 2;
        }
        return ans;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

直线上最多的点数

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    public int maxPoints(int[][] points) {
        // 边界处理
        int n = points.length;
        if (n <= 2) {
            return n;
        }
        // 遍历每个坐标
        int ans = 0;
        for (int i = 0; i < n; i++) {
            // 超过一半的点
            if (ans >= n - i || ans > n / 2) {
                break;
            }
            // 使用哈希表记录斜率
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            // 计算i点和之后所有点的斜率
            for (int j = i + 1; j < n; j++) {
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                if (x == 0) {
                    y = 1;
                } else if (y == 0) {
                    x = 1;
                } else {
                    if (y < 0) {
                        x = -x;
                        y = -y;
                    }
                    int gcdXY = gcd(Math.abs(x), Math.abs(y));
                    x /= gcdXY;
                    y /= gcdXY;
                }
                // 转换成唯一键
                int key = y + x * 20001;
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
            // 找到最大共线点数
            int maxNum = 0;
            for (int key : map.keySet()) {
                maxNum = Math.max(maxNum, map.get(key) + 1);
            }
            ans = Math.max(ans, maxNum);
        }
        return ans;
    }

    // 求最大公约数
    public int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}
  • 时间复杂度：$O(n^2 \times logm)$其中 n 为点的数量，m 为横纵坐标差的最大值。最坏情况下我们需要枚举所有 n 个点，枚举单个点过程中需要进行 O(n) 次最大公约数计算，单次最大公约数计算的时间复杂度是 O(logm)。
  • 空间复杂度：O(n)，哈希表消耗。
算法笔记 > 数学
#数学
面试经典 150 题-数学
http://example.com/2025/03/07/posts/hot150-17/
作者
Xuan Yang
发布于
2025年3月7日
许可协议