程序,计算Python中相邻对的和为完美平方的排列数
假设我们有一个称为nums的数字列表。我们必须找到num的排列数量,以使每对相邻值的总和是一个完美的平方。当存在一些索引i(其中A[i]与B[i]不同)时,两个置换A和B是唯一的。
因此,如果输入像nums=[2,9,7],则输出将为2,因为我们有[2,7,9]和[9,7,2]
为了解决这个问题,我们将遵循以下步骤-
res:=0
定义一个功能util()。这需要我
如果i+1与nums的大小相同,则
res:=res+1
返回
访问过:=一个新的空集
对于范围i+1到nums大小的j
将s标记为已访问
交换nums[i+1]和nums[j]
实用程序(i+1)
交换nums[i+1]和nums[j]
s:=nums[i]+nums[j]
如果未访问s并且(s的平方根)^2为s,则
从主要方法中执行以下操作-
参观了:=一套新的
对于范围从0到nums的i,执行
实用程序
交换nums[i]和nums[0]
如果未访问nums[0],则
将nums[0]标记为已访问
交换nums[i]和nums[0]
返回资源
让我们看下面的实现以更好地理解-
示例
from math import sqrt class Solution: def solve(self, nums): self.res = 0 def util(i): if i + 1 == len(nums): self.res += 1 return visited = set() for j in range(i + 1, len(nums)): s = nums[i] + nums[j] if s not in visited and int(sqrt(s)) ** 2 == s: visited.add(s) nums[i + 1], nums[j] = nums[j], nums[i + 1] util(i + 1) nums[i + 1], nums[j] = nums[j], nums[i + 1] visited = set() for i in range(len(nums)): nums[i], nums[0] = nums[0], nums[i] if nums[0] not in visited: util(0) visited.add(nums[0]) nums[i], nums[0] = nums[0], nums[i] return self.res ob = Solution() nums = [2, 9, 7] print(ob.solve(nums))
输入值
[2, 9, 7]输出结果
2