X

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-解题思路分析/
Categories: leetcode
kwantong:

View Comments (1)

  • I'm gone to say to my little brother, that he should also go to see
    this blog on regular basis to obtain updated from most up-to-date gossip.