Dado un patrón que contiene solo I y D. I para aumentar y D para disminuir. Dispositivo un algoritmo para imprimir el número mínimo siguiendo ese patrón. Los dígitos del 1 al 9 y los dígitos no se pueden repetir.
Ejemplos:
Input: D Output: 21 Input: I Output: 12 Input: DD Output: 321 Input: II Output: 123 Input: DIDI Output: 21435 Input: IIDDD Output: 126543 Input: DDIDDIID Output: 321654798
Fuente: pregunta de la entrevista de Amazon
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
A continuación se presentan algunas observaciones importantes
Dado que los dígitos no se pueden repetir, puede haber como máximo 9 dígitos en la salida.
Además, el número de dígitos en la salida es uno más que el número de caracteres en la entrada. Tenga en cuenta que el primer carácter de entrada corresponde a dos dígitos en la salida.
La idea es iterar sobre la array de entrada y realizar un seguimiento del último dígito impreso y el dígito máximo impreso hasta el momento. A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to print minimum number that can be formed
// from a given sequence of Is and Ds
#include <bits/stdc++.h>
using namespace std;
// Prints the minimum number that can be formed from
// input sequence of I's and D's
void PrintMinNumberForPattern(string arr)
{
// Initialize current_max (to make sure that
// we don't use repeated character
int curr_max = 0;
// Initialize last_entry (Keeps track for
// last printed digit)
int last_entry = 0;
int j;
// Iterate over input array
for (int i=0; i<arr.length(); i++)
{
// Initialize 'noOfNextD' to get count of
// next D's available
int noOfNextD = 0;
switch(arr[i])
{
case 'I':
// If letter is 'I'
// Calculate number of next consecutive D's
// available
j = i+1;
while (arr[j] == 'D' && j < arr.length())
{
noOfNextD++;
j++;
}
if (i==0)
{
curr_max = noOfNextD + 2;
// If 'I' is first letter, print incremented
// sequence from 1
cout << " " << ++last_entry;
cout << " " << curr_max;
// Set max digit reached
last_entry = curr_max;
}
else
{
// If not first letter
// Get next digit to print
curr_max = curr_max + noOfNextD + 1;
// Print digit for I
last_entry = curr_max;
cout << " " << last_entry;
}
// For all next consecutive 'D' print
// decremented sequence
for (int k=0; k<noOfNextD; k++)
{
cout << " " << --last_entry;
i++;
}
break;
// If letter is 'D'
case 'D':
if (i == 0)
{
// If 'D' is first letter in sequence
// Find number of Next D's available
j = i+1;
while (arr[j] == 'D' && j < arr.length())
{
noOfNextD++;
j++;
}
// Calculate first digit to print based on
// number of consecutive D's
curr_max = noOfNextD + 2;
// Print twice for the first time
cout << " " << curr_max << " " << curr_max - 1;
// Store last entry
last_entry = curr_max - 1;
}
else
{
// If current 'D' is not first letter
// Decrement last_entry
cout << " " << last_entry - 1;
last_entry--;
}
break;
}
}
cout << endl;
}
// Driver program to test above
int main()
{
PrintMinNumberForPattern("IDID");
PrintMinNumberForPattern("I");
PrintMinNumberForPattern("DD");
PrintMinNumberForPattern("II");
PrintMinNumberForPattern("DIDI");
PrintMinNumberForPattern("IIDDD");
PrintMinNumberForPattern("DDIDDIID");
return 0;
}
Java
// Java program to print minimum number that can be formed
// from a given sequence of Is and Ds
class GFG
{
// Prints the minimum number that can be formed from
// input sequence of I's and D's
static void PrintMinNumberForPattern(String arr)
{
// Initialize current_max (to make sure that
// we don't use repeated character
int curr_max = 0;
// Initialize last_entry (Keeps track for
// last printed digit)
int last_entry = 0;
int j;
// Iterate over input array
for (int i = 0; i < arr.length(); i++)
{
// Initialize 'noOfNextD' to get count of
// next D's available
int noOfNextD = 0;
switch (arr.charAt(i))
{
case 'I':
// If letter is 'I'
// Calculate number of next consecutive D's
// available
j = i + 1;
while (j < arr.length() && arr.charAt(j) == 'D')
{
noOfNextD++;
j++;
}
if (i == 0)
{
curr_max = noOfNextD + 2;
// If 'I' is first letter, print incremented
// sequence from 1
System.out.print(" " + ++last_entry);
System.out.print(" " + curr_max);
// Set max digit reached
last_entry = curr_max;
}
else
{
// If not first letter
// Get next digit to print
curr_max = curr_max + noOfNextD + 1;
// Print digit for I
last_entry = curr_max;
System.out.print(" " + last_entry);
}
// For all next consecutive 'D' print
// decremented sequence
for (int k = 0; k < noOfNextD; k++)
{
System.out.print(" " + --last_entry);
i++;
}
break;
// If letter is 'D'
case 'D':
if (i == 0)
{
// If 'D' is first letter in sequence
// Find number of Next D's available
j = i + 1;
while (j < arr.length()&&arr.charAt(j) == 'D')
{
noOfNextD++;
j++;
}
// Calculate first digit to print based on
// number of consecutive D's
curr_max = noOfNextD + 2;
// Print twice for the first time
System.out.print(" " + curr_max + " " + (curr_max - 1));
// Store last entry
last_entry = curr_max - 1;
}
else
{
// If current 'D' is not first letter
// Decrement last_entry
System.out.print(" " + (last_entry - 1));
last_entry--;
}
break;
}
}
System.out.println();
}
// Driver code
public static void main(String[] args)
{
PrintMinNumberForPattern("IDID");
PrintMinNumberForPattern("I");
PrintMinNumberForPattern("DD");
PrintMinNumberForPattern("II");
PrintMinNumberForPattern("DIDI");
PrintMinNumberForPattern("IIDDD");
PrintMinNumberForPattern("DDIDDIID");
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to print minimum number that
# can be formed from a given sequence of Is and Ds
# Prints the minimum number that can be formed from
# input sequence of I's and D's
def PrintMinNumberForPattern(arr):
# Initialize current_max (to make sure that
# we don't use repeated character
curr_max = 0
# Initialize last_entry (Keeps track for
# last printed digit)
last_entry = 0
i = 0
# Iterate over input array
while i < len(arr):
# Initialize 'noOfNextD' to get count of
# next D's available
noOfNextD = 0
if arr[i] == "I":
# If letter is 'I'
# Calculate number of next consecutive D's
# available
j = i + 1
while j < len(arr) and arr[j] == "D":
noOfNextD += 1
j += 1
if i == 0:
curr_max = noOfNextD + 2
last_entry += 1
# If 'I' is first letter, print incremented
# sequence from 1
print("", last_entry, end = "")
print("", curr_max, end = "")
# Set max digit reached
last_entry = curr_max
else:
# If not first letter
# Get next digit to print
curr_max += noOfNextD + 1
# Print digit for I
last_entry = curr_max
print("", last_entry, end = "")
# For all next consecutive 'D' print
# decremented sequence
for k in range(noOfNextD):
last_entry -= 1
print("", last_entry, end = "")
i += 1
# If letter is 'D'
elif arr[i] == "D":
if i == 0:
# If 'D' is first letter in sequence
# Find number of Next D's available
j = i + 1
while j < len(arr) and arr[j] == "D":
noOfNextD += 1
j += 1
# Calculate first digit to print based on
# number of consecutive D's
curr_max = noOfNextD + 2
# Print twice for the first time
print("", curr_max, curr_max - 1, end = "")
# Store last entry
last_entry = curr_max - 1
else:
# If current 'D' is not first letter
# Decrement last_entry
print("", last_entry - 1, end = "")
last_entry -= 1
i += 1
print()
# Driver code
if __name__ == "__main__":
PrintMinNumberForPattern("IDID")
PrintMinNumberForPattern("I")
PrintMinNumberForPattern("DD")
PrintMinNumberForPattern("II")
PrintMinNumberForPattern("DIDI")
PrintMinNumberForPattern("IIDDD")
PrintMinNumberForPattern("DDIDDIID")
# This code is contributed by
# sanjeev2552
C#
// C# program to print minimum number that can be formed
// from a given sequence of Is and Ds
using System;
class GFG
{
// Prints the minimum number that can be formed from
// input sequence of I's and D's
static void PrintMinNumberForPattern(String arr)
{
// Initialize current_max (to make sure that
// we don't use repeated character
int curr_max = 0;
// Initialize last_entry (Keeps track for
// last printed digit)
int last_entry = 0;
int j;
// Iterate over input array
for (int i = 0; i < arr.Length; i++)
{
// Initialize 'noOfNextD' to get count of
// next D's available
int noOfNextD = 0;
switch (arr[i])
{
case 'I':
// If letter is 'I'
// Calculate number of next consecutive D's
// available
j = i + 1;
while (j < arr.Length && arr[j] == 'D')
{
noOfNextD++;
j++;
}
if (i == 0)
{
curr_max = noOfNextD + 2;
// If 'I' is first letter, print incremented
// sequence from 1
Console.Write(" " + ++last_entry);
Console.Write(" " + curr_max);
// Set max digit reached
last_entry = curr_max;
}
else
{
// If not first letter
// Get next digit to print
curr_max = curr_max + noOfNextD + 1;
// Print digit for I
last_entry = curr_max;
Console.Write(" " + last_entry);
}
// For all next consecutive 'D' print
// decremented sequence
for (int k = 0; k < noOfNextD; k++)
{
Console.Write(" " + --last_entry);
i++;
}
break;
// If letter is 'D'
case 'D':
if (i == 0)
{
// If 'D' is first letter in sequence
// Find number of Next D's available
j = i + 1;
while (j < arr.Length&&arr[j] == 'D')
{
noOfNextD++;
j++;
}
// Calculate first digit to print based on
// number of consecutive D's
curr_max = noOfNextD + 2;
// Print twice for the first time
Console.Write(" " + curr_max + " " + (curr_max - 1));
// Store last entry
last_entry = curr_max - 1;
}
else
{
// If current 'D' is not first letter
// Decrement last_entry
Console.Write(" " + (last_entry - 1));
last_entry--;
}
break;
}
}
Console.WriteLine();
}
// Driver code
public static void Main(String[] args)
{
PrintMinNumberForPattern("IDID");
PrintMinNumberForPattern("I");
PrintMinNumberForPattern("DD");
PrintMinNumberForPattern("II");
PrintMinNumberForPattern("DIDI");
PrintMinNumberForPattern("IIDDD");
PrintMinNumberForPattern("DDIDDIID");
}
}
// This code is contributed by Princi Singh
PHP
<?php
// PHP program to print minimum
// number that can be formed
// from a given sequence of
// Is and Ds
// Prints the minimum number
// that can be formed from
// input sequence of I's and D's
function PrintMinNumberForPattern($arr)
{
// Initialize current_max
// (to make sure that
// we don't use repeated
// character
$curr_max = 0;
// Initialize last_entry
// (Keeps track for
// last printed digit)
$last_entry = 0;
$j;
// Iterate over
// input array
for ($i = 0; $i < strlen($arr); $i++)
{
// Initialize 'noOfNextD'
// to get count of
// next D's available
$noOfNextD = 0;
switch($arr[$i])
{
case 'I':
// If letter is 'I'
// Calculate number of
// next consecutive D's
// available
$j = $i + 1;
while ($arr[$j] == 'D' &&
$j < strlen($arr))
{
$noOfNextD++;
$j++;
}
if ($i == 0)
{
$curr_max = $noOfNextD + 2;
// If 'I' is first letter,
// print incremented
// sequence from 1
echo " " , ++$last_entry;
echo " " , $curr_max;
// Set max
// digit reached
$last_entry = $curr_max;
}
else
{
// If not first letter
// Get next digit
// to print
$curr_max = $curr_max +
$noOfNextD + 1;
// Print digit for I
$last_entry = $curr_max;
echo " " , $last_entry;
}
// For all next consecutive 'D'
// print decremented sequence
for ($k = 0; $k < $noOfNextD; $k++)
{
echo " " , --$last_entry;
$i++;
}
break;
// If letter is 'D'
case 'D':
if ($i == 0)
{
// If 'D' is first letter
// in sequence. Find number
// of Next D's available
$j = $i+1;
while (($arr[$j] == 'D') &&
($j < strlen($arr)))
{
$noOfNextD++;
$j++;
}
// Calculate first digit
// to print based on
// number of consecutive D's
$curr_max = $noOfNextD + 2;
// Print twice for
// the first time
echo " " , $curr_max ,
" " ,$curr_max - 1;
// Store last entry
$last_entry = $curr_max - 1;
}
else
{
// If current 'D'
// is not first letter
// Decrement last_entry
echo " " , $last_entry - 1;
$last_entry--;
}
break;
}
}
echo "\n";
}
// Driver Code
PrintMinNumberForPattern("IDID");
PrintMinNumberForPattern("I");
PrintMinNumberForPattern("DD");
PrintMinNumberForPattern("II");
PrintMinNumberForPattern("DIDI");
PrintMinNumberForPattern("IIDDD");
PrintMinNumberForPattern("DDIDDIID");
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to print minimum number that can be formed
// from a given sequence of Is and Ds
// Prints the minimum number that can be formed from
// input sequence of I's and D's
function PrintMinNumberForPattern(arr)
{
// Initialize current_max (to make sure that
// we don't use repeated character
let curr_max = 0;
// Initialize last_entry (Keeps track for
// last printed digit)
let last_entry = 0;
let j;
// Iterate over input array
for (let i = 0; i < arr.length; i++)
{
// Initialize 'noOfNextD' to get count of
// next D's available
let noOfNextD = 0;
switch (arr[i])
{
case 'I':
// If letter is 'I'
// Calculate number of next consecutive D's
// available
j = i + 1;
while (j < arr.length && arr[j] == 'D')
{
noOfNextD++;
j++;
}
if (i == 0)
{
curr_max = noOfNextD + 2;
// If 'I' is first letter, print incremented
// sequence from 1
document.write(" " + ++last_entry);
document.write(" " + curr_max);
// Set max digit reached
last_entry = curr_max;
}
else
{
// If not first letter
// Get next digit to print
curr_max = curr_max + noOfNextD + 1;
// Print digit for I
last_entry = curr_max;
document.write(" " + last_entry);
}
// For all next consecutive 'D' print
// decremented sequence
for (let k = 0; k < noOfNextD; k++)
{
document.write(" " + --last_entry);
i++;
}
break;
// If letter is 'D'
case 'D':
if (i == 0)
{
// If 'D' is first letter in sequence
// Find number of Next D's available
j = i + 1;
while (j < arr.length && arr[j] == 'D')
{
noOfNextD++;
j++;
}
// Calculate first digit to print based on
// number of consecutive D's
curr_max = noOfNextD + 2;
// Print twice for the first time
document.write(" " + curr_max + " " + (curr_max - 1));
// Store last entry
last_entry = curr_max - 1;
}
else
{
// If current 'D' is not first letter
// Decrement last_entry
document.write(" " + (last_entry - 1));
last_entry--;
}
break;
}
}
document.write("<br>");
}
// Driver code
PrintMinNumberForPattern("IDID");
PrintMinNumberForPattern("I");
PrintMinNumberForPattern("DD");
PrintMinNumberForPattern("II");
PrintMinNumberForPattern("DIDI");
PrintMinNumberForPattern("IIDDD");
PrintMinNumberForPattern("DDIDDIID");
// This code is contributed by ab2127
</script>
Producción
1 3 2 5 4 1 2 3 2 1 1 2 3 2 1 4 3 5 1 2 6 5 4 3 3 2 1 6 5 4 7 9 8
Esta solución es sugerida por Swapnil Trambake.
Solución alternativa:
observemos algunos hechos en caso de número mínimo:
- Los dígitos no se pueden repetir, por lo que puede haber 9 dígitos como máximo en la salida.
- Para formar un número mínimo, en cada índice de la salida, estamos interesados en el número mínimo que se puede colocar en ese índice.
La idea es iterar sobre toda la array de entrada, haciendo un seguimiento del número mínimo (1-9) que se puede colocar en esa posición de la salida.
La parte complicada, por supuesto, ocurre cuando ‘D’ se encuentra en un índice distinto de 0. En tal caso, tenemos que rastrear la ‘I’ más cercana a la izquierda de ‘D’ e incrementar cada número en el vector de salida en 1 en el medio ‘I’ y ‘D’.
Cubrimos el caso base de la siguiente manera:
- Si el primer carácter de entrada es ‘I’, agregamos 1 y 2 en el vector de salida y el número mínimo disponible se establece en 3. El índice de la ‘I’ más reciente se establece en 1.
- Si el primer carácter de entrada es ‘D’, agregamos 2 y 1 en el vector de salida y el número mínimo disponible se establece en 3, y el índice de la ‘I’ más reciente se establece en 0.
Ahora iteramos la string de entrada desde el índice 1 hasta su final y:
- Si el carácter escaneado es ‘I’, se agrega un valor mínimo que aún no se ha utilizado al vector de salida. Incrementamos el valor del número mínimo. disponible y el índice de la ‘I’ más reciente también se actualiza.
- Si el carácter escaneado es ‘D’ en el índice i de la array de entrada, agregamos el i-ésimo elemento del vector de salida en la salida y rastreamos la ‘I’ más cercana a la izquierda de ‘D’ e incrementamos cada número en el vector de salida en 1 entre ‘I’ y ‘D’.
El siguiente es el programa para el mismo:
C++
// C++ program to print minimum number that can be formed
// from a given sequence of Is and Ds
#include<bits/stdc++.h>
using namespace std;
void printLeast(string arr)
{
// min_avail represents the minimum number which is
// still available for inserting in the output vector.
// pos_of_I keeps track of the most recent index
// where 'I' was encountered w.r.t the output vector
int min_avail = 1, pos_of_I = 0;
//vector to store the output
vector<int>v;
// cover the base cases
if (arr[0]=='I')
{
v.push_back(1);
v.push_back(2);
min_avail = 3;
pos_of_I = 1;
}
else
{
v.push_back(2);
v.push_back(1);
min_avail = 3;
pos_of_I = 0;
}
// Traverse rest of the input
for (int i=1; i<arr.length(); i++)
{
if (arr[i]=='I')
{
v.push_back(min_avail);
min_avail++;
pos_of_I = i+1;
}
else
{
v.push_back(v[i]);
for (int j=pos_of_I; j<=i; j++)
v[j]++;
min_avail++;
}
}
// print the number
for (int i=0; i<v.size(); i++)
cout << v[i] << " ";
cout << endl;
}
// Driver program to check the above function
int main()
{
printLeast("IDID");
printLeast("I");
printLeast("DD");
printLeast("II");
printLeast("DIDI");
printLeast("IIDDD");
printLeast("DDIDDIID");
return 0;
}
Java
// Java program to print minimum number that can be formed
// from a given sequence of Is and Ds
import java.io.*;
import java.util.*;
public class GFG {
static void printLeast(String arr)
{
// min_avail represents the minimum number which is
// still available for inserting in the output vector.
// pos_of_I keeps track of the most recent index
// where 'I' was encountered w.r.t the output vector
int min_avail = 1, pos_of_I = 0;
//vector to store the output
ArrayList<Integer> al = new ArrayList<>();
// cover the base cases
if (arr.charAt(0) == 'I')
{
al.add(1);
al.add(2);
min_avail = 3;
pos_of_I = 1;
}
else
{
al.add(2);
al.add(1);
min_avail = 3;
pos_of_I = 0;
}
// Traverse rest of the input
for (int i = 1; i < arr.length(); i++)
{
if (arr.charAt(i) == 'I')
{
al.add(min_avail);
min_avail++;
pos_of_I = i + 1;
}
else
{
al.add(al.get(i));
for (int j = pos_of_I; j <= i; j++)
al.set(j, al.get(j) + 1);
min_avail++;
}
}
// print the number
for (int i = 0; i < al.size(); i++)
System.out.print(al.get(i) + " ");
System.out.println();
}
// Driver code
public static void main(String args[])
{
printLeast("IDID");
printLeast("I");
printLeast("DD");
printLeast("II");
printLeast("DIDI");
printLeast("IIDDD");
printLeast("DDIDDIID");
}
}
// This code is contributed by rachana soma
Python3
# Python3 program to print minimum number
# that can be formed from a given sequence
# of Is and Ds
def printLeast(arr):
# min_avail represents the minimum
# number which is still available
# for inserting in the output vector.
# pos_of_I keeps track of the most
# recent index where 'I' was
# encountered w.r.t the output vector
min_avail = 1
pos_of_I = 0
# Vector to store the output
v = []
# Cover the base cases
if (arr[0] == 'I'):
v.append(1)
v.append(2)
min_avail = 3
pos_of_I = 1
else:
v.append(2)
v.append(1)
min_avail = 3
pos_of_I = 0
# Traverse rest of the input
for i in range(1, len(arr)):
if (arr[i] == 'I'):
v.append(min_avail)
min_avail += 1
pos_of_I = i + 1
else:
v.append(v[i])
for j in range(pos_of_I, i + 1):
v[j] += 1
min_avail += 1
# Print the number
print(*v, sep = ' ')
# Driver code
printLeast("IDID")
printLeast("I")
printLeast("DD")
printLeast("II")
printLeast("DIDI")
printLeast("IIDDD")
printLeast("DDIDDIID")
# This code is contributed by avanitrachhadiya2155
C#
// C# program to print minimum number that can be formed
// from a given sequence of Is and Ds
using System;
using System.Collections.Generic;
class GFG
{
static void printLeast(String arr)
{
// min_avail represents the minimum number which is
// still available for inserting in the output vector.
// pos_of_I keeps track of the most recent index
// where 'I' was encountered w.r.t the output vector
int min_avail = 1, pos_of_I = 0;
//vector to store the output
List<int> al = new List<int>();
// cover the base cases
if (arr[0] == 'I')
{
al.Add(1);
al.Add(2);
min_avail = 3;
pos_of_I = 1;
}
else
{
al.Add(2);
al.Add(1);
min_avail = 3;
pos_of_I = 0;
}
// Traverse rest of the input
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] == 'I')
{
al.Add(min_avail);
min_avail++;
pos_of_I = i + 1;
}
else
{
al.Add(al[i]);
for (int j = pos_of_I; j <= i; j++)
al[j] = al[j] + 1;
min_avail++;
}
}
// print the number
for (int i = 0; i < al.Count; i++)
Console.Write(al[i] + " ");
Console.WriteLine();
}
// Driver code
public static void Main(String []args)
{
printLeast("IDID");
printLeast("I");
printLeast("DD");
printLeast("II");
printLeast("DIDI");
printLeast("IIDDD");
printLeast("DDIDDIID");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to print
// minimum number that can be formed
// from a given sequence of Is and Ds
function printLeast(arr)
{
// min_avail represents the
// minimum number which is
// still available for inserting
// in the output vector.
// pos_of_I keeps track of the
// most recent index
// where 'I' was encountered
// w.r.t the output vector
let min_avail = 1, pos_of_I = 0;
//vector to store the output
let al = [];
// cover the base cases
if (arr[0] == 'I')
{
al.push(1);
al.push(2);
min_avail = 3;
pos_of_I = 1;
}
else
{
al.push(2);
al.push(1);
min_avail = 3;
pos_of_I = 0;
}
// Traverse rest of the input
for (let i = 1; i < arr.length; i++)
{
if (arr[i] == 'I')
{
al.push(min_avail);
min_avail++;
pos_of_I = i + 1;
}
else
{
al.push(al[i]);
for (let j = pos_of_I; j <= i; j++)
al[j] = al[j] + 1;
min_avail++;
}
}
// print the number
for (let i = 0; i < al.length; i++)
document.write(al[i] + " ");
document.write("</br>");
}
printLeast("IDID");
printLeast("I");
printLeast("DD");
printLeast("II");
printLeast("DIDI");
printLeast("IIDDD");
printLeast("DDIDDIID");
</script>
Producción
1 3 2 5 4 1 2 3 2 1 1 2 3 2 1 4 3 5 1 2 6 5 4 3 3 2 1 6 5 4 7 9 8
Esta solución es sugerida por Ashutosh Kumar .
Método 3
Podemos que cuando encontramos I, tenemos números en orden creciente pero si encontramos ‘D’, queremos tener números en orden decreciente. La longitud de la string de salida siempre es uno más que la string de entrada. Entonces el ciclo es desde 0 hasta la longitud de la string. Tenemos que tomar números del 1 al 9, por lo que siempre empujamos (i+1) a nuestra pila. Luego verificamos cuál es el carácter resultante en el índice especificado. Por lo tanto, habrá dos casos que son los siguientes:
Caso 1: si hemos encontrado I o estamos en el último carácter de la string de entrada, salte de la pila y agréguelo al final de la string de salida hasta que la pila se vacíe.
Caso 2: Si hemos encontrado D, entonces queremos los números en orden decreciente. entonces simplemente empujamos (i+1) a nuestra pila.
C++
// C++ program to print minimum number that can be formed
// from a given sequence of Is and Ds
#include <bits/stdc++.h>
using namespace std;
// Function to decode the given sequence to construct
// minimum number without repeated digits
void PrintMinNumberForPattern(string seq)
{
// result store output string
string result;
// create an empty stack of integers
stack<int> stk;
// run n+1 times where n is length of input sequence
for (int i = 0; i <= seq.length(); i++)
{
// push number i+1 into the stack
stk.push(i + 1);
// if all characters of the input sequence are
// processed or current character is 'I'
// (increasing)
if (i == seq.length() || seq[i] == 'I')
{
// run till stack is empty
while (!stk.empty())
{
// remove top element from the stack and
// add it to solution
result += to_string(stk.top());
result += " ";
stk.pop();
}
}
}
cout << result << endl;
}
// main function
int main()
{
PrintMinNumberForPattern("IDID");
PrintMinNumberForPattern("I");
PrintMinNumberForPattern("DD");
PrintMinNumberForPattern("II");
PrintMinNumberForPattern("DIDI");
PrintMinNumberForPattern("IIDDD");
PrintMinNumberForPattern("DDIDDIID");
return 0;
}
Java
import java.util.Stack;
// Java program to print minimum number that can be formed
// from a given sequence of Is and Ds
class GFG {
// Function to decode the given sequence to construct
// minimum number without repeated digits
static void PrintMinNumberForPattern(String seq) {
// result store output string
String result = "";
// create an empty stack of integers
Stack<Integer> stk = new Stack<Integer>();
// run n+1 times where n is length of input sequence
for (int i = 0; i <= seq.length(); i++) {
// push number i+1 into the stack
stk.push(i + 1);
// if all characters of the input sequence are
// processed or current character is 'I'
// (increasing)
if (i == seq.length() || seq.charAt(i) == 'I') {
// run till stack is empty
while (!stk.empty()) {
// remove top element from the stack and
// add it to solution
result += String.valueOf(stk.peek());
result += " ";
stk.pop();
}
}
}
System.out.println(result);
}
// main function
public static void main(String[] args) {
PrintMinNumberForPattern("IDID");
PrintMinNumberForPattern("I");
PrintMinNumberForPattern("DD");
PrintMinNumberForPattern("II");
PrintMinNumberForPattern("DIDI");
PrintMinNumberForPattern("IIDDD");
PrintMinNumberForPattern("DDIDDIID");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to print minimum
# number that can be formed from a
# given sequence of Is and Ds
def PrintMinNumberForPattern(Strr):
# Take a List to work as Stack
stack = []
# String for storing result
res = ''
# run n+1 times where n is length
# of input sequence, As length of
# result string is always 1 greater
for i in range(len(Strr) + 1):
# Push number i+1 into the stack
stack.append(i + 1)
# If all characters of the input
# sequence are processed or current
# character is 'I
if (i == len(Strr) or Strr[i] == 'I'):
# Run While Loop Until stack is empty
while len(stack) > 0:
# pop the element on top of stack
# And store it in result String
res += str(stack.pop())
res += ' '
# Print the result
print(res)
# Driver Code
PrintMinNumberForPattern("IDID")
PrintMinNumberForPattern("I")
PrintMinNumberForPattern("DD")
PrintMinNumberForPattern("II")
PrintMinNumberForPattern("DIDI")
PrintMinNumberForPattern("IIDDD")
PrintMinNumberForPattern("DDIDDIID")
# This code is contributed by AyushManglani
C#
// C# program to print minimum number that can be formed
// from a given sequence of Is and Ds
using System;
using System.Collections;
public class GFG {
// Function to decode the given sequence to construct
// minimum number without repeated digits
static void PrintMinNumberForPattern(String seq) {
// result store output string
String result = "";
// create an empty stack of integers
Stack stk = new Stack();
// run n+1 times where n is length of input sequence
for (int i = 0; i <= seq.Length; i++) {
// push number i+1 into the stack
stk.Push(i + 1);
// if all characters of the input sequence are
// processed or current character is 'I'
// (increasing)
if (i == seq.Length || seq[i] == 'I') {
// run till stack is empty
while (stk.Count!=0) {
// remove top element from the stack and
// add it to solution
result += String.Join("",stk.Peek());
result += " ";
stk.Pop();
}
}
}
Console.WriteLine(result);
}
// main function
public static void Main() {
PrintMinNumberForPattern("IDID");
PrintMinNumberForPattern("I");
PrintMinNumberForPattern("DD");
PrintMinNumberForPattern("II");
PrintMinNumberForPattern("DIDI");
PrintMinNumberForPattern("IIDDD");
PrintMinNumberForPattern("DDIDDIID");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to print
// minimum number that can be formed
// from a given sequence of Is and Ds
// Function to decode the given
// sequence to construct
// minimum number without repeated digits
function PrintMinNumberForPattern(seq)
{
// result store output string
let result = "";
// create an empty stack of integers
let stk = [];
// run n+1 times where n is length
// of input sequence
for (let i = 0; i <= seq.length; i++)
{
// push number i+1 into the stack
stk.push(i + 1);
// if all characters of the input
// sequence are
// processed or current character is 'I'
// (increasing)
if (i == seq.length || seq[i] == 'I')
{
// run till stack is empty
while (stk.length!=0) {
// remove top element from
// the stack and
// add it to solution
result +=
(stk[stk.length - 1]).toString();
result += " ";
stk.pop();
}
}
}
document.write(result + "</br>");
}
PrintMinNumberForPattern("IDID");
PrintMinNumberForPattern("I");
PrintMinNumberForPattern("DD");
PrintMinNumberForPattern("II");
PrintMinNumberForPattern("DIDI");
PrintMinNumberForPattern("IIDDD");
PrintMinNumberForPattern("DDIDDIID");
</script>
Producción
1 3 2 5 4 1 2 3 2 1 1 2 3 2 1 4 3 5 1 2 6 5 4 3 3 2 1 6 5 4 7 9 8
Complejidad Temporal: O(n)
Espacio Auxiliar: O(n), ya que se ha tomado n espacio extra.
Este método es aportado por Roshni Agarwal .
Método 4 (usando dos punteros)
Observación
- Dado que tenemos que encontrar un número mínimo sin repetir dígitos, la longitud máxima de salida puede ser 9 (usando cada 1-9 dígitos una vez)
- La longitud de la salida será exactamente uno mayor que la longitud de entrada.
- La idea es iterar sobre la string y hacer lo siguiente si el carácter actual es ‘I’ o la string finaliza.
- Asigne la cuenta en orden creciente a cada elemento desde el actual-1 hasta el siguiente índice izquierdo de ‘I’ (o se alcanza el índice inicial).
- Aumente el conteo en 1.
Input : IDID Output : 13254 Input : I Output : 12 Input : DD Output : 321 Input : II Output : 123 Input : DIDI Output : 21435 Input : IIDDD Output : 126543 Input : DDIDDIID Output : 321654798
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of above approach
#include <bits/stdc++.h>
using namespace std;
// Returns minimum number made from given sequence without repeating digits
string getMinNumberForPattern(string seq)
{
int n = seq.length();
if (n >= 9)
return "-1";
string result(n+1, ' ');
int count = 1;
// The loop runs for each input character as well as
// one additional time for assigning rank to remaining characters
for (int i = 0; i <= n; i++)
{
if (i == n || seq[i] == 'I')
{
for (int j = i - 1 ; j >= -1 ; j--)
{
result[j + 1] = '0' + count++;
if(j >= 0 && seq[j] == 'I')
break;
}
}
}
return result;
}
// main function
int main()
{
string inputs[] = {"IDID", "I", "DD", "II", "DIDI", "IIDDD", "DDIDDIID"};
for (string input : inputs)
{
cout << getMinNumberForPattern(input) << "\n";
}
return 0;
}
Java
// Java program of above approach
import java.io.IOException;
public class Test
{
// Returns minimum number made from given sequence without repeating digits
static String getMinNumberForPattern(String seq)
{
int n = seq.length();
if (n >= 9)
return "-1";
char result[] = new char[n + 1];
int count = 1;
// The loop runs for each input character as well as
// one additional time for assigning rank to each remaining characters
for (int i = 0; i <= n; i++)
{
if (i == n || seq.charAt(i) == 'I')
{
for (int j = i - 1; j >= -1; j--)
{
result[j + 1] = (char) ((int) '0' + count++);
if (j >= 0 && seq.charAt(j) == 'I')
break;
}
}
}
return new String(result);
}
public static void main(String[] args) throws IOException
{
String inputs[] = { "IDID", "I", "DD", "II", "DIDI", "IIDDD", "DDIDDIID" };
for(String input : inputs)
{
System.out.println(getMinNumberForPattern(input));
}
}
}
Python3
# Python3 program of above approach
# Returns minimum number made from
# given sequence without repeating digits
def getMinNumberForPattern(seq):
n = len(seq)
if (n >= 9):
return "-1"
result = [None] * (n + 1)
count = 1
# The loop runs for each input character
# as well as one additional time for
# assigning rank to remaining characters
for i in range(n + 1):
if (i == n or seq[i] == 'I'):
for j in range(i - 1, -2, -1):
result[j + 1] = int('0' + str(count))
count += 1
if(j >= 0 and seq[j] == 'I'):
break
return result
# Driver Code
if __name__ == '__main__':
inputs = ["IDID", "I", "DD", "II",
"DIDI", "IIDDD", "DDIDDIID"]
for Input in inputs:
print(*(getMinNumberForPattern(Input)))
# This code is contributed by PranchalK
C#
// C# program of above approach
using System;
class GFG
{
// Returns minimum number made from given
// sequence without repeating digits
static String getMinNumberForPattern(String seq)
{
int n = seq.Length;
if (n >= 9)
return "-1";
char []result = new char[n + 1];
int count = 1;
// The loop runs for each input character
// as well as one additional time for
// assigning rank to each remaining characters
for (int i = 0; i <= n; i++)
{
if (i == n || seq[i] == 'I')
{
for (int j = i - 1; j >= -1; j--)
{
result[j + 1] = (char) ((int) '0' + count++);
if (j >= 0 && seq[j] == 'I')
break;
}
}
}
return new String(result);
}
// Driver Code
public static void Main()
{
String []inputs = { "IDID", "I", "DD", "II",
"DIDI", "IIDDD", "DDIDDIID" };
foreach(String input in inputs)
{
Console.WriteLine(getMinNumberForPattern(input));
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program of above approach
// Returns minimum number made from given
// sequence without repeating digits
function getMinNumberForPattern(seq)
{
let n = seq.length;
if (n >= 9)
return "-1";
let result = new Array(n + 1);
let count = 1;
// The loop runs for each input character
// as well as one additional time for
// assigning rank to each remaining characters
for (let i = 0; i <= n; i++)
{
if (i == n || seq[i] == 'I')
{
for (let j = i - 1; j >= -1; j--)
{
result[j + 1] =
String.fromCharCode('0'.charCodeAt() +
count++);
if (j >= 0 && seq[j] == 'I')
break;
}
}
}
return result.join("");
}
let inputs = [ "IDID", "I", "DD", "II", "DIDI",
"IIDDD", "DDIDDIID" ];
for(let input = 0; input < inputs.length; input++)
{
document.write(
getMinNumberForPattern(inputs[input]) + "</br>"
);
}
</script>
Producción
13254 12 321 123 21435 126543 321654798
Complejidad de tiempo: O(N)
Espacio auxiliar: O(N) Brij Desai
sugiere esta solución . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Método 5 (Comience con el más pequeño)
Comience con el número más pequeño como respuesta y siga cambiando los dígitos cuando encontremos una D.
No hay necesidad de retroceder para el índice.
Siga los pasos a continuación,
- Comience con el número más pequeño para len(s)+1 (por ejemplo, para DI, comience con «123» )
- Ahora, comenzando con el segundo dígito (índice 1) y el primer carácter ( D ), itere hasta el final de la lista de dígitos, haciendo un seguimiento de la primera D en una secuencia de Ds
- Cuando encontramos una D
, mueva el dígito en el índice actual a la primera D en la secuencia - Cuando encontramos un
restablecimiento de la última ubicación conocida de D. No hay nada que mover ya que el dígito está colocado correctamente (a partir de ahora… )
- Cuando encontramos una D
A continuación se muestra la implementación del enfoque anterior:
C++
// c++ program to generate required sequence
#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
using namespace std;
//:param s: a seq consisting only of 'D' and 'I' chars. D is
//for decreasing and I for increasing :return: digits from
//1-9 that fit the str. The number they repr should the min
//such number
vector<string> didi_seq_gen(string s)
{
if (s.size() == 0)
return {};
vector<string> base_list = { "1" };
for (int i = 2; i < s.size() + 2; i++)
base_list.push_back(to_string(i));
int last_D = -1;
for (int i = 1; i < base_list.size(); i++) {
if (s[i - 1] == 'D') {
if (last_D < 0)
last_D = i - 1;
string v = base_list[i];
base_list.erase(base_list.begin() + i);
base_list.insert(base_list.begin() + last_D, v);
}
else
last_D = -1;
}
return base_list;
}
int main()
{
vector<string> inputs
= { "IDID", "I", "DD", "II",
"DIDI", "IIDDD", "DDIDDIID" };
for (auto x : inputs) {
vector<string> ans = didi_seq_gen(x);
for (auto i : ans) {
cout << i;
}
cout << endl;
}
return 0;
}
Java
// Java program to generate required sequence
import java.util.*;
public class Main {
public static void main(String[] args)
{
String[] inputs
= { "IDID", "I", "DD", "II",
"DIDI", "IIDDD", "DDIDDIID" };
for (String x : inputs) {
List<String> ans = didi_seq_gen(x);
for (String i : ans) {
System.out.print(i);
}
System.out.println();
}
}
//:param s: a seq consisting only of 'D' and 'I' chars.
//D is for decreasing and I for increasing :return:
// digits from 1-9 that fit the str. The number they repr
// should the min such number
public static List<String> didi_seq_gen(String s)
{
if (s.length() == 0)
return new ArrayList<>();
List<String> base_list
= new ArrayList<>(Arrays.asList("1"));
for (int i = 2; i < s.length() + 2; i++)
base_list.add(Integer.toString(i));
int last_D = -1;
for (int i = 1; i < base_list.size(); i++) {
if (s.charAt(i - 1) == 'D') {
if (last_D < 0)
last_D = i - 1;
String v = base_list.get(i);
base_list.remove(i);
base_list.add(last_D, v);
}
else {
last_D = -1;
}
}
return base_list;
}
}
// This code is contributed by Tapesh (tapeshdua420)
Python3
# Python implementation of the above approach
def didi_seq_gen(s: str):
'''
:param s: a seq consisting only of 'D'
and 'I' chars. D is for decreasing and
I for increasing
:return: digits from 1-9 that fit the str.
The number they repr should the min
such number
:rtype: str
example : for seq DII -> 2134
'''
if not s or len(s) <= 0:
return ""
base_list = ["1"]
for i in range(1, len(s) + 1):
base_list.append(f'{i + 1}')
last_D = -1
for i in range(1, len(base_list)):
if s[i - 1] == 'D':
if last_D < 0:
last_D = i - 1
v = base_list[i]
del base_list[i]
base_list.insert(last_D, v)
else:
last_D = -1
return base_list
# Driver Code
# Function call
print(didi_seq_gen("IDID"))
print(didi_seq_gen("I"))
print(didi_seq_gen("DD"))
print(didi_seq_gen("II"))
print(didi_seq_gen("DIDI"))
print(didi_seq_gen("IIDDD"))
print(didi_seq_gen("DDIDDIID" ))
Producción
13254 12 321 123 21435 126543 321654798
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Método 6: (espacio optimizado y código modular del Método 1)
Ejemplos:
Input: "DDDD"
Output: "432156"
For input 1, pattern is like, D -> D -> D -> D
5 4 3 2 1
Input: "DDDII"
Output: "432156"
For input 2, pattern is like, D -> D -> D -> I -> I
4 3 2 1 5 6
Input: "IIDIDIII"
Output: "124365789"
For input 3, pattern is like, I -> I -> D -> I -> D -> I -> I -> I
1 2 4 3 6 5 7 8 9
Acercarse:
- Piense si la string contiene solo caracteres ‘I’ que aumentan, entonces no hay ningún problema, simplemente puede imprimir y seguir incrementando.
- Ahora piense que si la string contiene solo los caracteres ‘D’ en aumento, entonces de alguna manera tiene que obtener el número de caracteres ‘D’ presentes desde el punto inicial, de modo que pueda comenzar desde el recuento total de ‘D’ e imprimir disminuyendo.
- El problema es cuando te encuentras con el carácter ‘D’ después del carácter ‘I’. Aquí, de alguna manera, debe obtener la cuenta de ‘D’ para obtener el siguiente inicio decreciente posible para ‘D’ y luego imprimir decrementando hasta que haya encontrado todo ‘D’.
- Aquí, en este enfoque, el código se ha hecho más modular en comparación con el método 1 de la versión optimizada para el espacio.
C++
// This code illustrates to find minimum number following
// pattern with optimized space and modular code.
#include <bits/stdc++.h>
using namespace std;
// This function returns minimum number following
// pattern of increasing or decreasing sequence.
string findMinNumberPattern(string str)
{
string ans = ""; // Minimum number following pattern
int i = 0;
int cur = 1; // cur val following pattern
int dCount = 0; // Count of char 'D'
while (i < str.length()) {
char ch = str[i];
// If 1st ch == 'I', incr and add to ans
if (i == 0 && ch == 'I') {
ans += to_string(cur);
cur++;
}
// If cur char == 'D',
// incr dCount as well, since we always
// start counting for dCount from i+1
if (ch == 'D') {
dCount++;
}
int j = i + 1; // Count 'D' from i+1 index
while (j < str.length()
&& str[j] == 'D') {
dCount++;
j++;
}
int k = dCount; // Store dCount
while (dCount >= 0) {
ans += to_string(cur + dCount);
dCount--;
}
cur += (k + 1); // Manages next cur val
dCount = 0;
i = j;
}
return ans;
}
int main()
{
cout << (findMinNumberPattern("DIDID")) << endl;
cout << (findMinNumberPattern("DIDIII")) << endl;
cout << (findMinNumberPattern("DDDIIDI")) << endl;
cout << (findMinNumberPattern("IDIDIID")) << endl;
cout << (findMinNumberPattern("DIIDIDD")) << endl;
cout << (findMinNumberPattern("IIDIDDD")) << endl;
return 0;
}
// This code is contributed by suresh07.
Java
/*package whatever //do not write package name here */
// This code illustrates to find minimum number following
// pattern with optimized space and modular code.
import java.io.*;
class GFG {
// This function returns minimum number following
// pattern of increasing or decreasing sequence.
public static String findMinNumberPattern(String str)
{
String ans = ""; // Minimum number following pattern
int i = 0;
int cur = 1; // cur val following pattern
int dCount = 0; // Count of char 'D'
while (i < str.length()) {
char ch = str.charAt(i);
// If 1st ch == 'I', incr and add to ans
if (i == 0 && ch == 'I') {
ans += cur;
cur++;
}
// If cur char == 'D',
// incr dCount as well, since we always
// start counting for dCount from i+1
if (ch == 'D') {
dCount++;
}
int j = i + 1; // Count 'D' from i+1 index
while (j < str.length()
&& str.charAt(j) == 'D') {
dCount++;
j++;
}
int k = dCount; // Store dCount
while (dCount >= 0) {
ans += (cur + dCount);
dCount--;
}
cur += (k + 1); // Manages next cur val
dCount = 0;
i = j;
}
return ans;
}
public static void main(String[] args)
{
System.out.println(findMinNumberPattern("DIDID"));
System.out.println(findMinNumberPattern("DIDIII"));
System.out.println(findMinNumberPattern("DDDIIDI"));
System.out.println(findMinNumberPattern("IDIDIID"));
System.out.println(findMinNumberPattern("DIIDIDD"));
System.out.println(findMinNumberPattern("IIDIDDD"));
}
}
// This code is contributed by Arun M
Python3
# This code illustrates to find minimum number following
# pattern with optimized space and modular code.
# This function returns minimum number following
# pattern of increasing or decreasing sequence.
def findMinNumberPattern(Str):
ans = "" # Minimum number following pattern
i = 0
cur = 1 # cur val following pattern
dCount = 0 # Count of char 'D'
while (i < len(Str)) :
ch = Str[i]
# If 1st ch == 'I', incr and add to ans
if (i == 0 and ch == 'I') :
ans += str(cur)
cur+=1
# If cur char == 'D',
# incr dCount as well, since we always
# start counting for dCount from i+1
if (ch == 'D') :
dCount+=1
j = i + 1 # Count 'D' from i+1 index
while (j < len(Str) and Str[j] == 'D') :
dCount+=1
j+=1
k = dCount # Store dCount
while (dCount >= 0) :
ans += str(cur + dCount)
dCount-=1
cur += (k + 1) # Manages next cur val
dCount = 0
i = j
return ans
print(findMinNumberPattern("DIDID"))
print(findMinNumberPattern("DIDIII"))
print(findMinNumberPattern("DDDIIDI"))
print(findMinNumberPattern("IDIDIID"))
print(findMinNumberPattern("DIIDIDD"))
print(findMinNumberPattern("IIDIDDD"))
# This code is contributed by mukesh07.
C#
// This code illustrates to find minimum number following
// pattern with optimized space and modular code.
using System;
class GFG {
// This function returns minimum number following
// pattern of increasing or decreasing sequence.
public static string findMinNumberPattern(string str)
{
string ans = ""; // Minimum number following pattern
int i = 0;
int cur = 1; // cur val following pattern
int dCount = 0; // Count of char 'D'
while (i < str.Length) {
char ch = str[i];
// If 1st ch == 'I', incr and add to ans
if (i == 0 && ch == 'I') {
ans += cur;
cur++;
}
// If cur char == 'D',
// incr dCount as well, since we always
// start counting for dCount from i+1
if (ch == 'D') {
dCount++;
}
int j = i + 1; // Count 'D' from i+1 index
while (j < str.Length
&& str[j] == 'D') {
dCount++;
j++;
}
int k = dCount; // Store dCount
while (dCount >= 0) {
ans += (cur + dCount);
dCount--;
}
cur += (k + 1); // Manages next cur val
dCount = 0;
i = j;
}
return ans;
}
static void Main() {
Console.WriteLine(findMinNumberPattern("DIDID"));
Console.WriteLine(findMinNumberPattern("DIDIII"));
Console.WriteLine(findMinNumberPattern("DDDIIDI"));
Console.WriteLine(findMinNumberPattern("IDIDIID"));
Console.WriteLine(findMinNumberPattern("DIIDIDD"));
Console.WriteLine(findMinNumberPattern("IIDIDDD"));
}
}
// This code is contributed by mukesh07.
Javascript
<script>
// This code illustrates to find minimum number following
// pattern with optimized space and modular code.
// This function returns minimum number following
// pattern of increasing or decreasing sequence.
function findMinNumberPattern(str)
{
let ans = ""; // Minimum number following pattern
let i = 0;
let cur = 1; // cur val following pattern
let dCount = 0; // Count of char 'D'
while (i < str.length) {
let ch = str[i];
// If 1st ch == 'I', incr and add to ans
if (i == 0 && ch == 'I') {
ans += cur;
cur++;
}
// If cur char == 'D',
// incr dCount as well, since we always
// start counting for dCount from i+1
if (ch == 'D') {
dCount++;
}
let j = i + 1; // Count 'D' from i+1 index
while (j < str.length
&& str[j] == 'D') {
dCount++;
j++;
}
let k = dCount; // Store dCount
while (dCount >= 0) {
ans += (cur + dCount);
dCount--;
}
cur += (k + 1); // Manages next cur val
dCount = 0;
i = j;
}
return ans;
}
document.write(findMinNumberPattern("DIDID")+"<br>");
document.write(findMinNumberPattern("DIDIII")+"<br>");
document.write(findMinNumberPattern("DDDIIDI")+"<br>");
document.write(findMinNumberPattern("IDIDIID")+"<br>");
document.write(findMinNumberPattern("DIIDIDD")+"<br>");
document.write(findMinNumberPattern("IIDIDDD")+"<br>");
// This code is contributed by unknown2108
</script>
Producción
214365 2143567 43215768 13254687 21354876 12438765
Complejidad de tiempo : O(n)
Espacio Auxiliar : O(1)
Método 7: (Reversiones de substrings)
La idea es tomar el número más pequeño con len(s)+1 y realizar inversiones para cada substring que contenga solo ‘D’ .
Siga los pasos a continuación para resolver el problema:
1. Cree el menor número posible de longitud len(s)+1.
2. Atraviese la cuerda (digamos i).
3. Busque la primera y la última aparición de ‘D’ para cada substring que contenga solo ‘D’.
4. Invierta cada una de esas substrings y reinicie la primera y la última aparición.
C++14
#include <bits/stdc++.h>
using namespace std;
string get_num_seq(string& str_seq)
{
int n=str_seq.length(),start=-1,end=-1;
string ans;
for(int i=1;i<=n+1;i++)
ans.push_back(i+48);
for(int i=0;i<n;i++)
{
if(str_seq[i]=='D')
{
if(start==-1)
start=i;
end=i;
}
else {
if(start!=-1)
reverse(ans.begin()+start,ans.begin()+end+2);
start=-1;
end=-1;
}
}
if(start!=-1)
reverse(ans.begin()+start,ans.begin()+end+2);
return ans;
}
// driver's code
int main()
{
string str_seq="DDIDDIID";
cout<<get_num_seq(str_seq);
return 0;
}
// this code is contributed by prophet1999
Producción
321654798
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
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