数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
服装研究
法律研究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与a的大小相同，则：
(计数器加1)
返回
定义一个集合visited
对于初始化i := idx，当i < a的大小时，更新(i加1)，执行：
如果(idx为0或isSqr(a[idx - 1] + a[i]))且a[i]不在visited中，则：
交换(a[idx], a[i])
solve(a, idx + 1)
交换(a[idx], a[i])
将a[i]插入到visited中
从主方法中，执行以下操作：
count := 0
solve(a, 0)
返回count
让我们看看下面的实现，以便更好地理解：
示例
#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
更新于：2020年6月4日
236 次查看
广告