Entradas

Mostrando las entradas etiquetadas como slindingWindows

Técnicas para Algoritmos: Sliding Windows #2

Imagen
D ada una cadena(st) y un patrón(pt), averigüe si la cadena contiene alguna permutación del patrón. Detalles:  Si una cadena tiene 'n' caracteres distintos, tendrá n! Permutaciones. Del ejemplo anterior podemos decir que una cadena de 3 caracteres tiene un total de  3! = 3 *2*1 = 6 permutaciones. La permutación se define como la reorganización de los caracteres de la cadena. Por ejemplo, "abc" tiene las siguientes seis permutaciones: abc acb bac bca cab cba Escenarios de prueba:  Escenario #1:  Entrada: st=" oidbcaf ", pt="abc" (Strings). Salida:   true (Boolean). Explicación: La cadena contiene "bca" , que es una permutación del patrón dado. Escenario #2:  Entrada: st="odicf", pt="dc" (Strings). Salida:   false (Boolean). Explicación: No hay permutación del patrón presente en la cadena dada como una subcadena.. Escenario #3:  Entrada: st="bcdxabcdy", pt="bcdyabcdx" (Strings). Salida:   tru...

Técnicas para Algoritmos: Sliding Windows #1

Imagen
Estos ejercicios que presentaremos a continuación se fundamentan en la estrategia Slinding Windows. Aplicar esta técnica a problemas donde sea necesario recorrer una lista de elementos en donde tengas que buscar o calcular algo a partir de sub arreglos con elementos consecutivos de un tamaño k elementos. Escenario de pruebas: Dado un arreglo, encuentra el promedio de todos los sub arreglos de tamaño k. Input: arr = [1, 3, 2, 6, -1, 4, 1, 8, 2];  k= 5 Output: [ 2.2, 2.8, 2.4, 3.6, 2.8] Este problema puede tener varias soluciones posibles que pueden ser válidas,  en esta introducción tomaremos dos soluciones posibles. La primera solución no sigue ninguna estrategia en particular que le llamaremos fuerza bruta (FB) y la segunda solución si sigue una estrategia en este caso Sliding Windows (SW). Con estas dos estrategias vamos a resaltar la importancia de tener un plan a seguir bien pensado para resolver este tipo de problemas.  Problema (fácil): Promedio de sub arreglos ...