[刷题] LeetCode 279 Perfect Squares

 1 class Solution {
 2 public:
 3     int numSquares(int n) {
 4         
 5         assert( n > 0 );
 6         
 7         queue< pair<int,int> > q;
 8         q.push( make_pair( n , 0 ) );
 9         
10         while( !q.empty() ){
11             int num = q.front().first;
12             int step = q.front().second;
13             q.pop();
14             
15             if( num == 0 )
16                 return step;
17                 
18             for( int i = 1 ; num - i*i >=0 ; i ++ )
19                 q.push( make_pair( num - i * i , step + 1 ) );
20         }
21         
22         throw invalid_argument("No Solution");
23     }
24 };

 1 class Solution {
 2 public:
 3     int numSquares(int n) {
 4         
 5         assert( n > 0 );
 6         
 7         queue< pair<int,int> > q;
 8         q.push( make_pair( n , 0 ) );
 9         
10         vector<bool> visited(n+1, false);
11         visited[n] = true;
12         
13         while( !q.empty() ){
14             int num = q.front().first;
15             int step = q.front().second;
16             q.pop();
17             
18             for( int i = 1 ; ; i ++ ){
19                 int a = num - i*i;
20                 if( a < 0 )
21                     break;
22                 if( a == 0)
23                     return step + 1;
24                 if( ! visited[a] ){
25                 q.push( make_pair( a , step + 1 ) );
26                 visited[a] = true;
27             }
28         }
29     }
30     throw invalid_argument("No Solution");
31     }
32 };