मान लीजिए हमारे पास दो सूचियाँ 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।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
ans := 0- जब
nums1औरnums2दोनों गैर-खाली हों, करें:val1 := nums1 से अंतिम तत्व लें और अंतिम आइटम हटाएंcount1 := nums1 से अंतिम तत्व लें और अंतिम आइटम हटाएंval2 := nums2 से अंतिम तत्व लें और अंतिम आइटम हटाएंcount2 := nums2 से अंतिम तत्व लें और अंतिम आइटम हटाएंans := ans + (val1 * val2) * (count2 और count1 का न्यूनतम)- यदि
count2 > count1, तो:|count2 - count1|कोnums2के अंत में डालेंval2कोnums2के अंत में डालें
- अन्यथा जब
count1 > count2, तो:|count2 - count1|कोnums1के अंत में डालें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