โซลูชัน Leetcode โฟลเดอร์บันทึกของ Crawler


ระดับความยาก สะดวกสบาย
ถามบ่อยใน Mercari
กอง

คำชี้แจงปัญหา

ในปัญหานี้เรากำลังติดตามตำแหน่งของเราในระบบโฟลเดอร์ ตอนแรกเราอยู่ที่โฟลเดอร์รูทหรือโฟลเดอร์หลักของระบบนี้
โดยทั่วไปเรามีคำสั่ง 3 ประเภทที่นี่ คำสั่งอยู่ในรูปแบบของสตริงซึ่งแต่ละสตริงหมายถึงคำสั่ง

  •  “ ../” หมายถึงไปที่โฟลเดอร์หลักของโฟลเดอร์ปัจจุบัน (ถ้าอยู่ในโฟลเดอร์รากแล้วอย่าไปไหนเลย)
  •  “ ./” อยู่ในโฟลเดอร์ปัจจุบัน
  •  “ x /” เข้าไปในโฟลเดอร์ย่อยของโฟลเดอร์ปัจจุบันซึ่งมีชื่อ x

เราได้รับลำดับของคำสั่งซึ่งเป็นการรวมกันของ 3 คำสั่งข้างต้น เราต้องหาจำนวนขั้นต่ำของการดำเนินการเพื่อกลับไปที่โฟลเดอร์รูทหลังจากกำหนดรูปแบบคำสั่งที่กำหนดไว้ล่วงหน้า
เช่น
บันทึก = [“ d1 /”,” d2 /”,” ../”,” d21 /”, ”./”]

โซลูชัน Leetcode โฟลเดอร์บันทึกของ Crawler
เราอยู่ที่ระดับความลึก 2 จากโฟลเดอร์รูท ดังนั้นคำตอบของเราจะเป็น 2

ตัวอย่าง

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

คำอธิบาย:

ใช้การดำเนินการเปลี่ยนโฟลเดอร์“ ../” 2 ครั้งแล้วกลับไปที่โฟลเดอร์หลัก

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

แนวทางที่ 1 (การใช้ Stack)

เราสามารถใช้ชื่อไฟล์ซ้อนกัน เริ่มแรกสแต็กของเราว่างเปล่า เมื่อใดก็ตามที่เราต้องย้ายไปยังโฟลเดอร์ย่อยชื่อของโฟลเดอร์ย่อยจะถูกผลักเข้าไปในสแต็ก ดังนั้นโฟลเดอร์ที่เรานำเสนอในปัจจุบันจะยังคงอยู่ด้านบนสุดของสแต็กเสมอ
ดังนั้นเมื่อใดก็ตามที่เราพบ“ ../” หมายความว่าเราต้องออกมาจากโฟลเดอร์ปัจจุบัน (เช่นย้ายไปยังโฟลเดอร์หลัก) จากนั้นเราจะตรวจสอบว่าโฟลเดอร์ปัจจุบันเป็นรูทหรือไม่ ถ้าไม่เราจะแสดงองค์ประกอบด้านบนจากสแต็ก
และแน่นอนว่าเมื่อใดก็ตามที่เราต้องเจอกับ“ ./” เราต้องไม่ทำอะไรเลย
เรากำลังจัดการทั้งสามกรณีนี้โดยใช้ if else if แลดเดอร์

สิ่งหนึ่งที่เราควรทราบที่นี่คือจำนวนองค์ประกอบที่มีอยู่ในสแต็กกำลังบอกว่าความลึกที่เราอยู่ในโฟลเดอร์รูทนั้นอยู่ที่ระดับใด
ดังนั้นเราจะส่งคืนขนาดของสแต็กในตอนท้ายคือความลึกจากโฟลเดอร์รูท

การใช้งานสำหรับโซลูชัน 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 (เช่นความลึก -)
โปรดทราบว่าเราสามารถย้ายไปยังโฟลเดอร์หลักได้ก็ต่อเมื่อเราไม่ได้อยู่ในโฟลเดอร์ราก
ดังนั้นเราจะเริ่มดำเนินการคำสั่งจากซ้ายไปขวาใน a 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 สำหรับ Crawler Log Folder Leetcode Solution

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)