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