做公司员工福利的网站都有哪些,百度点击器下载,网站首页幻灯片尺寸,为什么网站有不同的扩展名输入#xff1a;一个非负整数n。 输出#xff1a;这个非负整数可以写成几个完全平方数。返回这个数量。 规则#xff1a;完全平方数可以表示为某个整数的平方。例如#xff1a;1#xff0c;4#xff0c;9… 分析#xff1a;1349 也就是说13可以写成2个完全平方数的和。我…输入一个非负整数n。 输出这个非负整数可以写成几个完全平方数。返回这个数量。 规则完全平方数可以表示为某个整数的平方。例如149… 分析1349 也就是说13可以写成2个完全平方数的和。我可以先把13写成111…113个1相加。接着去拼2∗242*242∗24可以写成4441。接着去拼3∗393*393∗39 可以写成94。接着去拼4∗4164*4164∗416,1613退出。O__O …没有写代码实现。 学习1计算n以内的完全平方数得到列表perfectSquares。 初始化数组int[] cntPerfectSquares。perfectSquares所有值val,cntPerfectSquares[val]1。 以n以内的完全平方数为起点1,4,9,… 每个节点i 与perfectSquares所有数据分别相加达到新的节点j,cntPerfectSquares[j]cntPerfectSquares[i]1。如果jn则退出返回cntPerfectSquares[n]。 思路是这样的。可以使用BFS或者DP实现。
//BFS
public int numSquares(int n) {ListInteger perfectSquares new ArrayListInteger();int[] cntPerfectSquares new int[n];for(int i1;i*in;i){if(i*in) return 1;perfectSquares.add(i*i);cntPerfectSquares[i*i-1] 1;}QueueInteger queue new LinkedListInteger();for(Integer val : perfectSquares){queue.offer(val);}while(!queue.isEmpty()){int size queue.size();for(int i0;isize;i){int val queue.poll();for(Integer val2 : perfectSquares){if(valval2n) return 1cntPerfectSquares[val-1];if(valval2n cntPerfectSquares[valval2-1]0){cntPerfectSquares[valval2-1] 1cntPerfectSquares[val-1];queue.offer(valval2);}}}}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∗1]1,cntPerfectSquares[4−2∗2]1))cntPerfectSquares[4]Min(cntPerfectSquares[4-1*1]1,cntPerfectSquares[4-2*2]1))cntPerfectSquares[4]Min(cntPerfectSquares[4−1∗1]1,cntPerfectSquares[4−2∗2]1)) … cntPerfectSquares[i]Min[cntPerfectSquares[i],cntPerfectSquares[i−j∗j]1]cntPerfectSquares[i]Min[cntPerfectSquares[i],cntPerfectSquares[i-j*j]1]cntPerfectSquares[i]Min[cntPerfectSquares[i],cntPerfectSquares[i−j∗j]1], 1lt;ilt;n1lt;ilt;n1in,1lt;j∗jlt;i1lt;j*jlt;i1j∗ji
public int numSquaresV2(int n) {int[] cntPerfectSquares new int[n1];//设置最大值for(int i0;icntPerfectSquares.length;i){cntPerfectSquares[i] n1;}cntPerfectSquares[0] 0;for(int i1;in;i){for(int j1;j*ji;j){cntPerfectSquares[i] Math.min(cntPerfectSquares[i],cntPerfectSquares[i-j*j]1);}}return cntPerfectSquares[n];}代码
