資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告