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

पायथन में मिन और मैक्स का अंतर k से कम वाले सबसे लंबे सबलिस्ट की लंबाई खोजने का प्रोग्राम


मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और एक मान k है, हमें सबसे लंबे सबलिस्ट की लंबाई ढूंढनी है जहां सबसे बड़े और सबसे छोटे तत्व का निरपेक्ष अंतर k से कम या बराबर हो।

उदाहरण के लिए, यदि इनपुट nums = [2, 4, 6, 10] और k = 4 है, तो आउटपुट 3 होगा, क्योंकि हम [2, 4, 6] चुन सकते हैं जहां निरपेक्ष अंतर 4 है।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (स्लाइडिंग विंडो + डीक्यू):

  • दो डबल-एंडेड क्यू maxd, mind बनाएं
  • i := 0, res := 1
  • प्रत्येक इंडेक्स j और मान a के लिए A में:
    • जब तक maxd खाली नहीं और a > maxd[-1]: maxd.pop()
    • जब तक mind खाली नहीं और a < mind[-1]: mind.pop()
    • a को maxd और mind के अंत में डालें
    • जब तक maxd[0] - mind[0] > limit:
      • यदि maxd[0] == A[i]: maxd.popleft()
      • यदि mind[0] == A[i]: mind.popleft()
      • i += 1
    • res := max(res, j-i+1)
  • res लौटाएं

उदाहरण कोड

from collections import deque

class Solution:
    def solve(self, A, limit):
        maxd = deque()
        mind = deque()
        i = 0
        res = 1
        for j, a in enumerate(A):
            while maxd and a > maxd[-1]:
                maxd.pop()
            while mind and a < mind[-1]:
                mind.pop()
            maxd.append(a)
            mind.append(a)
            while maxd[0] - mind[0] > limit:
                if maxd[0] == A[i]:
                    maxd.popleft()
                if mind[0] == A[i]:
                    mind.popleft()
                i += 1
            res = max(res, j - i + 1)
        return res

ob = Solution()
nums = [2, 4, 6, 10]
k = 4
print(ob.solve(nums, k))

इनपुट

[2, 4, 6, 10], 4

आउटपुट

3

  1. पायथन में नोड और उसके वंशज के बीच अंतर खोजने का प्रोग्राम पायथन में नोड और उसके वंशज के बीच अंतर खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें किसी भी नोड और उसके वंशजों के बीच सबसे बड़ा निरपेक्ष अंतर ढूंढना है।उदाहरण के लिए, यदि इनपुट ट्री है:तो आउटपुट 7 होगा क्योंकि सबसे बड़ा निरपेक्ष अंतर नोड्स 8 और 1 के बीच है।समाधान दृष्टिकोणइसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (पोस्ट-ऑर्डर

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

    मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, और हमें nums में सबसे लंबी सबलिस्ट की लंबाई ढूंढनी है जिसमें लगातार संख्याओं के बीच असमानता का संबंध बारी-बारी से कम-से-कम और अधिक-से-अधिक ऑपरेशन के बीच बदलता हो। पहले दो संख्याओं की असमानता या तो कम-से-कम या अधिक-से-अधिक हो सकती है। उदाहरण के लि

  1. - पायथन में K-आकार की सूची खोजने का प्रोग्राम जहां सबसे बड़े और सबसे छोटे आइटम का अंतर न्यूनतम हो

    मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और एक पूर्णांक k है। हमें nums से तत्व चुनकर आकार k की एक सूची बनानी है जिससे सूची में सबसे बड़े और सबसे छोटे पूर्णांक का अंतर जितना संभव हो उतना कम हो। और हमें यह अंतर लौटाना है। उदाहरण के लिए, यदि इनपुट nums = [3, 11, 6, 2, 9], k = 3 है, तो आउटपुट