目录

0996:平方数组的数目(1932 分)

力扣第 124 场周赛第 4 题

题目

如果一个数组的任意两个相邻元素之和都是 完全平方数 ,则该数组称为 平方数组

给定一个整数数组 nums,返回所有属于 平方数组 nums 的排列数量。

如果存在某个索引 i 使得 perm1[i] != perm2[i],则认为两个排列 perm1perm2 不同。

示例 1:

输入:nums = [1,17,8]
输出:2
解释:[1,8,17] 和 [17,8,1] 是有效的排列。

示例 2:

输入:nums = [2,2,2]
输出:1

提示:

  • 1 <= nums.length <= 12
  • 0 <= nums[i] <= 109

相似问题:

分析

#1

  • 典型的状压 dp,令 dfs(st,i) 代表子集 st 且末尾是 nums[i] 的排列数,枚举下一个数即可递归
  • 需要去掉重复的排列,可以利用组合数学的知识,对于重复 v 次的数,除以 v 的阶乘即可
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def numSquarefulPerms(self, nums: List[int]) -> int:
        @cache
        def dfs(st,i):
            if st==(1<<n)-1:
                return 1
            res,x = 0,nums[i]
            for j,y in enumerate(nums):
                if not st&1<<j and (i==-1 or isqrt(x+y)**2==x+y):
                    res += dfs(st|1<<j,j)
            return res

        n = len(nums)
        s = dfs(0,-1)
        for v in Counter(nums).values():
            s //= factorial(v)
        return s

171 ms

#2

  • 解决重复排列还有种常用方法:枚举时,在相同的数中只考虑第一个
  • 本题中,将 nums 排序,枚举到 nums[i] 时,假如 nums[i-1]=nums[i] 且 i-1 位于子集 st 中,那么 nums[i] 不考虑

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def numSquarefulPerms(self, nums: List[int]) -> int:
        @cache
        def dfs(st,i):
            if st==(1<<n)-1:
                return 1
            res,x = 0,nums[i]
            for j,y in enumerate(nums):
                if j and nums[j-1]==y and not st&1<<(j-1):
                    continue
                if not st&1<<j and (i==-1 or isqrt(x+y)**2==x+y):
                    res += dfs(st|1<<j,j)
            return res

        n = len(nums)
        nums.sort()
        return dfs(0,-1)

0 ms