leetcode 279. Perfect Squares

不念不忘少年蓝@ 2022-08-20 13:14 2阅读 0赞

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.

// ConsoleApplication1.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    #include<vector>
    #include<iostream>
    using namespace std;
    
    class Solution {
    private:
    	int minnum;
    	vector<int>minpath;
    public:
    	void do_once(int squarenum,int& remain,vector<int>&path)
    	{
    		if(path.size()>=minnum-1)
    			return;
    		for(int i=squarenum;i>=1;i--)
    		{
    			vector<int>pathcopy=path;
    			pathcopy.push_back(i);
    			int rem=remain-i*i;
    			if(rem==0)
    			{
    				if(pathcopy.size()<minnum)
    				{
    					minnum=pathcopy.size();
    					minpath=pathcopy;
    				}
    			}
    			else if(rem>0)
    			{
    				if(pathcopy.size()+1<minnum)
    				{
    					int startnum=sqrt(remain-i*i);
    					if(startnum>i)
    						startnum=i;
    					do_once(startnum,rem,pathcopy);
    
    				}
    			}
    		}
    	}
    	int numSquares(int n) {
    		int outsquare=sqrt(n);
    		minnum=100000;
    		while(outsquare!=0)
    		{
    			if(n/(outsquare*outsquare)>=minnum)
    				return minnum;
    			int remain=n;
    			vector<int>path;
    			do_once(outsquare,remain,path);
    			outsquare--;
    		}
    	}
    };
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	Solution sl;
    	cout<<sl.numSquares(7168);
    
    	system("pause");
    	return 0;
    }

超时

稍作修改

class Solution {
    private:
    	int minnum;
    	vector<int>minpath;
    public:
    	void do_once(int squarenum,int& remain,vector<int>&path)
    	{
    		if(path.size()>=minnum-1)
    			return;
    		for(int i=squarenum;i>=1;i--)
    		{
    			vector<int>pathcopy=path;
    			pathcopy.push_back(i);
    			int rem=remain-i*i;
    			if(rem==0)
    			{
    				if(pathcopy.size()<minnum)
    				{
    					minnum=pathcopy.size();
    					minpath=pathcopy;
    				}
    			}
    			else if(rem>0)
    			{
    				if(pathcopy.size()+1<minnum)
    				{
    					int startnum=sqrt(remain-i*i);
    					if(startnum>i)
    						startnum=i;
    					do_once(startnum,rem,pathcopy);
    				}
    			}
    		}
    	}
    	int numSquares(int n) {
    		int outsquare=sqrt(n);
    		minnum=100000;
    		while(outsquare!=0)
    		{
    			if(n/(outsquare*outsquare)>=minnum)
    				return minnum;
    			int insquare=sqrt(n-outsquare*outsquare);
    			if(insquare>outsquare)
    				insquare=outsquare;
    			int remain=n-outsquare*outsquare;
    			if(remain==0)
    				return 1;
    			vector<int>path;
    			path.push_back(outsquare);
    			do_once(insquare,remain,path);
    			outsquare--;
    		}
    		return minnum;
    	}
    };

accepted