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>
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