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

पायथन में कोर्स शेड्यूल II


मान लीजिए कुल n कोर्स हैं, ये 0 से n-1 तक लेबल किए गए हैं। कुछ कोर्स के प्रीरिक्विज़िट्स हो सकते हैं, दिए गए कुल कोर्स की संख्या और प्रीरिक्विज़िट जोड़े की लिस्ट को देखते हुए, हमें कोर्स का ऑर्डर ढूंढना है जिसे हमें सभी कोर्स खत्म करने के लिए लेना चाहिए। कई सही ऑर्डर हो सकते हैं, हमें उनमें से केवल एक ढूंढना है। यदि सभी कोर्स खत्म करना असंभव है, तो एक खाली ऐरे लौटाएं।

इसलिए यदि इनपुट 2, [[1, 0]] जैसा है, तो परिणाम [0,1] होगा। लेने के लिए कुल 2 कोर्स हैं। कोर्स नंबर 1 लेने के लिए हमें कोर्स 0 खत्म करना चाहिए। तो सही कोर्स ऑर्डर [0,1] है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

  • मुख्य मेथड में, यह numCourses, और prerequisites लेगा: यह इस तरह कार्य करेगा -

  • in_degree नामक एक ऐरे परिभाषित करें, और इसे सभी नोड्स के सभी इन-डिग्री से भरें, और adj := ग्राफ की एडजेसेंसी लिस्ट

  • visited नामक एक ऐरे परिभाषित करें, और इसे 0 से भरें, इसका आकार numCourses के समान है

  • एक खाली स्टैक परिभाषित करें।

  • i को 0 से numCourses तक रेंज में

    • यदि visited[i] false है और नोड i का dfs false है स्टैक को इसमें पास करके, तो

      • एक खाली लिस्ट लौटाएं

  • स्टैक एलिमेंट्स को रिवर्स ऑर्डर में लौटाएं।

उदाहरण

बेहतर समझ पाने के लिए निम्न कार्यान्वयन देखें -

class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        in_degree,adj=self.create_adj(numCourses,prerequisites)
        visited = [0 for i in range(numCourses)]
        stack = []
        for i in range(numCourses):
            if not visited[i] and not self.dfs(i,visited,stack,adj):
                return []
        return stack[::-1]
    def create_adj(self,n,graph):
        adj = {}
        in_degree= [0 for i in range(n)]
        for i in graph:
            in_degree[i[0]]+=1
            if i[1] in adj:
                adj[i[1]].append(i[0])
            else:
                adj[i[1]] = [i[0]]
        return in_degree,adj
    def dfs(self, node, visited,stack,adj):
        if visited[node] == -1:
            return False
        if visited[node] == 1:
            return True
        visited[node] = -1
        if node in adj:
            for i in adj[node]:
                if not self.dfs(i,visited,stack,adj):
                    return False
        visited[node]=1
        stack.append(node)
        return True

ob = Solution()
print(ob.findOrder(2, [[1,0]]))

इनपुट

2 [[1,0]]

आउटपुट

[0,1]

  1. - Python में इवेंट शेड्यूलर

    Python हमें विशिष्ट समय पर कार्य चलाने के लिए एक जेनेरिक शेड्यूलर देता है। हम schedule नामक एक मॉड्यूल का उपयोग करेंगे। इस मॉड्यूल में हम वांछित शेड्यूल प्राप्त करने के लिए every फ़ंक्शन का उपयोग करते हैं। नीचे every फ़ंक्शन के साथ उपलब्ध सुविधाएं हैं। सिंटैक्स Schedule.every(n).[timeframe] यहां n

  1. - पायथन में एकाधिक मान वापस करना

    पायथन फ़ंक्शन एकाधिक मान वापस कर सकते हैं। इन मानों को सीधे वेरिएबल्स में संग्रहीत किया जा सकता है। एक फ़ंक्शन एक वेरिएबल वापस करने तक सीमित नहीं है, यह शून्य, एक, दो या अधिक मान वापस कर सकता है।यह पायथन की डिफ़ॉल्ट संपत्ति है कि वह एकाधिक मान/वेरिएबल वापस कर सकता है जो C++ या Java जैसी कई अन्य प्रो

  1. - Python में एकाधिक मान कैसे लौटाएं?

    टपल, लिस्ट, डिक्शनरी या यूजर डिफाइंड क्लास के ऑब्जेक्ट के रूप में फंक्शन से एकाधिक मान लौटाना संभव है। टपल के रूप में लौटाएं >>> def function(): ... a = 10; b = 10 ... return a, b >>> x = function() >>> type(x) >>> x (10, 10) >>> x, y = function