首页 > 代码库 > 279. Perfect Squares
279. Perfect Squares
- Total Accepted: 48616
- Total Submissions: 142008
- Difficulty: Medium
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
穷举会： Time Limit Exceeded
加入几个分支判断，除去大部分没用分支
public class Solution { public int numSquares(int n) { if(n == 0){ return 0; } int count = 0; while (count*count <= n){ if(count*count == n){ return 1; } count++; } int nums [] = new int[count]; DFS(n,nums,count-1,0); return result; } int result = Integer.MAX_VALUE; private void DFS(int n,int[] nums,int selectNum,int preCount){ // count:平方数最大是几，n：sum target,nums 1——count if(n == 0){ int newResult = getResult(nums); if(result > newResult){ //time limit error 优化：加入preCount,统计到目前为止已用的的数量 result = newResult; } return; } if(preCount >= result){ return; } if(selectNum >= 1){ int maxLoop = n / selectNum /selectNum; if(preCount+maxLoop > result) return; //time limit error 优化：加入preCount,统计到目前为止已用的的数量 for(int i = maxLoop;i >= 0;i--){ nums[selectNum] = i; DFS(n-i*selectNum*selectNum,nums,selectNum-1,preCount+i); } } } private int getResult(int[]nums){ int result = 0; for(int i = 1;i < nums.length;i++){// System.out.print(nums[i] + " "); result+=nums[i]; }// System.out.println("result:"+result); return result; }}
279. Perfect Squares
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。