Giả sử chúng ta có một danh sách các số được gọi là nums. Chúng ta phải tìm số hoán vị của các num sao cho tổng của mọi cặp giá trị liền kề là một hình vuông hoàn hảo. Hai hoán vị A và B là duy nhất khi có một chỉ số i nào đó trong đó A [i] không giống với B [i].
Vì vậy, nếu đầu vào là nums =[2, 9, 7], thì đầu ra sẽ là 2, vì chúng ta có [2, 7, 9] và [9, 7, 2]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
res:=0
-
Định nghĩa một hàm dùng (). Điều này sẽ mất tôi
-
nếu i + 1 giống với kích thước của nums thì
-
res:=res + 1
-
trở lại
-
-
đã ghé thăm:=một tập hợp trống mới
-
đối với j trong phạm vi i + 1 đến kích thước của nums, thực hiện
-
s:=nums [i] + nums [j]
-
nếu s không được truy cập và (căn bậc hai của s) ^ 2 là s, thì
-
đánh dấu là đã ghé thăm
-
hoán đổi nums [i + 1] và nums [j]
-
sử dụng (i + 1)
-
hoán đổi nums [i + 1] và nums [j]
-
-
-
Từ phương thức chính, hãy làm như sau -
-
đã ghé thăm:=một tập hợp mới
-
đối với tôi trong phạm vi từ 0 đến kích thước của nums, hãy thực hiện
-
hoán đổi nums [i] và nums [0]
-
nếu nums [0] không được truy cập thì
-
sử dụng (0)
-
-
đánh dấu nums [0] là đã truy cập
-
hoán đổi nums [i] và nums [0]
-
-
trả lại res
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầu vào
[2, 9, 7]
Đầu ra
2