LeetCode279——完全平方数

偏执的太偏执、 2022-03-10 07:24 218阅读 0赞

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCode]

原题链接：[https://leetcode-cn.com/problems/perfect-squares/][https_leetcode-cn.com_problems_perfect-squares]

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70][]

知识点：广度优先搜索、动态规划

### 思路一：广度优先搜索 ###

深搜用栈，广搜用队列。

时间复杂度是O(n ^ 2)。空间复杂度是O(n)。

JAVA代码：

class Solution {
        public int numSquares(int n) {
            int result = 1;
            Queue<Integer> queue = new LinkedList<>();
            queue.add(n);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int now = queue.poll();
                    for (int j = 1; j * j <= now; j++) {
                        if (now - j * j == 0) {
                            return result;
                        }
                        queue.add(now - j * j);
                    }
                }
                result++;
            }
            return -1;
        }
    }

LeetCode解题报告：

![20190310095925963.jpg][]

### 思路二：动态规划 ###

仔细分析思路一中的广搜算法：12可以由11加上1，或者是8加上4，或者是3加上9得到。

对于11可以由10加上1，或者是**7**加上4，或者是2加上9得到。

对于8可以由**7**加上1，或者是4加上4得到。

……如果更进一步分析下去，我们需要分析两次上述的7，这其实是一种重复计算，因此我们采用动态规划来进行优化。

**状态定义**：

f(x) -------- 数字总和为x的最少完全平方数个数

**状态转移**：

f(x) = min(f(x), 1 + f(y)), y∈\[0, x - 1\]，且x - y是一个完全平方数

时间复杂度是O(n ^ 1.5)。空间复杂度是O(n)。

JAVA代码：

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

LeetCode解题报告：

![20190310100417350.jpg][]

[https_github.com_617076674_LeetCode]: https://github.com/617076674/LeetCode
[https_leetcode-cn.com_problems_perfect-squares]: https://leetcode-cn.com/problems/perfect-squares/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70]: /images/20220310/3eeaf50907e2483e9369ae0ad68615aa.png
[20190310095925963.jpg]: /images/20220310/71a87a20db39436bbe80c314ec96fbcc.png
[20190310100417350.jpg]: /images/20220310/67f6480692534a1d8d899958903a697d.png