LOS
10 MEJORES ALGORITMOS DE MATRICES
9.- El subconjunto más pequeño con una suma mayor que un valor dado |
&&&&&&&&&&
&&&&&&&
&&&
&
1.-
Invertir una cadena sin afectar a los caracteres especiales
Dada
una cadena, que contiene caracteres especiales junto con los alfabetos ('a' a
'z' y 'A' a 'Z'), invierta la cadena de manera que los caracteres especiales no
se vean afectados
Ejemplo:
Entrada: str = "a,b$c"
Salida:
str = "c,b$a"
El carácter $ no se mueve, solo la subsecuencia “abc”
Entrada: str = "Ab,c,de!$"
Salida:
str = "ed,c,bA!$"
Solución
sencilla:
1)
Crear una matriz de caracteres temporales, digamos temp[].
2)
Copiar los caracteres alfabéticos de la matriz dada a temp[].
3)
Invertir temp[] usando un algoritmo estándar de
inversión de cadenas.
4)
Ahora cruza la cadena de entrada y temp en un solo
bucle. Donde quiera que haya un carácter alfabético en la cadena de entrada,
reemplácelo por el carácter actual de temp[].
Solución
eficiente:
La
complejidad temporal de la solución anterior es O(n), pero requiere espacio
adicional y hace dos travesías de la cadena de entrada.
Podemos
invertir con una travesía y sin espacio extra. A continuación se muestra el
algoritmo. Veamos:
1)
Que la cadena de entrada sea "str[]" y la
longitud de la cadena sea "n".
2)
l = 0, r = n-1
3)
Mientras que l es más pequeño que r, haga lo siguiente
a) Si str[l] no
es un carácter alfabético, haga l++
b) Si no, si no es un carácter alfabético,
entonces...
c) Intercambiar las tiras y las tiras
A
continuación se muestran las implementaciones del algoritmo anterior, en
lenguaje C++.
#include<bits/stdc++.h>
usando namespace std;
bool
isAlphabet(char x)
{ retorno ( (x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z') );
}
void
reverse(char str[])
{ // Iniciar los punteros
izquierdo y derecho
int
r = strlen(str) - 1, l = 0;
// Atravesar desde ambos
extremos hasta 'l' y 'r' mientras que (l < r)
{
// Ignorar los
especiales
If (!es Alfabeto(str[l]))
l++;
else
if (!es Alfabeto(str[r]))
r--;
{
swap(str[l], str[r]);
l++;
r--;
}
}
}
// Código principal
int
main()
{
char
str[] = "a!!!b.c.d,e'f,ghi";
cout <<
"Cadena de entrada: " << str
<<< endl;
reverse(str);
cout
<< "Cadena de salida: " << str
<<< endl;
retorno 0;
}
Cadena de entrada: a!!!b.c.d,e'f,ghi
Cadena de salida: i!!! h.g.f, e'd, cba
2.-
Dada una lista, imprime todas las particiones de palíndromos posibles
Dada
una ristra, encontrar todas las posibles particiones palindromicas
de una ristra dada.
Nótese
que este problema es diferente del problema de partición del Palíndromo, allí la
tarea era encontrar la partición con cortes mínimos en la cadena de entrada.
Aquí necesitamos imprimir todas las particiones posibles.
La
idea es revisar cada subcadena empezando por el
primer carácter, comprobar si es el palíndromo. Si es así, entonces agregar la subcadena a la solución y recurrir para la parte restante.
Abajo está el algoritmo completo.
#include<bits/stdc++.h>
using namespace
std;
bool isPalindrome(string str, int
low, int high)
{
while (low < high)
{
if
(str[low] != str[high])
return false;
low++;
high--;
}
return true;
}
// Función recursiva para encontrar todas las particiones palindricas de str[start..n-1]
// allPart --> Un vector de cuerdas. Cada
vector dentro de él almacena
// una partición
// currPart --> Un vector de cuerdas para
almacenar la partición actual
void allPalPartUtil(vector<vector<string> >&allPart,
vector<string> &currPart,
int start, int
n, string str)
{
// If 'start' has reached len
if (start
>= n)
{
allPart.push_back(currPart);
return;
}
for (int
i=start; i<n; i++)
{
if
(isPalindrome(str, start, i))
{
currPart.push_back(str.substr(start, i-start+1));
allPalPartUtil(allPart, currPart, i+1, n, str);
currPart.pop_back();
}
}
}
void allPalPartitions(string str)
{
int n = str.length();
vector<vector<string>
> allPart;
vector<string> currPart;
allPalPartUtil(allPart, currPart, 0, n, str);
for (int
i=0; i< allPart.size(); i++ )
{
for
(int j=0; j<allPart[i].size(); j++)
cout << allPart[i][j]
<< " ";
cout
<< "\n";
}
}
// Principal
int main()
{
string str = "nitin";
allPalPartitions(str);
return 0;
}
3.-
Contar trillizos con una suma menor que un valor dado
Dada
una serie de números enteros distintos y un valor de suma. Encuentra el recuento
de trillizos con una suma menor que el valor de la suma dada. La complejidad de
tiempo esperada es O(n2).
Ejemplo:
Entrada
: arr[] = {-2, 0, 1, 3}
suma = 2.
Salida:
2
Explicación:
Abajo hay trillizos con una suma inferior a 2
(-2, 0, 1) y (-2, 0, 3)
1)
Ordena la matriz de entrada en orden creciente.
2)
Inicializar el resultado como 0.
3)
Ejecuta un bucle de i = 0 a n-2. Una
iteración de este bucle encuentra todo
trillizos con arresto como primer elemento.
a) Inicializar otros dos elementos como
elementos de esquina del subconjunto
arr[i+1..n-1],
es decir, j = i+1 y k = n-1
b) Mueve j y k hacia el otro hasta que se
encuentren, es decir, mientras que (j = suma), entonces haz k--
// Si no, para las corrientes i y
j, puede (k-j) haber terceros elementos posibles
// que satisfacen la restricción.
(ii) Else
Do ans += (k - j) seguido de j++
#include<bits/stdc++.h>
using namespace
std;
int countTriplets(int arr[], int
n, int sum)
{
sort(arr,
arr+n);
int ans
= 0;
for (int
i = 0; i < n - 2; i++)
{
int
j = i + 1, k = n - 1;
while
(j < k)
{
if (arr[i] + arr[j]
+ arr[k] >= sum)
k--;
else
{
ans += (k - j);
j++;
}
}
}
return ans;
}
// Principal
int main()
{
int arr[]
= {5, 1, 3, 4, 7};
int n = sizeof arr / sizeof
arr[0];
int sum = 12;
cout << countTriplets(arr, n, sum)
<< endl;
return 0;
}
Salida: 4
4.-
Convertir la matriz en la moda Zig-Zag
Dada
una serie de elementos DISTINTOS, reorganice los elementos de la serie en zig-zag en tiempo O(n). El arreglo convertido debe ser en
forma a < b > c < d > e < f.
Ejemplo:
Entrada:
arr[] = {4, 3, 7, 8, 6, 2, 1}
Salida:
arr[] = {3, 7, 4, 8, 2, 6, 1}
Una
solución simple es ordenar primero el conjunto. Después de ordenar, excluir el primer
elemento, intercambiar los elementos restantes en parejas. (es decir, mantener
el arr[0] tal cual, intercambiar el arr[1] y el arr[2], intercambiar
el arr[3] y el arr[4], y
así sucesivamente).
Complejidad
del tiempo: O(N log N) ya que necesitamos ordenar la matriz primero
Podemos
convertir en O(n) tiempo usando un enfoque eficiente. La idea es utilizar una
modificación de una pasada de tipo burbuja.
Mantener
una bandera para representar qué orden(es decir, < o >) necesitamos
actualmente.
Si
los dos elementos actuales no están en ese orden, entonces intercambien esos
elementos, de lo contrario no.
Veamos
la lógica principal usando tres elementos consecutivos A, B, C.
Supongamos
que estamos procesando B y C actualmente y la relación actual es '<', pero
tenemos B > C. Como la relación actual es '<' la relación anterior debe
ser '>' es decir, A debe ser mayor que B. Entonces, la relación es A > B
y B > C. Podemos deducir A > C. Entonces si intercambiamos B y C entonces
la relación es A > C y C < B. Finalmente obtenemos el orden deseado A C B
#include <iostream>
using namespace
std;
void zigZag(int arr[], int
n)
{
// La bandera verdadera indica la
relación "<" se espera,
// Si no, se espera
">". La primera relación esperada
// es "<"
bool flag
= true;
for (int
i=0; i<=n-2; i++)
{
if
(flag)
{
/* Si tenemos una
situación como A > B > C,
obtenemos A > B < C
cambiando B y C */
if (arr[i] > arr[i+1])
swap(arr[i], arr[i+1]);
}
else {
/* Si tenemos una
situación como A < B < C,
obtenemos A < C > B
intercambiando B y C */
if (arr[i] < arr[i+1])
swap(arr[i], arr[i+1]);
}
flag
= !flag;
}
}
// Principal
int main()
{
int arr[]
= {4, 3, 7, 8, 6, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
zigZag(arr, n);
for (int
i=0; i<n; i++)
cout
<< arr[i] << " ";
return 0;
}
Salida: 3 7
4 8 2
6 1
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
5.-
Generar todas las matrices ordenadas a partir de elementos alternativos de dos
matrices ordenadas dadas
Dados
dos arreglos ordenados A y B, genera todos los arreglos posibles de tal manera
que el primer elemento se toma de A, luego de B, luego de A y así sucesivamente
en orden creciente hasta que los arreglos se agoten. Las matrices generadas
deben terminar con un elemento de B.
Por
ejemplo
A
= {10, 15, 25}
B
= {1, 5, 20, 30}
Los
arreglos resultantes son:
10 20
10 20 25 30
10 30
15 20
15 20 25 30
15 30
25 30
Le
recomendamos encarecidamente que minimice su navegador y lo pruebe usted mismo
primero.
La
idea es usar la recursión. En la función recursiva, se pasa una bandera para
indicar si el elemento actual en la salida debe ser tomado de 'A' o 'B'. A
continuación se muestra la implementación de C++.
#include<bits/stdc++.h>
using namespace
std;
void printArr(int arr[], int
n);
/* La función de generar e imprimir todos los conjuntos ordenados de
elementos alternativos de
A[i..m-1]' y 'B[j..n-1]'.
Si "bandera" es cierto,
entonces el elemento actual debe ser incluido desde A, de lo contrario
de B.
'len' es
el índice en la matriz de salida C[]. Imprimimos la matriz de salida cada vez
antes de incluir un carácter de A
sólo si la longitud de la matriz de salida es
mayor que 0. Intentamos que todas
las combinaciones posibles
*/
void generateUtil(int A[], int B[], int C[], int i, int j, int m, int
n,
int len, bool
flag)
{
if (flag) {
if
(len) printArr(C, len+1);
for
(int k = i; k < m; k++)
{
if (!len)
{
/*
este bloque funciona para que la primera llamada incluya
el primer
elemento de la matriz de salida
*/
C[len] = A[k];
generateUtil(A, B, C, k+1, j, m, n, len,
!flag);
}
else {
if (A[k] > C[len])
{
C[len+1]
= A[k];
generateUtil(A, B, C, k+1, j, m, n, len+1, !flag);
}
}
}
}
else {
for
(int l = j; l < n; l++)
{
if (B[l] > C[len])
{
C[len+1]
= B[l];
generateUtil(A, B, C, i, l+1, m, n, len+1, !flag);
}
}
}
}
void generate(int A[], int B[], int m, int n)
{
int C[m+n];
generateUtil(A, B, C, 0,
0, m, n, 0, true);
}
void printArr(int arr[], int
n)
{
for (int
i = 0; i < n; i++)
cout
<< arr[i] << " ";
cout << endl;
}
// Principal
int main()
{
int A[] = {10, 15, 25};
int B[] = {5, 20, 30};
int n = sizeof(A)/sizeof(A[0]);
int m = sizeof(B)/sizeof(B[0]);
generate(A, B, n, m);
return 0;
}
Salida:
10 20
10 20 25 30
10 30
15 20
15 20 25 30
15 30
25 30
6.-
Trillizo de Pitágoras en un conjunto
Dada una
matriz de números enteros, escribe una función que devuelva verdadera si hay un
triplete (a, b, c) que satisfaga a2 + b2 = c2.
Ejemplo:
Entrada: arr[] = {3, 1, 4, 6, 5}
Salida:
Verdadero
Hay un
trillizo pitagórico (3, 4, 5).
Podemos
resolver esto en tiempo de O(n2) clasificando la matriz primero.
1)
Haz un cuadrado de cada elemento de la matriz de entrada. Este paso lleva O(n)
tiempo.
2)
Ordena la matriz cuadrada en orden creciente. Este paso lleva O(nLogn) tiempo.
3)
Para encontrar un triplete (a, b, c) de tal manera que a2 = b2 + c2, haz lo
siguiente.
Fijar
'a' como último elemento de la matriz ordenada.
Ahora
busque el par (b, c) en la submatriz entre el primer
elemento y 'a'. Un par (b, c) con una suma dada puede ser encontrado en el
tiempo de O(n) usando el algoritmo de encuentro en el medio discutido en el
método 1 de este post.
Si
no se encuentra un par para la actual "a", entonces mueva
"a" una posición hacia atrás y repita el paso 3.2.
#include <algorithm>
#include <iostream>
using namespace
std;
// Devuelve verdadero si hay un trillizo con la siguiente propiedad
// A[i]*A[i] = A[j]*A[j] + A[k]*[k]
// Tenga en cuenta que esta función modifica el conjunto dado
bool isTriplet(int arr[], int
n)
{
for (int
i = 0; i < n; i++) arr[i] = arr[i] * arr[i];
sort(arr,
arr + n);
for (int
i = n - 1; i >= 2; i--) {
// Para encontrar los otros
dos elementos, inicia dos índices
// ...variables de dos
esquinas del conjunto y se mueven...
// ellos hacia el otro
int
l = 0;
int
r = i - 1;
while
(l < r) {
if (arr[l] + arr[r]
== arr[i])
return true;
(arr[l] + arr[r] < arr[i]) ? l++ : r--;
}
}
return false;
}
//Principal
int main()
{
int arr[]
= { 3, 1, 4, 6, 5 };
int arr_size
= sizeof(arr) / sizeof(arr[0]);
isTriplet(arr, arr_size) ? cout << "Yes" : cout
<< "No";
return 0;
}
Salida: Si
Complejidad: O(n^2)
7.-
Longitud del mayor sub-arreglo con elementos contiguos
Dada
una serie de números enteros distintos, encuentre la longitud del subconjunto más
largo que contenga números que puedan ser ordenados en una secuencia continua.
Ejemplo:
Entrada:
arr[] = {10, 12, 11};
Salida:
Longitud del subconjunto contiguo más largo
Recomendamos
encarecidamente que minimice el navegador e intente esto usted mismo primero.
Lo
importante que hay que tener en cuenta es que todos los elementos son
distintos. Si todos los elementos son distintos, entonces un subconjunto tiene
elementos contiguos si y sólo si la diferencia entre los elementos máximos y
mínimos del subconjunto es igual a la diferencia entre el último y el primer
índice del subconjunto. Por lo tanto, la idea es llevar la cuenta de los
elementos mínimos y máximos en cada submatriz.
#include<iostream>
using namespace
std;
// Funciones de utilidad para encontrar el mínimo y el máximo de
// dos elementos int min(int
x, int y) { return (x <
y)? x : y; }
int max(int x, int y) { return (x > y)? x : y; }
// Devuelve la longitud del subarreglo contiguo
más largo
int findLength(int arr[], int
n)
{
int max_len
= 1;
for (int
i=0; i<n-1; i++)
{
int
mn = arr[i], mx = arr[i];
for
(int j=i+1; j<n; j++)
{
mn = min(mn, arr[j]);
mx
= max(mx, arr[j]);
if ((mx - mn) == j-i)
max_len = max(max_len,
mx-mn+1);
}
}
return max_len; // Return result
}
// Principal
int main()
{
int arr[]
= {1, 56, 58, 57, 90, 92, 94, 93, 91, 45};
int n = sizeof(arr)/sizeof(arr[0]);
cout << " La longitud
del subconjunto contiguo más largo es de "
<< findLength(arr, n);
return 0;
}
Salida: La longitud del subconjunto contiguo más largo es de 5
La complejidad temporal de la solución anterior es O(n2).
8.-
Encontrar el valor entero positivo más pequeño que no puede ser representado
como la suma de cualquier subconjunto de un conjunto dado
Dada
una matriz ordenada (ordenada en orden no decreciente) de números positivos,
encuentre el valor entero positivo más pequeño que no pueda representarse como
suma de elementos de ningún subconjunto del conjunto dado.
La
complejidad temporal esperada es O(n).
Ejemplo:
Entrada:
arr[] = {1, 3, 6, 10, 11, 15};
Salida:
2
Una
solución sencilla es empezar desde el valor 1 y comprobar todos los valores uno
por uno si pueden sumarse a los valores de la matriz dada. Esta solución es muy
ineficiente ya que reduce al problema de la suma de subconjuntos que es un
conocido problema completo de NP.
Podemos
resolver este problema en O(n) tiempo usando un simple bucle. Dejemos que el array de entrada sea arr[0..n-1].
Inicializamos el resultado como 1 (el resultado más pequeño posible) y
atravesamos el array dado. Dejemos que el elemento
más pequeño que no puede ser representado por los elementos en los índices de 0
a (i-1) sea 'res', hay dos posibilidades siguientes cuando consideramos el
elemento en el índice i:
1)
Decidimos que "res" es el resultado final: Si arr[i]
es mayor que 'res', entonces encontramos la brecha que es 'res' porque los
elementos después de arr[i] también van a ser mayores
que 'res'.
2)
El valor de "res" se incrementa después de considerar el arr[i]: El valor de 'res' se incrementa por arr[i] (¿por qué? Si los elementos de 0 a (i-1) pueden
representar 1 a 'res-1', entonces los elementos de 0 a i pueden representar 1 a
'res + arr[i] - 1' estarían añadiendo 'arr[i]' a todos los subconjuntos que representan 1 a 'res')
#include <bits/stdc++.h>
using
namespace std;
// Devuelve el número más pequeño que no puede ser representado
como suma
// del subconjunto de elementos del conjunto representado por el
conjunto ordenado arr[0..n-1]
int
findSmallest(int arr[], int n)
{
int
res = 1; // Initialize result
// Atravesar la matriz e incrementar la 'res' si la arr[i] es
// más pequeño o igual a 'res'.
for
(int i = 0; i < n && arr[i]
<= res; i++)
res = res + arr[i];
return
res;
}
// Principal
int
main()
{
int
arr1[] = {1, 3, 4, 5};
int
n1 = sizeof(arr1)/sizeof(arr1[0]);
cout
<< findSmallest(arr1, n1) << endl;
int
arr2[] = {1, 2, 6, 10, 11, 15};
int
n2 = sizeof(arr2)/sizeof(arr2[0]);
cout
<< findSmallest(arr2, n2) << endl;
int
arr3[] = {1, 1, 1, 1};
int
n3 = sizeof(arr3)/sizeof(arr3[0]);
cout
<< findSmallest(arr3, n3) << endl;
int
arr4[] = {1, 1, 3, 4};
int
n4 = sizeof(arr4)/sizeof(arr4[0]);
cout
<< findSmallest(arr4, n4) << endl;
return
0;
}
Salida: 2 4 5 10
Complejidad: O(n)
9.-
El subconjunto más pequeño con una suma mayor que un valor dado
Dada
una matriz de números enteros y un número x, encuentra la submatriz
más pequeña con una suma mayor que el valor dado.
Ejemplo:
arr[]
= {1, 4, 45, 6, 0, 19}
x = 51
Salida:
3
La
longitud mínima del subgrupo es de {4, 45, 6}
Solución
eficiente: Este problema puede ser resuelto en O(n) tiempo usando la idea usada
en este post
#include <iostream>
using namespace
std;
// Devuelve la longitud del subconjunto más pequeño con una suma mayor que
x.
// Si no hay un subconjunto con la suma dada, entonces devuelve n+1
int smallestSubWithSum(int arr[], int
n, int x)
{
int curr_sum
= 0, min_len = n+1;
int start
= 0, end = 0;
while (end < n)
{
// Sigue añadiendo elementos
de la matriz mientras la suma actual
// es más pequeño que x
while
(curr_sum <= x && end
< n)
curr_sum += arr[end++];
while
(curr_sum > x && start
< n)
{
if (end - start
< min_len)
min_len = end - start;
curr_sum -= arr[start++];
}
}
return min_len;
}
//Principal
int main()
{
int arr1[] = {1, 4, 45,
6, 10, 19};
int x = 51;
int n1 = sizeof(arr1)/sizeof(arr1[0]);
int res1 = smallestSubWithSum(arr1, n1, x);
(res1 == n1+1)? cout
<< "Not possible\n"
:
cout << res1 << endl;
int arr2[] = {1, 10, 5,
2, 7};
int n2 = sizeof(arr2)/sizeof(arr2[0]);
x = 9;
int res2 = smallestSubWithSum(arr2, n2, x);
(res2 == n2+1)? cout
<< "Not possible\n"
:
cout << res2 << endl;
int arr3[] = {1, 11, 100,
1, 0, 200, 3, 2, 1, 250};
int n3 = sizeof(arr3)/sizeof(arr3[0]);
x = 280;
int res3 = smallestSubWithSum(arr3, n3, x);
(res3 == n3+1)? cout
<< "Not possible\n"
:
cout << res3 << endl;
return 0;
}
Salida: 3 1
4
10.-
Compra y venta de acciones para maximizar el beneficio
El costo de una acción en cada día se da en
una matriz, encuentra la máxima ganancia que puedes hacer comprando y vendiendo
en esos días. Por ejemplo, si la matriz dada es {100, 180, 260, 310, 40, 535,
695}, el máximo beneficio puede obtenerse comprando en el día 0, vendiendo en
el día 3. Otra vez compra en el día 4 y vende en el día 6. Si la serie de
precios dada se ordena en orden decreciente, entonces no se puede obtener
ningún beneficio.
Si
se nos permite comprar y vender una sola vez, entonces podemos usar el
siguiente algoritmo. Diferencia máxima entre dos elementos. Aquí se nos permite
comprar y vender varias veces.
El
siguiente algoritmo es para este problema.
Encuentra
los mínimos locales y guárdalos como índice de partida. Si no existe, regresa.
Encuentra
los máximos locales y guárdalos como índice final. Si llegamos al final,
guardad el final como índice final.
Actualiza
la solución (Incrementa la cuenta de pares de compra-venta)
Repita
los pasos anteriores si no se alcanza el final.
#include <bits/stdc++.h>
using namespace
std;
// Esta función encuentra la compra-venta
// programa para el máximo beneficio
void stockBuySell(int price[], int
n)
{
if (n == 1)
return;
int i = 0;
while (i < n - 1) {
// Encuentra los mínimos
locales
// Tenga en cuenta que el
límite es (n-2) como estamos
// comparando el elemento actual con el
siguiente elemento
while
((i < n - 1) && (price[i + 1] <= price[i]))
i++;
// Si llegamos al final,
rompe
// como ninguna otra solución
posible
if
(i == n - 1) break;
int
buy = i++;
// Encuentra los máximos
locales
// Tenga en cuenta que el
límite es (n-1) como estamos
// comparando con el elemento
anterior
while
((i < n) && (price[i] >= price[i - 1]))
i++;
int
sell = i - 1;
cout
<< "Buy on day: " << buy
<<
"\t Sell on day: " << sell
<< endl;
}
}
//Principal
int main()
{
int price[]
= { 100, 180, 260, 310, 40, 535, 695 };
int n = sizeof(price) / sizeof(price[0]);
stockBuySell(price, n);
return 0;
}
Salida:
Compra en el día : 0 Vende en el día: 3
Comprar en el día: 4 Vender en el día: 6
Complejidad temporal: El bucle exterior corre hasta que la i se convierte
en n-1. Los dos bucles internos incrementan el valor de i en cada iteración.
Así que la complejidad temporal global es O(n)
&&&&&&&&&&&&&
&&&&&&&&&
&&&
&