leetcode 279. Perfect Squares-蒲公英云

leetcode 279. Perfect Squares

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;
    }
};