สมมติว่าเรามีรายการหมายเลขที่เรียกว่า nums เราต้องหาจำนวนการเรียงสับเปลี่ยนของ num โดยที่ผลรวมของค่าที่อยู่ติดกันทุกคู่เป็นกำลังสองสมบูรณ์ การเรียงสับเปลี่ยน A และ B สองครั้งจะไม่ซ้ำกันเมื่อมีดัชนี i โดยที่ A[i] ไม่เหมือนกับ B[i]
ดังนั้น หากอินพุตเป็น nums =[2, 9, 7] ผลลัพธ์จะเป็น 2 ตามที่เรามี [2, 7, 9] และ [9, 7, 2]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
res :=0
-
กำหนดฟังก์ชัน util() นี่จะใช้เวลาฉัน
-
ถ้า i + 1 เท่ากับขนาดของ nums แล้ว
-
res :=res + 1
-
กลับ
-
-
เยี่ยมชม :=ชุดว่างใหม่
-
สำหรับ j ในช่วง i + 1 ถึงขนาดของ nums ทำ
-
s :=nums[i] + nums[j]
-
ถ้า s ไม่ถูกเข้าชม และ (รากที่สองของ s)^2 คือ s แล้ว
-
ทำเครื่องหมายว่าเข้าชมแล้ว
-
สลับ nums[i + 1] และ nums[j]
-
util(i + 1)
-
สลับ nums[i + 1] และ nums[j]
-
-
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
เข้าชมแล้ว :=ชุดใหม่
-
สำหรับฉันในช่วง 0 ถึงขนาดของ nums ทำ
-
สลับ nums[i] และ nums[0]
-
หากไม่ได้เยี่ยมชม nums[0] แล้ว
-
util(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
