สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums อาร์เรย์นี้มีจำนวนองค์ประกอบที่เป็นคู่ และมีค่าอื่น k เราต้องแยก nums ออกเป็นคู่ n/2 ตรง ๆ เพื่อให้ผลรวมของแต่ละคู่หารด้วย k ลงตัว หากเราทำได้ก็คืนค่าจริงหรือเท็จ
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[9,5,3,4,7,10,20,8] k =3 ผลลัพธ์จะเป็น True เพราะเราสามารถสร้างคู่เช่น (9,3), (5 ,7), (4,20), (8,10) ผลรวมของทุกคู่หารด้วย 3 ลงตัว
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
dp :=รายการใหม่
-
จำนวน:=0
-
สำหรับแต่ละ x เป็นตัวเลข ทำ
-
t:=k - (x mod k)
-
ถ้า t เหมือนกับ k แล้ว
-
นับ :=นับ + 1
-
-
มิฉะนั้น
-
ใส่ t ต่อท้าย dp
-
-
-
หากการนับ mod 2 ไม่เหมือนกับ 0 แล้ว
-
คืนค่าเท็จ
-
-
เรียงลำดับรายการ dp
-
ต่ำ :=0
-
สูง :=ขนาด dp - 1
-
ในขณะที่ต่ำ <สูง ทำ
-
ถ้า dp[low] + dp[high] ไม่เหมือนกับ k แล้ว
-
คืนค่าเท็จ
-
-
ต่ำ :=ต่ำ + 1
-
สูง :=สูง - 1
-
-
คืนค่า True
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
def solve(nums, k): dp=[] count=0 for x in nums: t=k-(x % k) if t == k: count+=1 else: dp.append(t) if count % 2 != 0: return False dp.sort() low = 0 high = len(dp)-1 while low < high: if dp[low] + dp[high] != k: return False low += 1 high -= 1 return True nums = [9,5,3,4,7,10,20,8] k = 3 print(solve(nums, k))
อินพุต
[9,5,3,4,7,10,20,8], 3
ผลลัพธ์
True
