תיקיית יומן הסורקים פתרון Leetcode


רמת קושי קַל
נשאל לעתים קרובות מרצרי
לערום

הצהרת בעיה

בבעיה זו אנו ממשיכים לעקוב אחר מיקומנו במערכת תיקיות. בתחילה אנו נמצאים בתיקיית הבסיס או בתיקיה הראשית של מערכת זו.
יש לנו בעצם 3 סוגים של פקודות כאן. הפקודות הן בצורה של מחרוזת בה כל מחרוזת פירושה פקודה.

  •  "../" פירושו לעבור לתיקיית האב של התיקיה הנוכחית (אם כבר בתיקיית הבסיס אז אל תלך לשום מקום).
  •  "./" הישאר בתיקיה הנוכחית.
  •  "X /" נכנס לתיקיית הצאצא של התיקיה הנוכחית אשר יש לה שם x.

אנו מקבלים רצף של פקודות שהוא שילוב של מעל 3 פקודות. עלינו לגלות את מספר הפעולות המינימלי כדי לחזור לתיקיית השורש לאחר ביצוע הפקודות הנתונות.
לְמָשָׁל
יומנים = [“d1 /”, ”d2 /”,”../”, ”d21 /”,”./”]

תיקיית יומן הסורקים פתרון Leetcode
אנחנו בעומק 2 מתיקיית השורש. לפיכך, תשובתנו תהיה 2.

דוגמה

logs = ["d1/","d2/","../","d21/","./"]
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

תוכנית 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 של תיקיית יומן הסורקים

מורכבות זמן

עַל): אנו חוצים את מערך המיתרים הנתון באופן לינארי ועושים פעולת מחסנית בזמן O (1) בכל איטרציה. לפיכך, מורכבות הזמן היא O (n), כאשר n הוא אורך מערך הקלט.

מורכבות בחלל 

עַל): השתמשנו בערימה שגודלה יכול להיות שווה לאורך מערך הקלט הנתון. לפיכך, מורכבות החלל במקרה הגרוע ביותר היא O (n).

גישה 2 (באמצעות משתנה עומק)

ניתן לפתור את הבעיה בקלות על ידי המשך מעקב אחר משתנה עומק שמראה בעצם באיזה עומק אנו נמצאים בתיקיית השורש.
בכל פעם שאנחנו הולכים לתיקיית ילדים, אנחנו הולכים רחוק מתיקיית השורש לפי מרחק 1. (כלומר עומק ++)
בכל פעם שאנחנו הולכים לתיקיית אב, אנחנו הולכים ומתקרבים לתיקיית הבסיס לפי מרחק 1. (כלומר עומק–).
שים לב שנוכל לעבור לתיקיית האב רק אם איננו בתיקיית הבסיס.
אז נתחיל לבצע את הפקודות משמאל לימין ב- for לולאה .

  • אם ניתקל ב "../" נבדוק אם אנחנו בתיקיית שורש או לא. אם לא, אנו נפחית את העומק ב -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

תוכנית Java לפתרון תיקיית יומן הסורקים

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 של תיקיית יומן הסורקים

מורכבות זמן

עַל): אנו מבצעים את כל הפקודות פעם אחת. לפיכך, מורכבות הזמן היא O (n).

מורכבות בחלל 

O (1): הרגע השתמשנו במשתנה עומק. לפיכך, מורכבות החלל היא O (1).