LEETCODE 279. Perfect Squares 解题思路分析

题目大意：

完全平方数

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

示例 1:

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

示例 2:

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=279

解题思路分析：

本题需要找到一个或多个完全平方数，保证他们的和为n。首先我们考虑，完全平方数肯定是正数并且小于等于n，因此我们需要找到小于等于n的所有完全平方数。首先求出n开方后得到的数字，即sqrt(n)，sqrt(n)的平方肯定是小于等于n最大的那个完全平方数。因此，1到sqrt(n)所有整数的平方即是小于等于n的所有完全平方数。举个例子，比如n等于17，17开方，即sqrt(17)等于4，1到4所有数字的平方分别为1，4，9，16。我们将上述所有的完全平方数保存至一个数组。

得到了所有完全平方数之后，问题就转化为，我们是否能在一些数字中，找到某些数字之和等于n（数字可以重复使用）。由于完全平方数中一定包含数字1，因此，对于任意一个数字n，我们能够保证至少找到一个答案，即n个1相加等于n。不过题目要求找到完全平方数个数最小的解，这就需要我们去尝试每一种组合。

这样题目就转化为搜索题，我们将每个完全平方数看作是一个节点，每个节点之间都是互相连通的，只要我们能够找到一条最短路径，其路径上节点和等于n即可。因此本题可以使用bfs或bfs两种思路进行查找。两种解法思路基本一致，先看bfs广度优先搜索的解法。

解法一：bfs广度优先搜索

bfs的起点是每一个完全平方数，我们将其加入到Queue，bfs每次向外扩散一步，查看是否存在和等于n的数值，如果存在，返回当前步数，否则继续向外扩散一步，扩散时，凡是已经计算过的和或者当前和大于n的路径可以跳过。

实现代码：

public int numSquares(int n) {
    // bfs用的Queue
    Queue<Integer> q = new LinkedList<>();
    // 记录以经计算过的sum
    boolean[] visited =new boolean[n+1];
    // 将n开方
    int max=(int)Math.sqrt(n);
    int[] arr = new int[max];
    // 将1到max所有数字的平方加入到数组，
    // 找到所有小于等于n的完全平方数
    for(int i=max;i>=1;i--){
        arr[i-1]=i*i;
        q.offer(arr[i-1]);
    }
    // 返回结果
    int res=0;
    // 以下是标准bfs
    while(q.size()>0){
        int size =q.size();
        // 当前步数加一
        res++;
        while(size>0){
            // 当前路径和
            int cur=q.poll();
            // 如果和等于n，返回步数
            if(cur==n) return res;
            size--;
            // 用当前路径和尝试加上每一个完全平方数
            for(int i=max-1;i>=0;i--){
                // 当前和
                int sum=cur+arr[i];
                // 如果sum小于等于n并且该sum没被计算过
                if(sum<=n&&!visited[sum]){
                    // 将sum添加到Queue
                    q.offer(sum);
                    // 当前sum标记为已被计算过
                    visited[sum]=true;
                }
            }
        }
     }
    return res;
}

本解法执行时间为77ms。

Runtime: 77 ms, faster than 18.60% of Java online submissions for Perfect Squares.

Memory Usage: 55.1 MB, less than 9.72% of Java online submissions for Perfect Squares.

---

解法二：dfs深度优先搜索

dfs与bfs类似，只不过采用递归加memo数组形式而已。

实现代码：

int memo[]; // 记忆数组
public int numSquares(int n) {
    // 初始化记忆数组，
    // memo[i]表示从数字i加到n需要多少个完全平方数
    memo=new int[n+1];
    // 与bfs解法相同，先找出所有完全平方数
    int max=(int)Math.sqrt(n);
    int[] arr = new int[max];
    for(int i=1;i<=max;i++) arr[i-1]=i*i;
    // dfs递归求解，也就是求解memo[0]
    return dfs(arr,0,n);
}
int dfs(int[] arr,int sum,int n){
    // 如果当前和等于n，返回0。（从n加到n需要0个完全平方数）
    if(sum==n) return 0;
    // 如果记忆数组中存在当前解，直接返回
    if(memo[sum]>0) return memo[sum];
    // 返回结果（默认为n，因为最多需要n次，使用n个1相加）
    int res=n;
    // 循环每一个完全平方数
    for(int i=arr.length-1;i>=0;i--){
        // 使用一个完全平方数加上当前sum
        int s=sum+arr[i];
        // 如果和小于等于n，递归求解（求memo[s]）
        if(s<=n){
            // memo[s]加一为当前解，并更新所有情况的最优解
            res=Math.min(res,dfs(arr,s,n)+1);
        }
    }
    // 将当前的最优解保存至memo记忆数组
    memo[sum]=res;
    return res;
}

本解法执行时间为77ms。

Runtime: 77 ms, faster than 18.68% of Java online submissions for Perfect Squares.

Memory Usage: 43.4 MB, less than 13.89% of Java online submissions for Perfect Squares.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-279-perfect-squares-解题思路分析/