给定一个非负整数数组 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
方法一：回溯
思路
构造一张图，包含所有的边 i 到 j ，如果满足 A[i] + A[j] 是一个完全平方数。我们的目标就是求这张图的所有哈密顿路径，即经过图中所有点仅一次的路径。
算法
我们使用 count 记录对于每一种值还有多少个节点等待被访问，与一个变量 todo 记录还剩多少个节点等待被访问。
对于每一个节点，我们可以访问它的所有邻居节点（从数值的角度来看，从而大大减少复杂度）。
对于每一个节点，我们可以访问它的所有邻居节点（从数值的角度来看，从而大大减少复杂度）。
更多细节请看行内注释。
[mQV43TKa-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| 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();
for (int x: A)
count.put(x, count.getOrDefault(x, 0) + 1);
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);
}
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;
}
}
|
[mQV43TKa-Python]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution(object):
def numSquarefulPerms(self, A):
N = len(A)
count = collections.Counter(A)
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):
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, len(A) - 1) for x in count)
|
复杂度分析
方法二：动态规划
思路
与 方法一 中相似，构造一样的图。因为节点的数量非常少，所以可以使用掩码标记所有已经过点的方式来进行动态规划。
算法
我们用同样的方式构造与 方法一 中一样的图。
现在，我们令 dfs(node, visited) 等于从 node 节点出发访问剩余的节点的可行方法数。这里，visited 是一个掩码：(visited >> i) & 1 为真，当且仅当第 i 个节点已经被访问过了。
这样计算之后，对于 A 中拥有相同值的节点我们会重复计算。考虑这个因素，对于 A 中的值 x，如果 A 中包含 k 个值为 x 的节点，我们令最终答案除以 k!。
[DcJoGw67-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
int N;
Map<Integer, List<Integer>> graph;
Integer[][] memo;
public int numSquarefulPerms(int[] A) {
N = A.length;
graph = new HashMap();
memo = new Integer[N][1 << N];
for (int i = 0; i < N; ++i)
graph.put(i, new ArrayList());
for (int i = 0; i < N; ++i)
for (int j = i+1; j < N; ++j) {
int r = (int) (Math.sqrt(A[i] + A[j]) + 0.5);
if (r * r == A[i] + A[j]) {
graph.get(i).add(j);
graph.get(j).add(i);
}
}
int[] factorial = new int[20];
factorial[0] = 1;
for (int i = 1; i < 20; ++i)
factorial[i] = i * factorial[i-1];
int ans = 0;
for (int i = 0; i < N; ++i)
ans += dfs(i, 1 << i);
Map<Integer, Integer> count = new HashMap();
for (int x: A)
count.put(x, count.getOrDefault(x, 0) + 1);
for (int v: count.values())
ans /= factorial[v];
return ans;
}
public int dfs(int node, int visited) {
if (visited == (1 << N) - 1)
return 1;
if (memo[node][visited] != null)
return memo[node][visited];
int ans = 0;
for (int nei: graph.get(node))
if (((visited >> nei) & 1) == 0)
ans += dfs(nei, visited | (1 << nei));
memo[node][visited] = ans;
return ans;
}
}
|
[DcJoGw67-Python]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| from functools import lru_cache
class Solution:
def numSquarefulPerms(self, A):
N = len(A)
def edge(x, y):
r = math.sqrt(x+y)
return int(r + 0.5) ** 2 == x+y
graph = [[] for _ in range(len(A))]
for i, x in enumerate(A):
for j in range(i):
if edge(x, A[j]):
graph[i].append(j)
graph[j].append(i)
@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(A)
for v in count.values():
ans //= math.factorial(v)
return ans
|
复杂度分析
