Giả sử chúng ta có hai danh sách nums1 và nums2 trong đó mỗi phần tử trong cả hai danh sách nằm trong phạm vi từ 1 đến 6. Bây giờ hãy xem xét một phép toán mà theo đó, chúng ta có thể chọn một số từ nums1 hoặc nums2 và cập nhật giá trị của nó thành một số từ 1 đến 6. Chúng ta phải tìm số phép toán tối thiểu cần thiết để tổng của hai mảng này bằng nhau. Nếu chúng tôi không thể tìm thấy bất kỳ giải pháp nào, hãy trả về -1.
Vì vậy, nếu đầu vào giống như nums1 =[1, 4] nums2 =[5, 4, 4], thì đầu ra sẽ là 2, vì chúng ta có thể tạo 1 từ nums1 đến 6, vì vậy tổng nums1 là 10, sau đó thay đổi bất kỳ một 4 từ nums2 đến 1, vì vậy tổng của nó cũng là 10
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
sa:=tổng của tất cả các phần tử có trong nums1
-
sb:=tổng của tất cả các phần tử có trong nums2
-
if sa> sb, then
-
hoán đổi nums1 và nums2
-
hoán đổi sa và sb
-
-
sắp xếp danh sách nums1
-
sắp xếp danh sách nums2 theo thứ tự ngược lại
-
res:=0
-
cóc:=sb - sa
-
i:=0, j:=0
-
trong khi cóc> 0, thực hiện
-
res:=res + 1
-
nếu tôi
-
resa:=6 - nums1 [i]
-
resb:=nums2 [j] - 1
-
nếu resa> resb thì
-
cóc:=cóc - resa
-
i:=i + 1
-
-
nếu không,
-
cóc:=cóc - resb
-
j:=j + 1
-
-
ngược lại khi tôi
-
resa:=6 - nums1 [i]
-
cóc:=cóc - resa
-
i:=i + 1
-
-
ngược lại khi j
-
resb:=nums2 [j] - 1
-
cóc:=cóc - resb
-
j:=j + 1
-
-
nếu không,
-
trả về -1
-
-
-
-
trả lại res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
def solve(nums1, nums2): sa = sum(nums1) sb = sum(nums2) if sa > sb: nums1, nums2 = nums2, nums1 sa, sb = sb, sa nums1.sort() nums2.sort(reverse=True) res = 0 toadd = sb - sa i = 0 j = 0 while toadd > 0: res += 1 if i < len(nums1) and j < len(nums2): resa = 6 - nums1[i] resb = nums2[j] - 1 if resa > resb: toadd -= resa i += 1 else: toadd -= resb j += 1 elif i < len(nums1): resa = 6 - nums1[i] toadd -= resa i += 1 elif j < len(nums2): resb = nums2[j] - 1 toadd -= resb j += 1 else: return -1 return res nums1 = [1, 4] nums2 = [5, 4, 4] print(solve(nums1, nums2))
Đầu vào
[2,1,4,3,5,4]
Đầu ra
2