279PerfectSquares.org

[#B] Perfect Squares - LeetCode

题目

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

• 1 <= n <= 10⁴

思路

1. 可以看成是图的层序遍历，最先把 n 减到 0 的就是最短路径
2. 可以使用动态规划

层序遍历

CPP

class Solution {
public:
    int numSquares(int n) {
        queue<pair<int, int>> q;
    
        vector<bool> visted(n + 1, false);
        visted[n] = true;
    
        q.push(make_pair(n, 0));
    
        while (!q.empty()) {
            int num = q.front().first;
            int step = q.front().second;
            q.pop();
            for (int i = 1; ; i++) {
                int a = num - i * i;
                if (a < 0) break;
                if (a == 0) return step + 1;
                if (!visted[a]) {
                    q.push(make_pair(a, step + 1));
                    visted[a] = true;
                }
            
            }
        }
        throw invalid_argument("No Solution");
    }
};

Java

   class Solution {
       public int numSquares(int n) {
           Queue<Integer> q = new LinkedList();
           Set<Integer> visted = new HashSet();
           q.offer(n);
           int level = 0;
           while (!q.isEmpty()) {
               level++;
               int size = q.size();
               for (int j = 0; j < size; j++) {
                   int num = q.poll();
                   for (int i = 1; ;i++){
                       int a = num - i * i;
                       if (a < 0) break;
                       if (a == 0) return level;
                       if (!visted.contains(a)) {
                           q.offer(a);
                           visted.add(a);
                       }
                   }
               }
           }
           return -1;
       }
}

动态规划

Java

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            dp[i] = i; // 次数最多就是 1 + 1 + 1，1的个数最多和自己一样
            for (int j = 1; i - j * j >= 0; ++j) {
                // 把 i 拆成 （i - j * j) 和 （j * j) 两部分
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 状态转移方程，其实应该是 dp[i - j * j] + dp[j * j] 由于 dp[j * j] 是等于 1，所以简写成 +1，因为 j * j 就是完全平方数，所以它就只有一种情况。
            }
        }
        return dp[n];
    }
}

CPP

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp = vector<int>(n + 1);
        for (int i = 1; i <= n; ++i) {
            dp[i] = i;
            for (int j = 1; i - j * j >= 0; ++j) {
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
};