LeetCode 题解工作台
平方数组的数目
如果一个数组的任意两个相邻元素之和都是 完全平方数 ，则该数组称为 平方数组 。 给定一个整数数组 nums ，返回所有属于 平方数组 的 nums 的排列数量。 如果存在某个索引 i 使得 perm1[i] != perm2[i] ，则认为两个排列 perm1 和 perm2 不同。 示例 1： …
7
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
注意到，数组 的长度 不超过 ，因此我们可以用一个二进制数表示当前所选的数字的状态，若第 位为 ，则表示当前选择了第 个数字，否则表示当前没有选择第 个数字。 我们定义 表示当前所选的数字的状态为 ，且最后一个数字为 的方案数。那么答案就是 $\sum_{j=0}^{n-1} f[2^n-1][j]$。由于最后求解的是排列数，因此还需要除以每个数字出现的次数的阶乘。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
如果一个数组的任意两个相邻元素之和都是 完全平方数 ，则该数组称为 平方数组 。
给定一个整数数组 nums，返回所有属于 平方数组 的 nums 的排列数量。
如果存在某个索引 i 使得 perm1[i] != perm2[i]，则认为两个排列 perm1 和 perm2 不同。
示例 1：
输入：nums = [1,17,8] 输出：2 解释：[1,8,17] 和 [17,8,1] 是有效的排列。
示例 2：
输入：nums = [2,2,2] 输出：1
提示：
1 <= nums.length <= 120 <= nums[i] <= 109
解题思路
方法一：二进制状态压缩 + 动态规划
注意到，数组 的长度 不超过 ，因此我们可以用一个二进制数表示当前所选的数字的状态，若第 位为 ，则表示当前选择了第 个数字，否则表示当前没有选择第 个数字。
我们定义 表示当前所选的数字的状态为 ，且最后一个数字为 的方案数。那么答案就是 。由于最后求解的是排列数，因此还需要除以每个数字出现的次数的阶乘。
接下来，我们考虑如何进行状态转移。
假设当前所选的数字的状态为 ，最后一个数字为 ，那么我们可以枚举 的每一位为 的数字作为倒数第二个数，不妨设为 ，那么我们只需要判断 是否为完全平方数即可，若是，方案数 就可以加上 ，其中 表示将 的第 位取反，即表示将 从当前所选的数字中去除。
最后，我们还需要除以每个数字出现的次数的阶乘，因为我们在枚举 的每一位为 的数字时，可能会重复计算某些排列，因此需要除以每个数字出现的次数的阶乘。
时间复杂度 。其中 为数组 的长度。
class Solution:
def numSquarefulPerms(self, nums: List[int]) -> int:
n = len(nums)
f = [[0] * n for _ in range(1 << n)]
for j in range(n):
f[1 << j][j] = 1
for i in range(1 << n):
for j in range(n):
if i >> j & 1:
for k in range(n):
if (i >> k & 1) and k != j:
s = nums[j] + nums[k]
t = int(sqrt(s))
if t * t == s:
f[i][j] += f[i ^ (1 << j)][k]
ans = sum(f[(1 << n) - 1][j] for j in range(n))
for v in Counter(nums).values():
ans //= factorial(v)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Backtracking expertise
- question_mark
Proficiency with pruning techniques
- question_mark
Efficiency in handling permutations and checking perfect square sums
常见陷阱
外企场景- error
Misunderstanding how to efficiently prune the search space
- error
Failing to handle duplicate numbers correctly
- error
Incorrectly checking perfect square conditions for sums of adjacent elements
进阶变体
外企场景- arrow_right_alt
Using dynamic programming to optimize the backtracking process
- arrow_right_alt
Reducing space complexity by optimizing hash lookup operations
- arrow_right_alt
Exploring alternative approaches with bit manipulation to track visited elements