Giả sử chúng ta có hai danh sách nums1 và nums2. Mỗi danh sách trong số hai danh sách này đại diện cho một vectơ ở dạng mã hóa thời lượng chạy. Vì vậy, như một ví dụ, một vectơ [1, 1, 1, 2, 2, 2, 2] được biểu diễn là [3, 1, 4, 2]. (vì có 3 cái và 4 cái hai). Vì vậy ta phải tìm tích chấm của hai vectơ này. (Tích số chấm là tổng của phép nhân khôn ngoan phần tử của các mục có trong hai vectơ).
Vì vậy, nếu đầu vào giống như nums1 =[2, 7, 5, 3] nums2 =[3, 5, 4, 2], thì đầu ra sẽ là 109 bởi vì, các vectơ giống như [7, 7, 3, 3 , 3, 3, 3] • [5, 5, 5, 2, 2, 2, 2] =7 * 5 + 7 * 5 + 3 * 5 + 3 * 2 + 3 * 2 + 3 * 2 + 3 * 2 =35 + 35 + 15 + 6 + 6 + 6 + 6 =109.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- ans:=0
- trong khi cả nums1 và nums2 đều không trống, hãy thực hiện
- val1:=phần tử cuối cùng từ nums1 và xóa mục cuối cùng
- count1:=phần tử cuối cùng từ nums1 và xóa mục cuối cùng
- val2:=phần tử cuối cùng từ nums2 và xóa mục cuối cùng
- count2:=phần tử cuối cùng từ nums2 và xóa mục cuối cùng
- ans:=ans + (val1 * val2) * (tối thiểu của count2 và count1)
- nếu count2> count1, thì
- chèn | count2 - count1 | ở cuối nums2
- chèn val2 vào cuối nums2
- ngược lại khi count1> count2, thì
- chèn | count2 - count1 | ở cuối nums1
- chèn val1 vào cuối nums1
- trả lại 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): ans = 0 while nums1 and nums2: val1 = nums1.pop() count1 = nums1.pop() val2 = nums2.pop() count2 = nums2.pop() ans += (val1 * val2) * min(count2, count1) if count2 > count1: nums2.append(abs(count2 - count1)) nums2.append(val2) elif count1 > count2: nums1.append(abs(count2 - count1)) nums1.append(val1) return ans nums1 = [2, 7, 5, 3] nums2 = [3, 5, 4, 2] print(solve(nums1, nums2))
Đầu vào
[2, 7, 5, 3], [3, 5, 4, 2]
Đầu ra
109