LeetCode279-完全平方数

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/perfect-squares/

中文链接：https://leetcode-cn.com/problems/perfect-squares/

题目详述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

1
2
3
输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

1
2
3
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

题目详解

方法一：BFS，时间复杂度 O(n√n)。

可以将每个整数看成图中的一个结点，如果两个整数之差为一个平方数，那么这两个整数所在的结点就有一条边。

要求解最小的平方数数量，就是求解从结点 n 到结点 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
public class LeetCode_00279 {

    public int numSquares(int n) {
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[] vis = new boolean[n + 1];
        queue.offer(new int[]{n, 0});
        vis[n] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 1; ; ++i) {
                int x = cur[0] - i * i;
                if (x < 0) {
                    break;
                } else if (x == 0) {
                    return cur[1] + 1;
                }
                if (!vis[x]) {
                    queue.offer(new int[]{x, cur[1] + 1});
                    vis[x] = true;
                }
            }
        }
        throw new IllegalArgumentException();
    }
}

方法二：动态规划，时间复杂度 O(n√n)。

  • 令 dp[i] 表示通过平方数组成 i 所需要的最少数量。
  • 则 dp[i] = min(dp[i - j * j] + 1)， 其中 1≤j≤√i。
  • dp[n] 为最终结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_00279 {

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        // 最坏情况下就是本身，分解为 n 个 1
        for (int i = 1; i <= n; ++i) {
            dp[i] = i;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j * j <= i; ++j) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

方法三：数学方法，时间复杂度为 O(√n+logn)。

  • 根据 拉格朗日四平方和定理，可以得知答案必定为 1, 2, 3, 4 中的一个。
  • 根据 勒让德三平方和定理，可以得知当 n=4a(8b+7) 时，n 不能写成 3 个数的平方和。
  • 根据上面两个定理，首先判断结果是否 1。
  • 然后判断结果是否为 4。
  • 接着枚举结果是否为 2。
  • 最后上面条件都不满足，结果为 3。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode_00279 {

    public int numSquares(int n) {
        int s = (int) Math.sqrt(n);
        if (s * s == n) {
            return 1;
        }
        while ((n & 3) == 0) {      // n % 4 == 0
            n >>= 2;
        }
        if (((n - 7) & 7) == 0) {   // (n - 7) % 8 == 0
            return 4;
        }
        for (int i = 1; i * i <= n; ++i) {
            int j = (int) Math.sqrt(n - i * i);
            if (i * i + j * j == n) {
                return 2;
            }
        }
        return 3;
    }
}