Leetcode-996 Number of Squareful Arrays(正方形数组的数目)

 1 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 2 class Solution
 3 {
 4     public:
 5         bool judge(int n)
 6         {
 7             if(n == (int)sqrt(n)*(int)sqrt(n))
 8                 return true;
 9             return false;
10         }
11         int numSquarefulPerms(vector<int>& A)
12         {
13             int sz = A.size();
14             int cnt = 0;
15             int p = 0;
16             _for(i,0,sz)
17                 _for(j,i+1,sz)
18                     if(judge(A[i]+A[j]))
19                         p ++;
20             if(p*2<sz)
21                 return 0;
22             sort(A.begin(),A.end());
23             do
24             {
25                 int i;
26                 for(i = 0;i < sz-1;i ++)
27                     if(!judge(A[i]+A[i+1]))
28                         break;
29                 if(i==sz-1)
30                     cnt ++;
31             }
32             while(next_permutation(A.begin(),A.end()));
33             return cnt;
34         }
35 };

暴力+优化，说实话能过我也觉得很奇妙，可能是因为数据范围很小的缘故吧