Dada una string ‘str’ de dígitos y un entero ‘n’, construya el número más bajo posible eliminando ‘n’ dígitos de la string y sin cambiar el orden de los dígitos de entrada.
Ejemplos:
Input: str = "4325043", n = 3 Output: "2043" Input: str = "765028321", n = 5 Output: "0221" Input: str = "121198", n = 2 Output: "1118"
La idea se basa en el hecho de que un carácter entre los primeros (n+1) caracteres debe estar allí en el número resultante. Así que elegimos el más pequeño de los primeros dígitos (n+1) y lo ponemos en el resultado, y recurrimos para los caracteres restantes. A continuación se muestra el algoritmo completo.
Initialize result as empty string res = "" buildLowestNumber(str, n, res) 1) If n == 0, then there is nothing to remove. Append the whole 'str' to 'res' and return 2) Let 'len' be length of 'str'. If 'len' is smaller or equal to n, then everything can be removed Append nothing to 'res' and return 3) Find the smallest character among first (n+1) characters of 'str'. Let the index of smallest character be minIndex. Append 'str[minIndex]' to 'res' and recur for substring after minIndex and for n = n-minIndex buildLowestNumber(str[minIndex+1..len-1], n-minIndex).
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; string removeKdigits(string num, int k) { int n = num.size(); stack<char> mystack; // Store the final string in stack for (char c : num) { while (!mystack.empty() && k > 0 && mystack.top() > c) { mystack.pop(); k -= 1; } if (!mystack.empty() || c != '0'){ mystack.push(c); } } // Now remove the largest values from the top of the // stack while (!mystack.empty() && k--) mystack.pop(); if (mystack.empty()) return "0"; // Now retrieve the number from stack into a string // (reusing num) while (!mystack.empty()) { num[n - 1] = mystack.top(); mystack.pop(); n -= 1; } return num.substr(n); } int main() { string str = "765028321"; int k = 5; cout << removeKdigits(str, k); return 0; }
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { public static String removeKdigits(String num, int k) { StringBuilder result = new StringBuilder(); // We have to delete all digits if (k >= num.length()) { return "0"; } // Nothing to delete if (k == 0) { return num; } Stack<Character> s = new Stack<Character>(); for (int i = 0; i < num.length(); i++) { char c = num.charAt(i); // Removing all digits in stack that are greater // than this digit(since they have higher // weightage) while (!s.isEmpty() && k > 0 && s.peek() > c) { s.pop(); k--; } // ignore pushing 0 if (!s.isEmpty() || c != '0') s.push(c); } // If our k isnt 0 yet then we keep popping out the // stack until k becomes 0 while (!s.isEmpty() && k > 0) { k--; s.pop(); } if (s.isEmpty()) return "0"; while (!s.isEmpty()) { result.append(s.pop()); } String str = result.reverse().toString(); return str; } // Driver Code public static void main(String[] args) { String s = "765028321"; int k = 5; System.out.println(removeKdigits(s, 5)); } } // this code is contributed by gireeshgudaparthi
Python3
# Python program for the above approach def removeKdigits(num, k): n = len(num) mystack = [] # Store the final string in stack for c in num: while (len(mystack) > 0 and k > 0 and ord(mystack[len(mystack)-1]) > ord(c)): mystack.pop() k -= 1 if len(mystack) > 0 or c != '0' : mystack.append(c) # Now remove the largest values from the top of the # stack while len(mystack) > 0 and k: mystack.pop() k -= 1 if len(mystack) == 0: return "0" # Now retrieve the number from stack into a string # (reusing num) while(len(mystack) > 0): num = num.replace(num[n - 1],mystack[len(mystack) - 1]) mystack.pop() n -= 1 return num[n:] # driver code str = "765028321" k = 5 print(removeKdigits(str, k)) # This code is contributed by shinjanpatra
C#
// C# program for the above approach using System; using System.Collections.Generic; using System.Collections; class HelloWorld { static string removeKdigits(string Num, int k) { char[] num = Num.ToCharArray(); int n = num.Length; Stack<char> mystack = new Stack<char>(); // Store the final string in stack for (int i = 0; i < num.Length; i++) { while (mystack.Count > 0 && k > 0 && mystack.Peek() > num[i]) { mystack.Pop(); k = k - 1; } if (mystack.Count > 0 || num[i] != '0') { mystack.Push(num[i]); } } // Now remove the largest values from the top of the // stack while (mystack.Count > 0 && k > 0) { mystack.Pop(); k = k - 1; } if (mystack.Count == 0) return "0"; // Now retrieve the number from stack into a string // (reusing num) while (mystack.Count > 0) { char temp = mystack.Peek(); num[n - 1] = temp; mystack.Pop(); n = n - 1; } return new string(num).Substring(n); } static void Main() { string str = "765028321"; int k = 5; Console.WriteLine(removeKdigits(str, k)); } } // The code is contributed by Nidhi goel
Javascript
<script> // JavaScript program for the above approach function removeKdigits(num,k) { let n = num.length; let mystack = []; // Store the final string in stack for (let c of num) { while (mystack.length>0 && k > 0 && mystack[mystack.length-1].charCodeAt(0) > c.charCodeAt(0)) { mystack.pop(); k -= 1; } if(mystack.length > 0 || c !== '0') { mystack.push(c); } } // Now remove the largest values from the top of the // stack while(mystack.length > 0 && k--) mystack.pop(); if (mystack.length == 0) return "0"; // Now retrieve the number from stack into a string // (reusing num) while(mystack.length > 0) { num = num.split(''); num[n - 1] = mystack[mystack.length - 1]; num = num.join(''); mystack.pop(); n -= 1; } return num.substr(n); } // Driver code let str = "765028321" let k = 5 document.write(removeKdigits(str, k)) // This code is contributed by shinjanpatra </script>
221
A continuación se muestra un código optimizado en C++ aportado por Gaurav Mamgain
C++14
// C++ program to build the smallest number by removing // n digits from a given number #include <bits/stdc++.h> using namespace std; void insertInNonDecOrder(deque<char>& dq, char ch) { // If container is empty , insert the current digit if (dq.empty()) dq.push_back(ch); else { char temp = dq.back(); // Keep removing digits larger than current digit // from the back side of deque while (temp > ch && !dq.empty()) { dq.pop_back(); if (!dq.empty()) temp = dq.back(); } // Insert the current digit dq.push_back(ch); } return; } string buildLowestNumber(string str, int n) { int len = str.length(); // Deleting n digits means we need to print k digits int k = len - n; deque<char> dq; string res = ""; // Leaving rightmost k-1 digits we need to choose // minimum digit from rest of the string and print it int i; for (i = 0; i <= len - k; i++) // Insert new digit from the back side in // appropriate position and/ keep removing // digits larger than current digit insertInNonDecOrder(dq, str[i]); // Now the minimum digit is at front of deque while (i < len) { // keep the minimum digit in output string res += dq.front(); // remove minimum digit dq.pop_front(); // Again insert new digit from the back // side in appropriate position and keep // removing digits larger than current digit insertInNonDecOrder(dq, str[i]); i++; } // Now only one element will be there in the deque res += dq.front(); dq.pop_front(); return res; } string lowestNumber(string str, int n) { string res = buildLowestNumber(str, n); // Remove all the leading zeroes string ans = ""; int flag = 0; for (int i = 0; i < res.length(); i++) { if (res[i] != '0' || flag == 1) { flag = 1; ans += res[i]; } } if (ans.length() == 0) return "0"; else return ans; } // Driver program to test above function int main() { string str = "765028321"; int n = 5; cout <<lowestNumber(str, n) << endl; return 0; } // This code is contributed by Gaurav Mamgain
221
Complejidad temporal: O(N)
Complejidad espacial: O(N)
Enfoque-2:
Supongamos que la longitud de la string num dada sea n, por lo que la string resultante contendrá la longitud de nk.
A medida que procedemos a resolver este problema, debemos asegurarnos de que la string de salida contenga valores mínimos en sus posiciones de peso alto. por lo que nos aseguramos de que mediante el uso de una pila.
- Devuelve 0 si k >=n. y devuelve num si k=0.
- Cree una pila e itere a través de la string numérica y empuje el valor en esa posición si es mayor que el elemento superior de la pila.
- Iterar a través de la string numérica y si el valor entero en esa posición es menor que la parte superior de la pila, abriremos la pila y disminuiremos k hasta llegar a la condición en la que la parte superior de la pila es menor que el valor que estamos viendo ( mientras que k>0) (con esto nos aseguramos de que las posiciones más significativas del resultado se llenen con valores mínimos).
- Si k sigue siendo mayor que 0, abriremos la pila hasta que k se convierta en 0.
- Agregue los elementos de la pila a la string de resultados.
- Elimine los ceros iniciales de la string de resultados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; string removeKdigits(string num, int k) { int n = num.size(); stack<char> mystack; // Store the final string in stack for (char c : num) { while (!mystack.empty() && k > 0 && mystack.top() > c) { mystack.pop(); k -= 1; } if (!mystack.empty() || c != '0') mystack.push(c); } // Now remove the largest values from the top of the // stack while (!mystack.empty() && k--) mystack.pop(); if (mystack.empty()) return "0"; // Now retrieve the number from stack into a string // (reusing num) while (!mystack.empty()) { num[n - 1] = mystack.top(); mystack.pop(); n -= 1; } return num.substr(n); } int main() { string str = "765028321"; int k = 5; cout << removeKdigits(str, k); return 0; }
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { public static String removeKdigits(String num, int k) { StringBuilder result = new StringBuilder(); // We have to delete all digits if (k >= num.length()) { return "0"; } // Nothing to delete if (k == 0) { return num; } Stack<Character> s = new Stack<Character>(); for (int i = 0; i < num.length(); i++) { char c = num.charAt(i); // Removing all digits in stack that are greater // than this digit(since they have higher // weightage) while (!s.isEmpty() && k > 0 && s.peek() > c) { s.pop(); k--; } // ignore pushing 0 if (!s.isEmpty() || c != '0') s.push(c); } // If our k isnt 0 yet then we keep popping out the // stack until k becomes 0 while (!s.isEmpty() && k > 0) { k--; s.pop(); } if (s.isEmpty()) return "0"; while (!s.isEmpty()) { result.append(s.pop()); } String str = result.reverse().toString(); return str; } // Driver Code public static void main(String[] args) { String s = "765028321"; int k = 5; System.out.println(removeKdigits(s, 5)); } } // this code is contributed by gireeshgudaparthi
Python3
# Python program for the above approach def removeKdigits(num, k): n = len(num) mystack = [] # Store the final string in stack for c in num: while (len(mystack) > 0 and k > 0 and mystack[-1] > c): mystack.pop() k -= 1 if (len(mystack) > 0 or c != '0'): mystack.append(c) # Now remove the largest values from the top of the # stack while (len(mystack) > 0 and k): k -= 1 mystack.pop() if (len(mystack) == 0): return "0" # Now retrieve the number from stack into a string # (reusing num) while (len(mystack) > 0): num = num.replace(num[n - 1] , mystack[-1]) mystack.pop() n -= 1 return num[n:] # driver code Str = "765028321" k = 5 print(removeKdigits(Str, k)) # This code is contributed by shinjanpatra
Javascript
<script> // JavaScript program for the above approach function removeKdigits(num,k){ let n = num.length let mystack = [] // Store the final string in stack for(let c of num){ while (mystack.length>0 && k > 0 && mystack[mystack.length - 1] > c){ mystack.pop() k -= 1 } if (mystack.length>0 || c != '0') mystack.push(c) } // Now remove the largest values from the top of the // stack while (mystack.length>0 && k){ k -= 1 mystack.pop() } if (mystack.length == 0) return "0" // Now retrieve the number from stack into a string // (reusing num) while (mystack.length>0){ num = num.replace(num[n - 1] , mystack[mystack.length-1]) mystack.pop() n -= 1 } return num.substring(n,) } // driver code let Str = "765028321" let k = 5 document.write(removeKdigits(Str, k)) // code is contributed by shinjanpatra </script>
221
Complejidad temporal: O(N)
Complejidad espacial: O(N)
Este artículo es una contribución de Pallav Gurha . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA