C ++中平方数组的数量

假设我们有一个由正整数组成的数组A，可以说该数组是正方形的，如果对于每对相邻元素，它们的和是一个完美的平方。我们必须找到平方的A的排列数。当且仅当存在一些索引i使得A1 [i]与A2 [i]不同时，两个置换A1和A2才会相同。

因此，如果输入像[3,30,6]，那么输出将为2，因为我们有两个排列，例如[3,6,30]，[30,6,3]。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数isSqr()，将花费n，

• x：= n的平方根

• 当（x * x）与n相同时返回true

• 定义一个函数solve()，它将使用一个数组a，idx，

• 如果（idx与0或isSqr（a [idx-1] + a [i]））和a [i]未访问，则-

• swap（a [idx]，a [i]）

• 解决（a，idx + 1）

• swap（a [idx]，a [i]）

• 在访问过的地方插入一个[i]

• （增加1）

• 返回

• 如果idx与a的大小相同，则-

• 定义一组参观

• 对于初始化i：= idx，当i <a的大小时，更新（将i增加1），执行-

• 从主要方法中，执行以下操作-

• 计数：= 0

• 解决(a,0)

• 返回计数

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int count;
   bool isSqr(lli n){
      lli x = sqrt(n);
      return x * x == n;
   }
   void solve(vector<int>& a, int idx){
      if (idx == a.size()) {
         count++;
         return;
      }
      set<int> visited;
      for (int i = idx; i < a.size(); i++) {
         if ((idx == 0 || isSqr(a[idx - 1] + a[i])) &&
         !visited.count(a[i])) {
            swap(a[idx], a[i]);
            solve(a, idx + 1);
            swap(a[idx], a[i]);
            visited.insert(a[i]);
         }
      }
   }
   int numSquarefulPerms(vector<int>& a){
      count = 0;
      solve(a, 0);
      return count;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,30,6};
   cout << (ob.numSquarefulPerms(v));
}

输入值

{3,30,6}

输出结果

2