資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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 次瀏覽
廣告