Giả sử chúng ta có một danh sách các số được gọi là target. Bây giờ chúng ta hãy xem xét một danh sách X có cùng độ dài với danh sách đã cho và X được điền bằng 1s. Chúng ta có thể thực hiện thao tác sau bao nhiêu lần tùy thích:Lấy bất kỳ chỉ số i nào trong X và đặt X [i] thành tổng hiện tại của X. Cuối cùng kiểm tra xem X có thể biến thành mục tiêu hay không.
Vì vậy, nếu đầu vào là target =[5, 9, 3], thì đầu ra sẽ là True như ban đầu X =[1, 1, 1], sau đó cập nhật nó với tổng tổng là 3, mảng sẽ là [1, 1 , 3], tổng hiện tại là 5, hãy cập nhật nó [5, 1, 3], tổng hiện tại là 9, vì vậy danh sách sẽ là [5, 9, 3] và nó là đích.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
- nếu nums chỉ có một phần tử, thì
- trả về true khi num có 1
- q:=một hàng đợi có giá trị âm của tất cả các số là nums
- tạo q thành đống
- s:=tổng của tất cả các số trong nums
- ok:=True
- trong khi ok là Đúng, hãy thực hiện
- x:=xóa phần tử khỏi heap và phủ định nó
- d:=s - x
- x2:=x mod d nếu d> 1 nếu không 1
- s:=s + x2 - x
- ok:=x không giống x2
- x:=x2
- chèn -x vào heap q
- trả về true khi tất cả các phần tử trong q là -1
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Ví dụ
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))
Đầu vào
[5, 9, 3]
Đầu ra
True