C语言 | Leetcode C语言题解之第279题完全平方数

题目：

题解：

// 判断是否为完全平方数
bool isPerfectSquare(int x) {
    int y = sqrt(x);
    return y * y == x;
}

// 判断是否能表示为 4^k*(8m+7)
bool checkAnswer4(int x) {
    while (x % 4 == 0) {
        x /= 4;
    }
    return x % 8 == 7;
}

int numSquares(int n) {
    if (isPerfectSquare(n)) {
        return 1;
    }
    if (checkAnswer4(n)) {
        return 4;
    }
    for (int i = 1; i * i <= n; i++) {
        int j = n - i * i;
        if (isPerfectSquare(j)) {
            return 2;
        }
    }
    return 3;
}