【Breadth-first Search 】279. Perfect Squares

输入：一个非负整数n。
输出：这个非负整数可以写成几个完全平方数。返回这个数量。
规则：完全平方数可以表示为某个整数的平方。例如：1，4，9…
分析：13=4+9 也就是说13可以写成2个完全平方数的和。我可以先把13写成1+1+1+…+1，13个1相加。接着去拼$2\ast 2=4$，可以写成4+4+4+1。接着去拼$3\ast 3=9$， 可以写成9+4。接着去拼$4\ast 4=16$,16>13，退出。O__O "…没有写代码实现。
学习1：计算n以内的完全平方数，得到列表perfectSquares。
　初始化数组int[] cntPerfectSquares。perfectSquares所有值val,cntPerfectSquares[val]=1。
　以n以内的完全平方数为起点：1,4,9,… 每个节点i 与perfectSquares所有数据分别相加达到新的节点j,cntPerfectSquares[j]=cntPerfectSquares[i]+1。如果j=n，则退出返回cntPerfectSquares[n]。
　思路是这样的。可以使用BFS或者DP实现。

//BFS public int numSquares(int n) {List<Integer> perfectSquares = new ArrayList<Integer>();int[] cntPerfectSquares = new int[n];for(int i=1;i*i<=n;i++){if(i*i==n) return 1;perfectSquares.add(i*i);cntPerfectSquares[i*i-1] = 1;}Queue<Integer> queue = new LinkedList<Integer>();for(Integer val : perfectSquares){queue.offer(val);}while(!queue.isEmpty()){int size = queue.size();for(int i=0;i<size;i++){int val = queue.poll();for(Integer val2 : perfectSquares){if(val+val2==n) return 1+cntPerfectSquares[val-1];if(val+val2<n && cntPerfectSquares[val+val2-1]==0){cntPerfectSquares[val+val2-1] = 1+cntPerfectSquares[val-1];queue.offer(val+val2);}}}}return -1;}

DP思路：cntPerfectSquares[i]表示至少有cntPerfectSquares[i]个完全平方数的相加等于i。
cntPerfectSquares[0]=1;
cntPerfectSquares[1]=1;
cntPerfectSquares[2]=cntPerfectSquares[2-1]+1;
cntPerfectSquares[3]=cntPerfectSquares[3-1]+1;
$cntPerfectSquares[4]=Min(cntPerfectSquares[4-1\ast 1]+1,cntPerfectSquares[4-2\ast 2]+1))$
…
$cntPerfectSquares[i]=Min[cntPerfectSquares[i],cntPerfectSquares[i-j\ast j]+1]$, $1<=i<=n$,$1<=j\ast j<=i$

public int numSquaresV2(int n) {int[] cntPerfectSquares = new int[n+1];//设置最大值for(int i=0;i<cntPerfectSquares.length;i++){cntPerfectSquares[i] = n+1;}cntPerfectSquares[0] = 0;for(int i=1;i<=n;i++){for(int j=1;j*j<=i;j++){cntPerfectSquares[i] = Math.min(cntPerfectSquares[i],cntPerfectSquares[i-j*j]+1);}}return cntPerfectSquares[n];}

代码

总结

以上是生活随笔为你收集整理的【Breadth-first Search 】279. Perfect Squares的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。