class Solution {
public:
int numSquarefulPerms(vector<int>& nums) {
}
};
996. 正方形数组的数目
给定一个非负整数数组 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 <= 120 <= A[i] <= 1e9相似题目
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-10-12 10:34:41
func numSquarefulPerms(A []int) int {
used := make([]bool, len(A))
sum := 0
sort.Ints(A)
for i := 0; i < len(A); i++ {
if i > 0 && A[i] == A[i-1] {
continue
}
used[i] = true
backtrack(A, used, A[i], 1, &sum)
used[i] = false
}
return sum
}
// 不考虑重复位置的回溯
func backtrack(A []int, used []bool, now int, count int, sum *int) {
if count == len(A) {
*sum += 1
return
}
for i := 0; i < len(A); i++ {
if used[i] {
continue
}
var flag bool
for j := i - 1; j >= 0; j-- {
if !used[j] {
if A[j] == A[i] {
flag = true
}
break
}
}
if flag {
continue
}
if isSquare(now + A[i]) {
used[i] = true
backtrack(A, used, A[i], count + 1, sum)
used[i] = false
}
}
}
func isSquare(x int) bool {
s := math.Sqrt(float64(x))
i := float64(int(s))
return s == i
}
golang 解法, 执行用时: 4 ms, 内存消耗: 1.8 MB, 提交时间: 2023-10-12 10:32:36
// 全排列II + 剪枝
func numSquarefulPerms(nums []int) (ans int) {
n := len(nums)
vis := make([]bool, n)
sort.Ints(nums)
var dfs func([]int, int)
dfs = func(x []int, pre int) {
if len(x) == n {
ans++
return
}
last := -1
for i, v := range nums {
if vis[i] == false && (last == -1 || v != nums[last]) {
// 第一个数或者和上一个数之和为完全平方数才继续dfs
if pre == -1 || isPerfectSquare(v + pre) {
last = i
vis[i] = true
dfs(append(x, v), v)
vis[i] = false
}
}
}
}
dfs([]int{}, -1)
return
}
func isPerfectSquare(x int) bool {
return int(math.Sqrt(float64(x))) * int(math.Sqrt(float64(x))) == x
}
python3 解法, 执行用时: 152 ms, 内存消耗: 24.3 MB, 提交时间: 2023-10-12 10:29:37
class Solution:
def numSquarefulPerms(self, nums: List[int]) -> int:
from functools import lru_cache
n = len(nums)
def edge(x, y):
r = math.sqrt(x+y)
return int(r + 0.5) ** 2 == x+y
graph = [[] for _ in range(n)]
for i, x in enumerate(nums):
for j in range(i):
if edge(x, nums[j]):
graph[i].append(j)
graph[j].append(i)
# dfs(node, visited) 等于从 node 节点出发访问剩余的节点的可行方法数。
@lru_cache(None)
def dfs(node, visited):
if visited == (1 << n) - 1:
return 1
ans = 0
for nei in graph[node]:
if (visited >> nei) & 1 == 0:
ans += dfs(nei, visited | (1 << nei))
return ans
ans = sum(dfs(i, 1<<i) for i in range(n))
count = collections.Counter(nums)
for v in count.values():
ans //= math.factorial(v)
return ans
cpp 解法, 执行用时: 40 ms, 内存消耗: 8.1 MB, 提交时间: 2023-10-12 10:26:51
class Solution {
public:
int dp[13][1<<12],g[13];
unordered_map<int,int>mp;
bool check(int a,int b) {
int d=(int)sqrt(a+b);
return d*d==(a+b);
}
int numSquarefulPerms(vector<int>& nums) {
int n=nums.size();
for(int i=0;i<n;i++) dp[i][(1<<i)]=1,g[i]|=(1<<i),mp[nums[i]]++;
for(int i=1;i<1<<n;i++) {
for(int j=0;j<n;j++) {
if(i&(1<<j)) {
for(int k=0;k<n;k++) {
if(j!=k&&check(nums[j],nums[k])&&((1<<k)&i))
dp[j][i]+=dp[k][i^(1<<j)];
}
}
}
}
int ans=0;
for(int i=0;i<n;i++) ans+=dp[i][(1<<n)-1];
for(auto& [k,v]:mp) {
for(int i=1;i<=v;i++) ans/=i;
}
return ans;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 38.7 MB, 提交时间: 2023-10-12 10:25:04
class Solution {
public int numSquarefulPerms(int[] A) {
/*
普通的全排列
*/
Arrays.sort(A);
count = 0;
len = A.length;
dfs(A, new boolean[len], 0, -1);
return count;
}
int count;
int len;
private void dfs(int[] A, boolean[] used, int index, int pre){
if(index == len){
count++;
return;
}
for(int i = 0; i < len; i++){
if(!used[i]){
if(i > 0 && A[i - 1] == A[i] && !used[i - 1]){
continue;
}
used[i] = true;
//index == 0，表示这是排列的第一个数
if(index == 0){
dfs(A, used, index + 1, A[i]);
}else{
int sum = A[i] + pre;
int sqrt = (int)Math.sqrt(sum);
//判断是否是完全平方数
if(sqrt * sqrt == sum){
dfs(A, used, index + 1, A[i]);
}
}
used[i] = false;
}
}
}
}
java 解法, 执行用时: 1 ms, 内存消耗: 38.7 MB, 提交时间: 2023-10-12 10:22:55
class Solution {
Map<Integer, Integer> count;
Map<Integer, List<Integer>> graph;
public int numSquarefulPerms(int[] A) {
int N = A.length;
count = new HashMap();
graph = new HashMap();
// count.get(v) : 数组 A 中值为 v 的节点数量
for (int x: A)
count.put(x, count.getOrDefault(x, 0) + 1);
// graph.get(v) : 在 A 中的值 w 满足 v + w 是完全平方数
// (ie., "vw" is an edge)
for (int x: count.keySet())
graph.put(x, new ArrayList());
for (int x: count.keySet())
for (int y: count.keySet()) {
int r = (int) (Math.sqrt(x + y) + 0.5);
if (r * r == x + y)
graph.get(x).add(y);
}
// 增加从 x 开始的可行路径数量
int ans = 0;
for (int x: count.keySet())
ans += dfs(x, N - 1);
return ans;
}
public int dfs(int x, int todo) {
count.put(x, count.get(x) - 1);
int ans = 1;
if (todo != 0) {
ans = 0;
for (int y: graph.get(x)) if (count.get(y) != 0) {
ans += dfs(y, todo - 1);
}
}
count.put(x, count.get(x) + 1);
return ans;
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 15.8 MB, 提交时间: 2023-10-12 10:22:21
class Solution:
'''
回溯
使用 count 记录对于每一种值还有多少个节点等待被访问，与一个变量 todo 记录还剩多少个节点等待被访问。
对于每一个节点，我们可以访问它的所有邻居节点（从数值的角度来看，从而大大减少复杂度）。
对于每一个节点，我们可以访问它的所有邻居节点（从数值的角度来看，从而大大减少复杂度）。
'''
def numSquarefulPerms(self, nums: List[int]) -> int:
n = len(nums)
count = collections.Counter(nums)
graph = {x: [] for x in count}
for x in count:
for y in count:
if int((x+y)**.5 + 0.5) ** 2 == x+y:
graph[x].append(y)
def dfs(x, todo: int) -> int:
count[x] -= 1
if todo == 0:
ans = 1
else:
ans = 0
for y in graph[x]:
if count[y]:
ans += dfs(y, todo - 1)
count[x] += 1
return ans
return sum(dfs(x, n - 1) for x in count)