Chương trình tính tích vô hướng của vector mã hóa độ dài chạy Python

Hai danh sách nums1, nums2 biểu diễn vector dạng mã hóa độ dài chạy (run-length encoding). Ví dụ: [1,1,1,2,2,2,2] → [3,1,4,2] (3 số 1, 4 số 2). Tính tích vô hướng của hai vector này.

Ví dụ: nums1=[2,7,5,3], nums2=[3,5,4,2] → 109 (vector: [7,7,3,3,3,3,3]·[5,5,5,2,2,2,2]).

Giải thuật (Xử lý từ cuối mảng)

1. Lấy cặp (val, count) từ cuối mỗi mảng
2. Cộng dồn (val1 * val2) * min(count1, count2) vào kết quả
3. Phần dư của count lớn hơn đẩy ngược vào mảng tương ứng
4. Lặp cho đến khi một mảng rỗng

Ví dụ triển khai

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