สมมติว่าเรามีสองรายการ nums1 และ nums2 แต่ละรายการแสดงเวกเตอร์ในรูปแบบ Run-Length Encoding ตัวอย่างเช่น เวกเตอร์ [1, 1, 1, 2, 2, 2, 2] แสดงเป็น [3, 1, 4, 2] (เพราะมี 1 สามตัว และ 2 สี่ตัว) เราต้องหาผลคูณสเกลาร์ (dot product) ของเวกเตอร์ทั้งสอง (ผลรวมของการคูณสมาชิกแต่ละคู่ในสองเวกเตอร์)
เช่น ถ้าอินพุตคือ nums1 = [2, 7, 5, 3], nums2 = [3, 5, 4, 2] ผลลัพธ์จะเป็น 109 เพราะเวกเตอร์คือ [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
ขั้นตอนการแก้ปัญหา
ans := 0- ในขณะที่
nums1และnums2ทั้งคู่ไม่ว่าง:val1 := นำสมาชิกสุดท้ายจาก nums1 ออก,count1 := นำสมาชิกสุดท้ายจาก nums1 ออกval2 := นำสมาชิกสุดท้ายจาก nums2 ออก,count2 := นำสมาชิกสุดท้ายจาก nums2 ออกans := ans + (val1 * val2) * min(count2, count1)- ถ้า
count2 > count1แทรก|count2 - count1|และval2กลับเข้าnums2 - มิฉะนั้นถ้า
count1 > count2แทรก|count2 - count1|และval1กลับเข้าnums1
- คืนค่า
ans
ตัวอย่างการใช้งาน
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))
อินพุต
[2, 7, 5, 3], [3, 5, 4, 2]
เอาต์พุต
109
