数学题：开方

0050. Pow(x, n) (opens new window)

题目

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

解析

快速幂。

快速幂算法，见 算法模板：快速幂。

代码

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (n < 0) N = -N;
        double ans = 1.0;
        while (N) {
            if (N & 1) ans *= x;
            x *= x;
            N >>= 1;
        }
        return n < 0 ? 1 / ans : ans;
    }
};

0367. 有效的完全平方数 (opens new window)

题目

给定一个正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true，否则返回 false。

解析

二分法。

注意

需要设置 mid 的类型为 long，因为在计算 mid * mid 时可能导致溢出。

代码

class Solution {
public:
    bool isPerfectSquare(int num) {
        int low = 1, high = num;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (mid * mid == num) {
                return true;
            } else if (mid * mid < num) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return false;
    }
};

0507. 完美数 (opens new window)

题目

对于一个正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为「完美数」。

给定一个整数 n， 如果是完美数，返回 true，否则返回 false。

解析

找出所有正因子相加，最后判断是否相等即可。

代码

class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num == 1) return false;
        int sum = 1;
        for (int i = 2; i <= sqrt(num); i ++) {
            if (num % i == 0) {
                sum += i + num / i;
            }
        }
        return sum == num;
    }
};