Ahora vamos a poner en práctica todo lo que hemos aprendido durante este módulo con algunos retos. ¡Empecemos!
Espero tus soluciones en la sección de aportes con tu lenguaje preferido, también puedes ver y aportar a las soluciones de tus compañeras y compañeros. 👨🚀🚀
Algunos ejemplos de casos en los que se puede utilizar este patrón son:
Para encontrar una subcadena que cumpla ciertas condiciones, puedo usar 2 apuntadores y avanzar uno mientras parece una posible subcadena, mientras que el otro indica donde inicia la subcadena.
Para comparar elementos en dos listas puedo usar 2 punteros, cada uno de estos apuntadores tiene noción del punto actual en una de las listas.
Para mover y ordenar los elementos “in place”, puedo tener apuntadores para tener noción de los elementos ordenados y los que no.
1. Mover ceros al final
Dada la lista de enteros nums, mueve todos los ceros al final de la misma, manteniendo el orden relativo de los elementos no nulos.
Reto: reordena los valores “in place”, sin hacer una copia de la lista.
Escribe una función que invierta una cadena. La cadena de entrada se da como un arreglo de caracteres.
Reto: hacerlo modificando la lista de entrada con O(1) de memoria extra.
Ejemplo 1:
# Entrada: s =["h","e","l","l","o"]# Salida:["o","l","l","e","h"]
Ejemplo 2:
# Entrada: s =["H","a","n","n","a","h"]# Salida:["h","a","n","n","a","H"]
3. Reordenar colores
Dado un arreglo nums con n objetos de color rojo, blanco o azul, ordénalos en su lugar para que los objetos del mismo color sean adyacentes, con los colores en el orden rojo, blanco y azul.
Utilizaremos los enteros 0, 1 y 2 para representar el color rojo, blanco y azul, respectivamente.
Reto 1: debes resolver este problema sin utilizar la función de ordenación de la biblioteca.
Reto 2: ¿podrías idear un algoritmo de una sola pasada utilizando solo un espacio extra constante?
Dada una cadena de caracteres, invierte solo todas las vocales de la cadena.
Las vocales son 'a', 'e', 'i', 'o' y 'u', 'A', 'E', 'I', 'O', 'U'.
Ejemplo 1:
# Entrada: s ="hola"# Salida:"halo"
Ejemplo 2:
# Entrada: s = s ="leetcode"# Salida:"leotcede"
5. Cuadrados de un arreglo ordenado
Dado un arreglo de números enteros ordenados en orden ascendente, devuelve una matriz de los cuadrados de cada número ordenados en orden no decreciente.
Ejemplo 1:
# Entrada: nums =[-4,-1,0,3,10]# Salida:[0,1,9,16,100]# Explicación: Después de elevar al cuadrado, el arreglo se convierte en [16,1,0,9,100].# Después de ordenar, se convierte en [0,1,9,16,100].
Dada una cadena de caracteres, averigua si la cadena dada es un palíndromo o no. Puedes eliminar un carácter de la cadena. Una cadena es un palíndromo si se lee igual hacia adelante y hacia atrás.
Ejemplo 1:
# Entrada: s ="aba"# Salida: true
Ejemplo 2:
# Entrada: s ="abca"# Salida: true
#Explicación: Podría eliminar el carácter 'c'.
7. Intersecciones de la lista de intervalos
Dadas dos listas de intervalos cerrados, lista1 y lista2, donde lista1[i] = [inicio_i, final_i] y lista2[j] = [inicio_j, final_j]. Cada lista de intervalos es disjunta por pares y está ordenada.
Devuelve la intersección de estas dos listas de intervalos.
Un intervalo cerrado [a, b] (con a <= b) denota el conjunto de números reales x con a <= x <= b. La intersección de dos intervalos cerrados es un conjunto de números reales que está vacío o representado como un intervalo cerrado. Por ejemplo, la intersección de [1, 3] y [2, 4] es [2, 3].
Los últimos tres me toco con ayuda parcial, pero tremenda la práctica.
Mover ceros al final
Invertir string
Reordenar colores
Invertir vocales
Cuadrados de un arreglo ordenado
Validar palíndromo (con k reemplazos)
Intersecciones de la lista de intervalos
Creo que en la solución del problema 1 estás ordenando los números de mayor a menor, pero el problema dice "manteniendo el orden relativo de los numeros no nulos" y creo que se refiere a: [0,10,5,12,0] ----> [10,5,12,0,0]
Claro que esto se resolvería con una pregunta al entrevistador y como no podemos, pues yo quiero creer que este es el caso, además de que no sabemos si hay palabras también.
constmoveZeros=(nums)=>{let len = nums.length;let pointer =0;while(len >0){if(nums[pointer]===0){ nums.splice(pointer,1); nums.push(0);}else{ pointer++;} len--;}console.log(nums);}moveZeros([0,1,0,3,12]);moveZeros([0]);constinvertString=(text)=>{let left =0;let right = text.length-1;while(left < right){ currentValue = text[right] text[right]= text[left]; text[left]= currentValue; left++; right--;}console.log(text);}invertString(['h','e','l','l','o']);invertString(["H","a","n","n","a","h"]);constsortColors=(nums)=>{let len = nums.length;let pointer =0;while(len >0){if(nums[pointer]===0){ nums.splice(pointer,1); nums.unshift(0);}elseif(nums[pointer]===2){ nums.splice(pointer,1); nums.push(2);} pointer++; len--;}console.log(nums);}sortColors([2,0,2,1,1,0]);sortColors([2,0,1]);constinvertVowels=(text)=>{const vowels =['a','e','i','o','u'];const newText = text.split("");console.log(newText);let left =0;let right = text.length-1;let currentChar ='';while(left < right){if(vowels.includes(newText[left])&& vowels.includes(newText[right])){ currentChar = newText[right]; newText[right]= newText[left]; newText[left]= currentChar; left++; right--;}elseif(!vowels.includes(newText[left])){ left++;}elseif(!vowels.includes(newText[right])){ right--}}console.log(newText.join(""));}invertVowels("hola");invertVowels("leetcode");constsortList=(nums)=>{let left =0;let right = nums.length-1;for(const key in nums){ nums[key]=Math.pow(Math.abs(nums[key]),2);}while(left < right){if(nums[left]> nums[right]){ nums.splice(right +1,0, nums[left]); nums.splice(left,1);}else{ right--;}}console.log(nums);}sortList([-4,-1,0,3,10]);sortList([-7,-3,2,3,11]);constpalindrome=(text)=>{const newText = text.split("");let left =0;let right = newText.length-1;let currentChar ='';while(left < right){ currentChar = newText[right] newText[right]= newText[left]; newText[left]= currentChar; left++; right--;}return newText.join("")=== text ?true:false;}console.log(palindrome("aba"));console.log(palindrome("abca"));constintersectList=(firstList, secondList)=>{let left =0;let right =0;const newList =[];const len =Math.min(firstList.length, secondList.length);while(left < len && right < len){const currentList =[];if(firstList[left][0]<= secondList[right][0]&& secondList[right][0]<= firstList[left][1]){ currentList.push(secondList[right][0]);}if(firstList[left][0]<= secondList[right][1]&& secondList[right][1]<= firstList[left][1]){ currentList.push(secondList[right][1]);}if(secondList[right][0]<= firstList[left][0]&& firstList[left][0]<= secondList[right][1]){ currentList.push(firstList[left][0]);}if(secondList[right][0]<= firstList[left][1]&& firstList[left][1]<= secondList[right][1]){ currentList.push(firstList[left][1]);}if(currentList.length>0){ newList.push(currentList);}if(firstList[left][0]< secondList[right][0]){ left++;}else{ right++;}}console.log(newList);}intersectList([[0,2],[5,10],[13,23],[24,25]],[[1,5],[8,12],[15,24],[25,26]]);intersectList([[1,3],[5,9]],[]);
Mis aportes en C++:
#include<iostream>#include<vector>voidmove_zeroes(std::vector<int>&data){ int p1 =0; int p2 =0;while(p1 < data.size()&& p2 < data.size()){if(data[p1]!=0){ p1++;}elseif(data[p2]==0){ p2++;}else{ data[p1]+= data[p2]; data[p2]= data[p1]- data[p2]; data[p1]-= data[p2];}}}int main(){std::vector<int> data ={0,1,0,3,12};move_zeroes(data);for(auto d: data) std::cout << d <<" ";std::cout << std::endl; data ={0};move_zeroes(data);for(auto d: data) std::cout << d <<" ";std::cout << std::endl;return0;}
#include<iostream>#include<vector>voidreverse_string(std::vector<char>&str){ int p1 =0; int p2 = str.size()-1;while(p1 < p2){ str[p1]+= str[p2]; str[p2]= str[p1]- str[p2]; str[p1]-= str[p2]; p1++; p2--;}}int main(){std::vector<char> str ={'h','e','l','l','o'};reverse_string(str);for(auto c:str) std::cout << c <<" ";std::cout <<std::endl;std::vector<char> str2 ={'H','a','n','n','a','h'};reverse_string(str2);for(auto c:str2) std::cout << c <<" ";std::cout <<std::endl;return0;}
#include<iostream>#include<vector>voidorder_rba(std::vector<int>&rba){ int pr =0; int pb =0; int pa = rba.size()-1;while(pb <= pa){if(rba[pb]==0){ rba[pr]+= rba[pb]; rba[pb]= rba[pr]- rba[pb]; rba[pr]-= rba[pb]; pr++; pb++;}elseif(rba[pb]==2){ rba[pa]+= rba[pb]; rba[pb]= rba[pa]- rba[pb]; rba[pa]-= rba[pb]; pa--;}else{ pb++;}}}int main(){std::vector<int> rba ={2,0,2,1,1,0};order_rba(rba);for(auto c: rba) std::cout << c <<" ";std::cout << std::endl; rba ={2,0,1};order_rba(rba);for(auto c: rba) std::cout << c <<" ";std::cout << std::endl; rba ={1,2,0,1};order_rba(rba);for(auto c: rba) std::cout << c <<" ";std::cout << std::endl;return0;}
Invertir string
Mover ceros al final
Hice todos los ejercicios con la complejidad algorítmica O(n). En algunos de ellos no sabia lo que estaba haciendo pero al final funcionaban, a lo que me refiero es que no se como explicar lo que estaba haciendo.
Mi aporte para el ejercicio "Invertir vocales". Decidí usar un diccionario/objeto para las vocales, ya que la función Array.prototype.includes hace una búsqueda lineal de forma ascendente pasando por todos los elementos del arreglo.
functionreverseVowels(string){// O(1)let left =0;let right = string.length-1;let temp ="";const vowels =['a','e','i','o','u','A','E','I','O','U']const dictionary ={}; string =Array.from(string);// Building the vowels dictionary. O(n) vowels.forEach(character=>{ dictionary[character]= character;// O(1)});// O(n)while(left < right){// Pointer have found a vowelif(dictionary[string[left]]&& dictionary[string[right]]){ temp = string[left]; string[left]= string[right]; string[right]= temp; left++; right--;}if(!dictionary[string[left]]){// No vowel on left, increase pointer. left++;}elseif(!dictionary[string[right]]){// No vowel on right, decrease pointer. right--;}}return string.join("");}
Mi aporte para el ejercicio "Invertir string"
functionreverseList(list){let left =0;let right = list.length-1;let temp =""while(left < right){ temp = list[right]; list[right]= list[left]; list[left]= temp; left++; right--;}return list;}
