Giả sử chúng ta có hai mảng được gọi là nums1 và nums2. Các giá trị trong mảng nằm trong khoảng từ 1 đến 6 (bao gồm). Trong một thao tác, chúng ta có thể cập nhật bất kỳ giá trị nào trong bất kỳ mảng nào thành bất kỳ giá trị nào từ 1 đến 6. Chúng ta phải tìm số phép toán tối thiểu cần thiết để làm cho tổng giá trị trong nums1 bằng tổng giá trị trong nums2. Chúng tôi phải trả về -1 nếu không thể.
Vì vậy, nếu đầu vào giống như nums1 =[1,5,6], nums2 =[4,1,1], thì đầu ra sẽ là 2 vì chúng ta có thể thay đổi nums2 từ [4,1,1] thành [4, 1,6] trong thao tác đầu tiên và [4,2,6] trong thao tác thứ hai để biến nó bằng nums1.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
s1:=tổng của tất cả các phần tử trong nums1
-
s2:=tổng của tất cả các phần tử trong nums2
-
sắp xếp danh sách nums1 và sắp xếp danh sách nums2
-
nếu s1> s2 thì
-
hoán đổi nums1 và nums2
-
hoán đổi s1 và s2
-
-
ans:=0
-
left:=0, right:=size of nums2 -1
-
trong khi bên trái
=0, thực hiện -
nếu s1 giống s2 thì
-
trả lại ans
-
-
curr_left:=nums1 [left] nếu left
-
curr_right:=nums2 [right] nếu đúng> =0 nếu không thì 0
-
if 6-curr_left> =curr_right-1, then
-
s1:=s1 + tối thiểu là 6-curr_left và s2-s1
-
left:=left + 1
-
-
nếu không,
-
s2:=s2 - tối thiểu curr_right-1 và s2-s1
-
right:=right - 1
-
-
ans:=ans + 1
-
-
trả về -1 nếu s1 không giống s2 nếu không thì ans
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):
s1 = sum(nums1)
s2 = sum(nums2)
nums1.sort()
nums2.sort()
if s1>s2:
nums1, nums2 = nums2, nums1
s1, s2 = s2, s1
ans = 0
left, right = 0, len(nums2)-1
while(left<len(nums1) or right>=0):
if s1==s2:
return ans
curr_left = nums1[left] if left<len(nums1) else 7
curr_right = nums2[right] if right>=0 else 0
if 6-curr_left>=curr_right-1:
s1+= min(6-curr_left, s2-s1)
left+=1
else:
s2-= min(curr_right-1, s2-s1)
right-=1
ans+=1
return -1 if s1!=s2 else ans
nums1 = [1,5,6]
nums2 = [4,1,1]
print(solve(nums1, nums2)) Đầu vào
[1,5,6], [4,1,1]
Đầu ra
2