Número mínimo de operaciones necesarias para volver a la carpeta principal

Dada una array de strings arr[] que representan las operaciones de carpeta modificadas (estilo Unix) realizadas en el sistema de archivos. Inicialmente, el sistema de archivos se abre en la carpeta principal. La tarea es encontrar el recuento mínimo de operaciones de los siguientes tres tipos para volver a la carpeta principal:

  • “../”: se mueve a la carpeta principal de la carpeta actual. (Si la carpeta actual es la carpeta principal, permanece en la misma carpeta).
  • “./”: Permanece en la misma carpeta.
  • “F/”: se mueve a la carpeta secundaria denominada F.

Ejemplos:

Entrada: arr[] = {“F1/”, “F2/”, “./”, “F3/”, “../”, “F31/”}
Salida: 3
Explicación: 
arr[0] = “F1 /”. Mover a la carpeta secundaria llamada F1. Por lo tanto, la ruta del directorio actual es /F1. 
array[1] = “F2/”. Se mueve a la carpeta del niño, llamada F2. Por lo tanto, la ruta del directorio actual es /F1/F2 
arr[2] = “./” . Permanece en la carpeta actual. Por lo tanto, la ruta del directorio actual es /F1/F2 
arr[3] = “F3/”. Se mueve a la carpeta del niño, llamada F3. Por lo tanto, la ruta del directorio actual es /F1/F2/F3 
arr[4] = “../”. Mover a la carpeta principal de F3. Por lo tanto, la ruta del directorio actual es /F1/F2 
Arr[5] “F31/” . Vaya a la carpeta del niño, llamada F31. Por lo tanto, la ruta del directorio actual es /F1/F2/F31 
Ahora, la operación “../” debe realizarse tres veces para volver a la carpeta principal. 
Por lo tanto, la salida requerida es 3.

Entrada: arr[] = {“F1/”, “../”, “../”}
Salida: 0
Explicación: 
arr[0] = “F1/”. Por lo tanto, la ruta del directorio actual es /F1. 
array[1] = “../”. Por lo tanto, la ruta del directorio actual es / 
arr[2] = “../”. Por lo tanto, la ruta del directorio actual es / 
Dado que la ruta actual del directorio ya está en la carpeta principal, no se requieren operaciones. Por lo tanto, la salida requerida es 0. 

 

Enfoque: El problema se puede resolver usando Stack . Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, diga cntOp para almacenar el recuento de operaciones mínimas requeridas para volver a la carpeta principal.
  • Cree una pila , diga st para almacenar la ruta de la carpeta actual
  • Atraviese la array y verifique las siguientes condiciones: 
    • Si arr[i] == “../” , extraiga el elemento superior de la pila.
    • Si arr[i] == “F/” , entonces inserte el valor de arr[i] en la parte superior de la pila.
  • Finalmente, imprima el conteo de elementos que quedan en la pila.

A continuación se muestra la implementación del enfoque anterior:

C++

// 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);
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to find minimum number of
// operations to go back to main folder
static int minOperations(String []arr, int N)
{
     
    // Stores path of
    // the current folder
    Stack<String> st = new Stack<>();
 
    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
public static void main(String args[])
{
    String []arr = { "F1/", "F2/", "./",
                     "F3/", "../", "F31/" };
                      
    int N = arr.length;
     
    System.out.print(minOperations(arr, N));
}
}
 
// This code is contributed by ipg2016107

Python3

# Python3 program to implement
# the above approach
 
# Function to find minimum number of
# operations to go back to main folder
def minOperations(arr, N):
     
    # Stores path of
    # the current folder
    st = []
 
    for i in range(N):
         
        # If stack is not empty and
        # the value of arr[i] is "../"
        if (arr[i] == "../" and len(st) != 0):
             
            # Pop top element of
            # the stack
            st.pop(-1)
 
        # If the value of arr[i]
        # is like "F/"
        elif (arr[i] != "./"):
             
            # Push arr[i] on top element
            # of the stack
            st.append(arr[i])
 
    # Return count of elements left
    # into the stack
    return len(st)
 
# Driver code
if __name__ == '__main__':
     
    # Given array
    arr = [ "F1/", "F2/", "./",
            "F3/", "../", "F31/" ]
 
    # Size of the array
    N = len(arr)
 
    # Function Call
    print(minOperations(arr, N))
 
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to find minimum
// number of operations to
// go back to main folder
static int minOperations(String []arr,
                         int N)
{   
  // Stores path of
  // the current folder
  Stack<String> st =
        new Stack<String>();
 
  for(int i = 0; i < N; i++)
  {
    // If stack is not empty
    // and the value of arr[i]
    // is "../"
    if (arr[i] == "../" &&
        st.Count != 0)
    {
      // 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.Count;
}
 
// Driver Code
public static void Main(String []args)
{
  String []arr = {"F1/", "F2/", "./",
                  "F3/", "../", "F31/"};
  int N = arr.Length;
  Console.Write(minOperations(arr, N));
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
//Javascript  program to implement
// the above approach
 
// Function to find minimum number of
// operations to go back to main folder
function minOperations(arr, N)
{
    // Stores path of
    // the current folder
    st = [];
 
    for (var i = 0; i < N; i++) {
       
        // If stack is not empty and
        // the value of arr[i] is "../"
        if (arr[i] == "../" && (st.length-1) !== 0) {
             
            // 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.length;
}
 
var arr = [ "F1/", "F2/", "./", "F3/", "../", "F31/" ];
var N = arr.length;
document.write( minOperations(arr, N));
 
// This code is contributed by SoumikMondal
</script>
Producción: 

3

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *