返回主文件夾所需的最少操作數

    給定一個陣列的串 的常用3 []表示在文件系統上執行的文件夾的操作的變化(Unix風格)。最初,文件系統在主文件夾中打開。該任務是查找以下三種類型的最小操作數以返回到主文件夾:

    • “ ../”:移動到當前文件夾的父文件夾。(如果當前文件夾是主文件夾,則它將保留在同一文件夾中)。
    • “ ./”:保留在同一文件夾中。
    • “ F /”:移動到名為F的子文件夾。

    例子:

    
    
        輸入: arr[] = {“F1/”, “F2/”, “./”, “F3/”, “../”, “F31/”}
        輸出: 3
        說明:
        arr[0] = “F1/”。移到名為F1的子文件夾。因此,當前目錄的路徑為/ F1。
        arr [1] =“F2/”。移到名為F2的子文件夾。因此,當前目錄的路徑為/ F1 / F2
        arr [2] =“./”。保留在當前文件夾中。因此,當前目錄的路徑為/ F1 / F2
        arr [3] =“F3/”。移到名為F3的子文件夾。因此,當前目錄的路徑為/ F1 / F2 / F3
        arr [4] =“../”。移至F3的父文件夾。因此,當前目錄的路徑為/ F1 / F2
        arr [5] =“F31 /”。移到名為F31的子文件夾。因此,當前目錄的路徑為/ F1 / F2 / F31
        現在,需要執行三次“ ../”操作才能返回到主文件夾。
        因此,所需的輸出為3。
    
        輸入: arr [] = {“ F1 /”,“ ../”,“ ../”}
        輸出: 0
        說明:
        arr [0] =“F1/”。因此,當前目錄的路徑為/ F1。
        arr [1] =“../”。因此,當前目錄的路徑為/
        arr [2] =“../”。因此,當前目錄的路徑為/。
        由於目錄的當前路徑已在主文件夾中,因此不需要任何操作。因此,所需的輸出為0。
    

    方法:可以使用Stack解決該問題。請按照以下步驟解決問題:

    1. 初始化一個變量,例如cntOp,以存儲返回主文件夾所需的最少操作數。
    2. 創建一個堆棧,說st來存儲當前文件夾的路徑
    3. 遍歷數組並檢查以下條件:
      如果arr [i] ==“ ../”,則彈出堆棧的頂部元素。
      如果arr [i] ==“ F /”,則將arr [i]的值壓入堆棧頂部。
    4. 最後,打印留在堆棧中的元素計數。

    下面是上述方法的實現:

    // C++ program to implement 
    // the above approach 
    #include <bits/stdc++.h> 
    using namespace std; 
    
    // Function to find minimum number of 
    // operations to go back to main folder 
    int minOperations(vector<string>& arr, 
                                int N) 
    { 
        // Stores path of 
        // the current folder 
        stack<string> st; 
    
        for (int i = 0; i < N; i++) { 
    
            // If stack is not empty and 
            // the value of arr[i] is "../" 
            if (arr[i] == "../" && 
                        !st.empty()) { 
    
                // Pop top element of 
                // the stack             
                st.pop(); 
            } 
    
            // If the value of arr[i] 
            // is like "F/" 
            else if (arr[i] != "./") { 
    
                // Push arr[i] on top element 
                // of the stack             
                st.push(arr[i]); 
            } 
        } 
    
        // Return count of elements left 
        // into the stack 
        return st.size(); 
    } 
    
    // Driver Code 
    int main() 
    { 
        vector<string> arr 
            = { "F1/", "F2/", "./", 
            "F3/", "../", "F31/" }; 
        int N = arr.size(); 
        cout << minOperations(arr, N); 
    } 
    

    輸出:

    3

    時間複雜度: O(N)
    輔助空間: O(N)