Ҳалли Leetcode Папкаи Гузориши Crawler


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Меркари
тӯда

Изҳороти мушкилот

Дар ин масъала, мо мавқеи худро дар системаи ҷузвдон пайгирӣ мекунем. Мо дар аввал дар ҷузвдони root ё ҷузвдони асосии ин система қарор дорем.
Мо дар ин ҷо асосан 3 намуди фармонҳо дорем. Фармонҳо дар шакли сатр мебошанд, ки ҳар як сатр фармонро ифода мекунад.

  •  "../" маънои онро дорад, ки ба ҷузвдони волидии ҷузвдони ҷорӣ гузаред (агар аллакай дар ҷузвдони root бошад, пас ба ҷое наравед).
  •  "./" дар ҷузвдони ҷорӣ бимонед.
  •  "X /" ба ҷузвдони сабти ҷузвдони ҷорӣ, ки номи х дорад, ворид шавед.

Ба мо пайдарпаии фармонҳо дода мешавад, ки аз 3 фармони боло иборат аст. Мо бояд шумораи камтарини амалиётро пайдо кунем, то пас аз таҳияи фармонҳои додашуда ба папкаи root баргардем.
масалан
гузоришҳо = ["d1 /", "d2 /Ø," .../ "," d21 /

Ҳалли Leetcode Папкаи Гузориши Crawler
Мо дар чуқурии 2 аз ҷузвдони решавӣ ҳастем. Аз ин рӯ, ҷавоби мо 2 хоҳад буд.

мисол

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

Шарҳ:

Ин амалиёти папкаи тағиротро "../" -ро 2 маротиба истифода баред ва ба ҷузвдони асосӣ баргардед.

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

Муносибати 1 (Истифодаи анбор)

Мо метавонем стеки номҳои файлҳоро истифода барем. Дар аввал анбори мо холӣ аст. Ҳар вақте ки мо бояд ба зерпапка гузарем, пас номи зерпапка ба стака ворид карда мешавад. Ҳамин тариқ, ҷузвдоне, ки мо ҳоло дар он ҳузур дорем, ҳамеша дар болои стек боқӣ хоҳад монд.
Ҳамин тавр, вақте ки мо бо “../” дучор меоем, ин маънои онро дорад, ки мо бояд аз ҷузвдони ҳозира бароем (яъне ба ҷузвдони волидайн гузарем), пас мо тафтиш мекунем, ки ҷузвдони ҷорӣ реша дорад. Агар не, пас мо унсури болоро аз стек мебарорем.
Ва албатта, вақте ки мо бо "./" дучор меоем, мо ҳеҷ коре намекунем.
Мо ин се ҳолатро бо истифодаи if else агар нардбон баррасӣ кунем.

Як чизро мо бояд дар ин ҷо донем, ки шумораи унсури дар стак мавҷудбуда мегӯяд, ки мо ҳоло дар ҷузвдони решавӣ дар кадом умқ ҳастем.
Ҳамин тариқ, мо андозаи стекро дар охир, яъне чуқуриро аз ҷузвдони root бармегардонем.

Татбиқи ҳалли Leetcode папкаи Crawler Log

Барномаи 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

Барномаи Java

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

Таҳлили мураккабӣ барои ҳалли Leetcode папкаи Crawler Log

Мураккабии вақт

O (n): Мо массиви додашудаи сатрҳоро хаттӣ мегузаронем ва амали стекро дар вақти O (1) дар ҳар як такрор иҷро мекунем. Ҳамин тавр, мураккабии вақт O (n) аст, ки n дарозии массиви вуруд аст.

Мураккабии фазо 

O (n): Мо стакаро истифода кардем, ки андозаи он ба дарозии массиви додашуда баробар шуда метавонад. Ҳамин тариқ, бадтарин мураккабии фазо O (n) мебошад.

Муносибати 2 (Истифодаи тағирёбандаи умқ)

Мушкилотро бо осонӣ пайгирӣ кардан мумкин аст, зеро танҳо як пайгирии тағирёбандаи умқро пайгирӣ кунед, ки асосан нишон медиҳад, ки мо аз ҷузвдони реша дар кадом умқ ҳастем.
Ҳар дафъае, ки мо ба ҷузвдони кудакӣ меравем, мо аз папкаи решавӣ ба масофаи 1 дур мешавем (яъне чуқурӣ ++)
Ҳар дафъае, ки мо ба ҷузвдони волидайн меравем, мо наздик шудан ба решаи ҷузвдонро бо масофаи 1. кам мекунем (яъне чуқурӣ -).
Дар хотир доред, ки мо метавонем танҳо ба ҷузвдони волидайн гузарем, агар мо дар ҷузвдони root набошем.
Ҳамин тавр, мо ба иҷрои фармонҳо аз чап ба рост дар a for шурӯъ хоҳем кард Давр .

  • Агар мо бо "../" дучор оем, мо тафтиш мекунем, ки дар ҷузвдони root ҳастем ё не. Агар не, пас мо чуқуриро 1 кам мекунем.
  • Дар акси ҳол, агар мо бо "./" дучор оем, мо бояд дар ҷузвдони ҷории худ бимонем, бинобар ин тағирёбанда дар умқи тағирот тағир намеёбад.
  • Дар акси ҳол, мо бояд ба яке аз ҷузвдонҳои кӯдаконамон гузарем. Ҳамин тариқ, мо чуқурии худро 1 зиёд мекунем.

Пас аз ҳамаи фармонҳо, тағирёбандаи умқи мо масофаро аз ҷузвдони root нигоҳ медорад. Мо онро ҳамчун натиҷа бармегардонем.

Татбиқи ҳалли Leetcode папкаи Crawler Log

Барномаи 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

Барномаи Java барои ҳалли Leetcode ҷузвдони Crawler Log

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

Таҳлили мураккабӣ барои ҳалли Leetcode папкаи Crawler Log

Мураккабии вақт

O (n): Мо ҳамаи фармонҳоро як маротиба иҷро карда истодаем. Ҳамин тавр, мураккабии вақт O (n) мебошад.

Мураккабии фазо 

О (1): мо танҳо як тағирёбандаи умқро истифода кардем. Ҳамин тариқ, мураккабии фазо O (1) мебошад.