สมมติว่าเรามีรายการตัวเลขที่เรียกว่าเป้าหมาย ตอนนี้ ให้เราพิจารณารายการ X ที่มีความยาวเท่ากับรายการที่กำหนด และ X จะถูกเติมด้วย 1s เราสามารถดำเนินการต่อไปนี้กี่ครั้งก็ได้ตามต้องการ:ใช้ดัชนี i ใดๆ ใน X และตั้งค่า X[i] เป็นผลรวมปัจจุบันของ X สุดท้ายให้ตรวจสอบว่า X สามารถเปลี่ยนเป็นเป้าหมายได้หรือไม่
ดังนั้น หากอินพุตเหมือนเป้าหมาย =[5, 9, 3] ผลลัพธ์จะเป็น True ตามค่าเริ่มต้น X =[1, 1, 1] จากนั้นอัปเดตด้วยผลรวมทั้งหมด 3 อาร์เรย์จะเป็น [1, 1 , 3], ผลรวมปัจจุบันคือ 5, อัปเดตเป็น [5, 1, 3], ผลรวมปัจจุบัน 9 ดังนั้นรายการจะเป็น [5, 9, 3] และมันเป็นเป้าหมาย
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- ถ้า nums มีองค์ประกอบเพียงตัวเดียว
- คืนค่า จริง เมื่อ nums มี 1
- q :=คิวที่มีค่าลบของตัวเลขทั้งหมด nums
- สร้าง q เป็นฮีป
- s :=ผลรวมของตัวเลขทั้งหมดเป็นตัวเลข
- โอเค :=จริง
- ทั้งๆ ที่ ok ก็คือ จริง ก็ทำ
- x :=ลบองค์ประกอบออกจากฮีปและลบล้าง
- d :=s - x
- x2 :=x mod d if d> 1 มิฉะนั้น 1
- s :=s + x2 - x
- โอเค :=x ไม่เหมือนกับ x2
- x :=x2
- แทรก -x ลงในฮีป q
- คืนค่า จริง เมื่อองค์ประกอบทั้งหมดใน q เป็น -1
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
class Solution: def solve(self, nums): if len(nums) == 1: return nums == [1] from heapq import heapify, heappop, heappush q = [-x for x in nums] heapify(q) s = sum(nums) ok = True while ok: x = -heappop(q) d = s - x x2 = x % d if d > 1 else 1 s += x2 - x ok = x != x2 x = x2 heappush(q, -x) return all(x == -1 for x in q) ob = Solution() target = [5, 9, 3] print(ob.solve(target))
อินพุต
[5, 9, 3]
ผลลัพธ์
True
