Python程序：计算相邻对之和为完全平方数的排列数

假设我们有一个名为nums的数字列表。我们必须找到nums的排列数，使得每对相邻值的和都是完全平方数。当存在某个索引i使得A[i]与B[i]不同时，两个排列A和B是唯一的。

因此，如果输入类似于nums = [2, 9, 7]，则输出将为2，因为我们有[2, 7, 9]和[9, 7, 2]

为了解决这个问题，我们将遵循以下步骤：

  • res := 0

  • 定义一个函数util()。这将接收i作为参数

  • 如果i + 1等于nums的大小，则

    • res := res + 1

    • 返回

  • visited := 一个新的空集合

  • 对于j从i + 1到nums的大小，执行以下操作：

    • s := nums[i] + nums[j]

    • 如果s未被访问过并且(s的平方根)^2等于s，则

      • 标记s为已访问

      • 交换nums[i + 1]和nums[j]

      • util(i + 1)

      • 交换nums[i + 1]和nums[j]

  • 在主方法中执行以下操作：

  • visited := 一个新的集合

  • 对于i从0到nums的大小，执行以下操作：

    • 交换nums[i]和nums[0]

    • 如果nums[0]未被访问过，则

      • util(0)

    • 标记nums[0]为已访问

    • 交换nums[i]和nums[0]

  • 返回res

让我们看下面的实现来更好地理解：

示例

在线演示

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

更新于：2020-12-26

144 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告