文章目錄
- 1. 題目
- 2. 解題
1. 題目
給定一個非負整數陣列 A，如果該陣列每對相鄰元素之和是一個完全平方數，則稱這一陣列為正方形陣列，
回傳 A 的正方形排列的數目，兩個排列 A1 和 A2 不同的充要條件是存在某個索引 i，使得 A1[i] != A2[i]，
示例 1：
輸入：[1,17,8]
輸出：2
解釋：
[1,8,17] 和 [17,8,1] 都是有效的排列，
示例 2：
輸入：[2,2,2]
輸出：1
提示：
1 <= A.length <= 12
0 <= A[i] <= 1e9
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/number-of-squareful-arrays
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
2. 解題
類似題目：
LeetCode 47. 全排列 II（回溯+搜索剪枝）
LeetCode 46. 全排列（回溯）
class Solution {
int ans = 0;
public:
int numSquarefulPerms(vector<int>& A) {
vector<bool> vis(A.size(), false);
sort(A.begin(), A.end());
dfs(A, 0, -1, vis);
return ans;
}
void dfs(vector<int>& A, int count, int prev, vector<bool>& vis)
{
if(count == A.size())
{
ans++;
return;
}
for(int i = 0; i < A.size(); ++i)
{
if(i > 0 && !vis[i-1] && A[i-1]==A[i])
continue;// 剪枝
if(!vis[i] && (prev == -1 || ok(prev, A[i])))
{
vis[i] = true;
dfs(A, count+1, A[i], vis);
vis[i] = false;
}
}
}
bool ok(int a, int b)
{
int num = sqrt(a+b);
return num*num == a+b;
}
};
4 ms 7.8 MB
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/160861.html
標籤：其他
上一篇：「物流跟蹤管理系統」 · Java Swing + MySQL JDBC開發，美和易思結業考試機試試題
下一篇：CTF ics-04