Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में रन-लेंथ एन्कोडेड वेक्टर का डॉट प्रोडक्ट खोजने का प्रोग्राम

मान लीजिए हमारे पास दो सूचियाँ 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
  1. टारगेट को धारण करने वाले सबसे छोटे चक्र की लंबाई ज्ञात करने का पायथन प्रोग्राम टारगेट को धारण करने वाले सबसे छोटे चक्र की लंबाई ज्ञात करने का पायथन प्रोग्राम

    मान लीजिए हमारे पास एक निर्देशित ग्राफ की आसन्न सूची है, जहां इंडेक्स i पर प्रत्येक सूची नोड i से जुड़े नोड्स को दर्शाती है। हमारे पास एक टारगेट मान भी है। हमें उस सबसे छोटे चक्र की लंबाई ढूंढनी है जिसमें टारगेट शामिल है। यदि कोई समाधान नहीं है तो -1 लौटाएं। उदाहरण के लिए, यदि इनपुट इस तरह है: tar

  1. - पायथन में गैर-साझा शब्दों की अधिकतम लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास words नामक लोअरकेस वर्णमाला स्ट्रिंग्स की एक सूची है, हमें दो अलग-अलग शब्दों की लंबाई का अधिकतम योग ढूंढना है जो एक सामान्य अक्षर साझा नहीं करते। इसलिए, यदि इनपुट words = [abcd, mno, abdcmno, amno] जैसा है, तो आउटपुट 7 होगा, क्योंकि जो शब्द कोई सामान्य अक्षर साझा नहीं करते वे [ab

  1. - पायथन में सबसे लंबे पैलिंड्रोमिक सबस्ट्रिंग की लंबाई ढूंढने का प्रोग्राम

    मान लीजिए हमारे पास एक स्ट्रिंग S है। हमें S में सबसे लंबे पैलिंड्रोमिक सबस्ट्रिंग की लंबाई ढूंढनी है। हम मान रहे हैं कि स्ट्रिंग S की लंबाई 1000 है। उदाहरण के लिए, यदि स्ट्रिंग BABAC है, तो सबसे लंबा पैलिंड्रोमिक सबस्ट्रिंग BAB है और इसकी लंबाई 3 है।समाधान दृष्टिकोण (डायनामिक प्रोग्रामिंग)इस समस्या