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