LeetCode 279. Perfect Squares

Posted on Edited on In 
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
class Solution {
public:
    int numSquares(int n) {
        if (n < 2) return n;
        vector<int> v;
        for (int x = 1; x * x <= n; ++x)
            v.emplace_back(x * x);
        if (v.back() == n) return 1;
        queue<int> q;
        vector<bool> visited(n);
        for (auto x : v) {
            q.push(x);
            visited[x] = true;
        }
        int steps = 1;
        while (!q.empty()) {
            ++steps;
            int size = q.size();
            while (size--) {
                int x = q.front(); q.pop();
                for (auto y : v) {
                    int next = x + y;
                    if (next == n) {
                        return steps;
                    } else if (next < n && !visited[next]) {
                        q.push(next);
                        visited[next] = true;
                    } else if (next > n) {
                        break;
                    }
                }
            }
        }
        return 0;
    }
};
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
class Solution {
public:
    int numSquares(int n) {
        vector<int> v;
        int t = 1;
        while (t * t <= n) {
            v.emplace_back(t * t);
            ++t;
        }
        int m = v.size();
        vector<vector<int>> f(m + 1, vector<int>(n + 1, n));
        f[0][0] = 0;
        for (int i = 1; i <= m; ++i) {
            int x = v[i - 1];
            for (int j = 0; j <= n; ++j) {
                f[i][j] = f[i - 1][j];
                for (int k = 1; k * x <= j; ++k) {
                    if (f[i - 1][j - k * x] != n) {
                        f[i][j] = min(f[i][j], f[i - 1][j - k * x] + k);
                    }
                }
            }
        }
        return f[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1, n);
        f[0] = 0;
        for (int t = 1; t * t <= n; ++t) {
            int x = t * t;
            for (int j = x; j <= n; ++j)
                f[j] = min(f[j], f[j - x] + 1);
        }
        return f[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isPerfectSquare(int n) {
        int x = sqrt(n);
        return x * x == n;
    }
    bool checkAnswer4(int n) {
        while (n % 4 == 0)
            n /= 4;
        return n % 8 == 7;
    }
    int numSquares(int n) {
        if (isPerfectSquare(n)) return 1;
        if (checkAnswer4(n)) return 4;
        for (int i = 1; i * i <= n; ++i)
            if (isPerfectSquare(n - i * i))
                return 2;
        return 3;
    }
}; // Lagrange's Four-Square Theorem