MLE in my BFS solution, why?


  • 0
    V

    I wrote nearly the same code as this post by BFS

    https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics

    However, I get MLE while the code in that post can get AC.

    Any suggestion?

    class Solution {
    public:
        int numSquares(int n) {
            
            if( !n )
                {
                return 0;   
                }
            vector<int> squareTable( 1, 0 );
            vector<int> ans( n + 1, INT_MAX );
            for( int i = 1; i * i <= n; ++i )
                {
                squareTable.push_back( i * i );
                ans[i*i] = 1;
                }
            if( squareTable.back() == n )
                {
                return 1;
                }
            queue<int> searchQueue;
            for( int i = 1; i < squareTable.size(); ++i )
                {
                searchQueue.push( squareTable[i] );
                }
            
            while( !searchQueue.empty() )
                {
                int current = searchQueue.front();
                searchQueue.pop();
                
                for( int i = 1; i < squareTable.size() && squareTable[i] + current <= n; ++i  )
                    {
                    int sum = current + squareTable[i];
                    if( sum == n )
                        {
                        return ans[ current ] + 1;
                        }
                    else
                        {
                        ans[ sum ] = ans[ current ] + 1;
                        searchQueue.push( sum );
                        }
                    }
                }
        return 0;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.