279 Perfect Squares

Search…
279 Perfect Squares
279. Perfect Squares​
1. Question
Given a positive integern, find the least number of perfect square numbers (for example,1, 4, 9, 16, ...) which sum ton.
For example, givenn=12, return3because12 = 4 + 4 + 4; givenn=13, return2because13 = 4 + 9.
2. Implementation
(1) BFS
1
class Solution {
2
    public int numSquares(int n) {
3
        int upperBound = (int)Math.sqrt(n);
4
        int[] squares = new int[upperBound];
5
​
6
        for (int i = 1; i <= upperBound; i++) {
7
            squares[i - 1] = i * i;
8
        }
9
​
10
        Queue<Integer> queue = new LinkedList<>();
11
        queue.add(0);
12
​
13
        boolean[] visited = new boolean[n + 1];
14
        int level = 0;
15
​
16
        while (!queue.isEmpty()) {
17
            int size = queue.size();
18
            ++level;
19
​
20
            for (int i = 0; i < size; i++) {
21
                int curNum = queue.remove();
22
                visited[curNum] = true;
23
​
24
                for (int square : squares) {
25
                    int nextNum = curNum + square;
26
​
27
                    if (nextNum > n) {
28
                        break;
29
                    }
30
                    else if (nextNum == n) {
31
                        return level;
32
                    }
33
                    else if (!visited[nextNum]) {
34
                        queue.add(nextNum);
35
                    }
36
                }
37
            }
38
        }
39
        return level;
40
    }
41
}
Copied!
(2) DP
1
class Solution {
2
    public int numSquares(int n) {
3
        int[] dp = new int[n + 1];
4
        Arrays.fill(dp, Integer.MAX_VALUE);
5
        dp[0] = 0;
6
​
7
        for (int i = 1; i <= n; i++) {
8
            for (int j = 1; j <= (int)Math.sqrt(i); j++) {
9
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
10
            }
11
        }
12
        return dp[n];
13
    }
14
}
Copied!
(3) Memoization
1
public class Solution {
2
    public int numSquares(int n) {
3
        int[] cache = new int[n + 1];
4
        return dfs(n, cache);
5
    }
6
​
7
    public int dfs(int n, int[] cache) {
8
        if (n == 0) {
9
            return 0;
10
        }
11
​
12
        if (n == 1) {
13
            return 1;
14
        }
15
​
16
        if (cache[n] != 0) {
17
            return cache[n];
18
        }
19
​
20
        int num = Integer.MAX_VALUE;
21
​
22
        for (int i = 1; i * i <= n; i++) {
23
            num = Math.min(num, dfs(n - i * i, cache) + 1);
24
        }
25
        cache[n] = num;
26
        return num;
27
    }
28
}
Copied!
3. Time & Space Complexity
BFS: 时间复杂度O(n * sqrt(n)), 空间复杂度O(n)
DP: 时间复杂度O(n * sqrt(n)), 空间复杂度O(n)
Memoization: 时间复杂度O(n * sqrt(n)), 空间复杂度O(n)
130 Surrounded Regions
286 Walls and Gates
Last modified 2yr ago
Copy link
Contents
279. Perfect Squares
1. Question
2. Implementation
3. Time & Space Complexity
279. Perfect Squares​

1. Question

2. Implementation

3. Time & Space Complexity

279. Perfect Squares
