क्रॉलर लॉग फ़ोल्डर Leetcode समाधान


कठिनाई स्तर आसान
में अक्सर पूछा मरकरी
धुआँरा

समस्या का विवरण

इस समस्या में, हम एक फ़ोल्डर सिस्टम में अपनी स्थिति पर नज़र रखते हैं। हम शुरू में रूट फ़ोल्डर या इस सिस्टम के मुख्य फ़ोल्डर में हैं।
हमारे यहां मूल रूप से 3 तरह के कमांड हैं। कमांड स्ट्रिंग के रूप में होते हैं जिसमें प्रत्येक स्ट्रिंग का अर्थ कमांड होता है।

  •  "../" का अर्थ है वर्तमान फ़ोल्डर के मूल फ़ोल्डर में जाएं (यदि पहले से रूट फ़ोल्डर में है तो कहीं भी न जाएं)।
  •  वर्तमान फ़ोल्डर में "./" रहें।
  •  "X /" वर्तमान फ़ोल्डर के बच्चे फ़ोल्डर में जाता है जिसका नाम x है।

हमें आदेशों का एक क्रम दिया गया है जो कि 3 आदेशों से ऊपर का संयोजन है। हमें दिए गए आदेशों को आगे बढ़ाने के बाद रूट फ़ोल्डर में वापस जाने के लिए न्यूनतम संख्या में ऑपरेशन का पता लगाना होगा।
जैसे
लॉग्स = ["डी 1 /", "डी 2 / रिटर्न्स../", "डी 21 / रिट्रीटमेंट्स। /"]

क्रॉलर लॉग फ़ोल्डर Leetcode समाधान
हम रूट फ़ोल्डर से गहराई 2 पर हैं। इसलिए, हमारा उत्तर 2 होगा।

उदाहरण

logs = ["d1/","d2/","../","d21/","./"]
2

स्पष्टीकरण:

इस परिवर्तन फ़ोल्डर ऑपरेशन का उपयोग "../" 2 बार करें और मुख्य फ़ोल्डर में वापस जाएं।

logs = ["d1/","d2/","./","d3/","../","d31/"]
3

दृष्टिकोण 1 (स्टैक का उपयोग करके)

हम फ़ाइल नामों के ढेर का उपयोग कर सकते हैं। प्रारंभ में हमारा ढेर खाली है। जब भी हमें किसी सबफ़ोल्डर में जाना होता है तो सबफ़ोल्डर का नाम स्टैक में धकेल दिया जाता है। इस प्रकार, जिस फ़ोल्डर में हम वर्तमान में मौजूद हैं वह हमेशा स्टैक के शीर्ष पर रहेगा।
इसलिए, जब भी हमारा सामना "../" से होता है, तो हमें वर्तमान फ़ोल्डर से बाहर आना होगा (यानी मूल फ़ोल्डर में जाना होगा), तो हम जांच करेंगे कि क्या वर्तमान फ़ोल्डर जड़ है। यदि नहीं, तो हम स्टैक से शीर्ष तत्व को पॉप करेंगे।
और निश्चित रूप से जब भी हमारा सामना एक “./” से होगा, हमें कुछ नहीं करना है।
हम इन तीन मामलों को संभाल रहे हैं अगर सीढ़ी का उपयोग कर रहे हैं।

एक बात हमें यहां जान लेनी चाहिए कि स्टैक में मौजूद तत्व की संख्या कह रही है कि हम वर्तमान में रूट फ़ोल्डर से कितनी गहराई पर हैं।
इस प्रकार, हम अंत में ढेर के आकार को वापस कर देंगे अर्थात रूट फ़ोल्डर से गहराई।

क्रॉलर लॉग फ़ोल्डर Leetcode समाधान के लिए कार्यान्वयन

C ++ प्रोग्राम

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int minOperations(vector<string>& logs) {
        stack<string>stack;
        for(string log:logs){
            if(log=="../"){
                if(stack.size()>0)stack.pop();
            }
            else if(log=="./");
            else{
                stack.push(log);
            }
        }
        return stack.size();
    }
int main()
{
    vector<string>logs{"d1/","d2/","../","d21/","./"};
    cout<<minOperations(logs);
}
2

जावा प्रोग्राम

import java.util.*;
import java.lang.*;

class Solution
{  
    public static int minOperations(String[] logs) {
        Stack<String>stack=new Stack<String>();
        for(String log:logs){
            if(log.equals("../")){
                if(stack.size()>0)stack.pop();
            }
            else if(log.equals("./"));
            else{
                stack.push(log);
            }
        }
        return stack.size();
    }
    
    public static void main(String args[])
    {
        String[]logs={"d1/","d2/","../","d21/","./"};
        
        System.out.println(minOperations(logs));
    }
}
2

क्रॉलर लॉग फ़ोल्डर लेकोडकोड समाधान के लिए जटिलता विश्लेषण

समय जटिलता

पर): हम रैखिक रूप से स्ट्रिंग्स के दिए गए एरे को ट्रेस कर रहे हैं और प्रत्येक पुनरावृति में O (1) समय में स्टैक ऑपरेशन कर रहे हैं। इस प्रकार, समय जटिलता O (n) है, जहां n इनपुट सरणी की लंबाई है।

अंतरिक्ष जटिलता 

पर): हमने एक स्टैक का उपयोग किया है जिसका आकार दी गई इनपुट सरणी लंबाई के बराबर हो सकता है। इस प्रकार, सबसे खराब स्थिति अंतरिक्ष जटिलता O (n) है।

दृष्टिकोण 2 (गहराई चर का उपयोग करके)

समस्या को आसानी से हल किया जा सकता है बस एक गहन चर को ट्रैक करते रहें जो मूल रूप से दिखा रहा है कि हम रूट फ़ोल्डर से किस गहराई पर हैं।
हर बार जब हम चाइल्ड फोल्डर में जा रहे होते हैं, तो हम रूट फोल्डर से दूरी 1 से दूर जा रहे होते हैं (यानी गहराई ++)
हर बार जब हम मूल फ़ोल्डर में जा रहे होते हैं, तो हम दूरी 1 (यानी गहराई) से रूट फ़ोल्डर के करीब आ रहे हैं।
ध्यान दें कि हम केवल मूल फ़ोल्डर में जा सकते हैं यदि हम रूट फ़ोल्डर में नहीं हैं।
तो, हम थोड़ी देर में कमांड को बाएं से दाएं पर अमल करना शुरू कर देंगे पाश .

  • यदि हम “../” का सामना करेंगे तो हम जाँचेंगे कि हम रूट फोल्डर में हैं या नहीं। यदि नहीं, तो हम 1 से गहराई कम कर देंगे।
  • यदि हम मुठभेड़ करेंगे "तो।"
  • और हमें अपने बच्चे के एक फोल्डर में जाना है। इस प्रकार, हम अपनी गहराई को 1 से बढ़ा देंगे।

सभी कमांड के बाद, हमारी गहराई चर रूट फ़ोल्डर से दूरी को संग्रहीत कर रही है। हम इसे आउटपुट के रूप में वापस करेंगे।

क्रॉलर लॉग फ़ोल्डर Leetcode समाधान के लिए कार्यान्वयन

C ++ प्रोग्राम

#include <iostream>
#include <vector>
using namespace std;

int minOperations(vector<string>& logs)
{
    int depth=0;
    for(string log:logs)
    {
        if(log=="../")
        {
            if(depth>0)depth--;//moving to parent folder only if depth>0 i.e. current folder is    
                                 other than main folder 
        }
        else if(log=="./");    //staying to current folder
        else depth++;          //moving to child folder
    }
    return depth;
}
int main()
{
    vector<string>logs{"d1/","d2/","../","d21/","./"};
    cout<<minOperations(logs);
}
2

क्रॉलर लॉग फोल्डर लेटकोड सॉल्यूशन के लिए जावा प्रोग्राम

import java.util.*;
import java.lang.*;

class Solution
{  
    public static int minOperations(String[] logs)
    {
        int depth=0;
        for(String log:logs)
        {
            if(log.equals("../"))
            {
                if(depth>0)depth--;//moving to parent folder only if depth>0 i.e. current folder is other than main folder 
            }
            else if(log.equals("./"));  //staying to current folder
            else depth++;               //moving to child folder
        }
        return depth;
    }
    
    public static void main(String args[])
    {
        String[]logs={"d1/","d2/","../","d21/","./"};
        
        System.out.println(minOperations(logs));
    }
}
2

क्रॉलर लॉग फ़ोल्डर लेकोडकोड समाधान के लिए जटिलता विश्लेषण

समय जटिलता

पर): हम सभी कमांड को एक बार निष्पादित कर रहे हैं। इस प्रकार, समय जटिलता O (n) है।

अंतरिक्ष जटिलता 

ओ (1): हमने केवल एक गहन चर का उपयोग किया है। इस प्रकार, अंतरिक्ष जटिलता हे (1) है।