lintcode：完美平方

题目

给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。

样例

给出 n = 12, 返回 3 因为 12 = 4 + 4 + 4。
给出 n = 13, 返回 2 因为 13 = 4 + 9。

解题

题目标签：深度优先遍历

下面的深搜，通过找到所有结果，再找出最短的那个

public class Solution {

    /**

     * @param n a positive integer

     * @return an integer

     */

    public int numSquares(int n) {

        // Write your code here

        int up = (int)Math.sqrt(n);

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        ArrayList<Integer> list = new ArrayList<Integer>();

        int sum = 0;

        dfs(result,list,up,sum,n);

        int min = result.get(0).size();

        for(int i=0;i<result.size();i++){

            min = Math.min(min,result.get(i).size());

        }

        return min;

    }

    public void dfs(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list,int start,int sum,int n){

        if(n == sum){

            result.add(new ArrayList<Integer>(list));

            return;

        }

        if(start==0 || sum>n)

            return;

        for(int i=start;i>=1;i--){

            if(sum+i*i >n){

                continue;

            }

            list.add(i);

            dfs(result,list,i,sum+i*i,n);

            list.remove(list.size()-1);

        }

    }

}

输入：

1684
时候内存溢出

不记录结果，只统计次数，改成下面的在1684时候时间超时

public class Solution {

    /**

     * @param n a positive integer

     * @return an integer

     */

     int minCount = Integer.MAX_VALUE;

    public int numSquares(int n) {

        // Write your code here

        int up = (int)Math.sqrt(n);

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        ArrayList<Integer> list = new ArrayList<Integer>();

        int sum = 0;

        dfs(result,list,up,sum,n);

        // int min = result.get(0).size();

        // for(int i=0;i<result.size();i++){

            // min = Math.min(min,result.get(i).size());

        // }

        return minCount;

    }

    public void dfs(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list,int start,int sum,int n){

        if(n == sum){

            // result.add(new ArrayList<Integer>(list));

            minCount = Math.min(minCount,list.size());

            return;

        }

        if(start==0 || sum>n)

            return;

        for(int i=start;i>=1;i--){

            if(sum+i*i >n){

                continue;

            }

            list.add(i);

            dfs(result,list,i,sum+i*i,n);

            list.remove(list.size()-1);

        }

    }

}

动态规划解题

参考链接

如果一个数x可以表示为一个任意数a加上一个平方数bｘb，也就是x=a+bｘb，那么能组成这个数x最少的平方数个数，就是能组成a最少的平方数个数加上1（因为b*b已经是平方数了）。

public class Solution {

    /**

     * @param n a positive integer

     * @return an integer

     */

     int minCount = Integer.MAX_VALUE;

    public int numSquares(int n) {

        // Write your code here

        int[] dp = new int[n+1];

        // 将所有非平方数的结果置最大，保证之后比较的时候不被选中

        Arrays.fill(dp, Integer.MAX_VALUE);

        // 将所有平方数的结果置1

        for(int i = 0; i * i <= n; i++){

            dp[i * i] = 1;

        }

        // 从小到大找任意数a

        for(int a = 0; a <= n; a++){

            // 从小到大找平方数bｘb

            for(int b = 0; a + b * b <= n; b++){

                // 因为a+b*b可能本身就是平方数，所以我们要取两个中较小的

                dp[a + b * b] = Math.min(dp[a] + 1, dp[a + b * b]);

            }

        }

        return dp[n];

    }

}

巴特西

lintcode：完美平方

最新文章

热门文章