Soluciones:
Los últimos tres me toco con ayuda parcial, pero tremenda la práctica.
Introducción
Patrones de Arreglos y Strings: Ventana Deslizante y Dos Apuntadores
Arrays y Strings: Funcionamiento y Complejidades Temporales
Dos Apuntadores
Patrón de Dos Apuntadores en Algoritmos de Lista
Verificación de Orden en Diccionario Alienígena
Ordenamiento de Palabras en Idiomas Alienígenas
Playground: Verifying Alien Dictionary
Ordenación de Palabras en Diccionario Alienígena
Combinar Listas Ordenadas en un Array Ascendente
Ordenamiento de Listas con Complejidad Óptima y Espacio Constante
Playground: Merge Two Sorted Lists
Intercalación de Listas Ordenadas en Python
Resolver el problema "Container with Most Water" en Python
Cálculo Óptimo de Área en Listas de Alturas
Playground: Container with Most Water
Implementación de solución de cálculo de área máxima en Java
Implementación de Trapping Rainwater en Complejidad Lineal
Retos de Algoritmos con Apuntadores en Python
Patrones de Dos Apuntadores: Soluciones a Problemas Comunes en Python
Ventana Deslizante
Patrón Ventana Deslizante para Análisis de Datos Secuenciales
Subcadena más larga sin caracteres repetidos: patrón ventana deslizante
Algoritmo de Ventana Deslizante para Subcadenas Únicas
Playground: Longest Substring Without Repeating Characters
Algoritmo Python para Substring más Largo Sin Repeticiones
Retos de Algoritmos: Dos Apuntadores y Subcadenas
Máximos 1s Consecutivos y Subcadenas sin Repeticiones
Búsqueda Binaria
Algoritmo de búsqueda binaria en listas ordenadas
Búsqueda en Arrays Rotados: Encontrar Entero en Lista Ordenada
Búsqueda Binaria en Arreglos Rotados
Playground: Search in Rotated Arrays
Búsqueda en Arrays Rotados con C++
Búsqueda eficiente en matriz ordenada MxN
Búsqueda Binaria en Matrices 2D Ordenadas
Playground: Search 2D Array Matrix
Búsqueda Binaria en Matrices con Python
Próximos pasos
Estructuras de Datos Lineales: Conceptos y Aplicaciones
Retos de Algoritmos con Apuntadores en Python
17/35Lectura
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. 👨🚀🚀
...
Regístrate o inicia sesión para leer el resto del contenido.
Aportes 22
Preguntas 0
Ordenar por:
A continación mi aporte:
const moveZeros = (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]);
const invertString = (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"]
);
const sortColors = (nums) => {
let len = nums.length;
let pointer = 0;
while(len > 0) {
if(nums[pointer] === 0) {
nums.splice(pointer, 1);
nums.unshift(0);
} else if(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]);
const invertVowels = (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--;
} else if (!vowels.includes(newText[left])) {
left++;
} else if (!vowels.includes(newText[right])) {
right--
}
}
console.log(newText.join(""));
}
invertVowels("hola");
invertVowels("leetcode");
const sortList = (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]);
const palindrome = (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"));
const intersectList = (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]], []);
## 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.
A continuar con el curso.
```js
function isPalindromo(){
let s = "aba";
let diveS = s.split("");
let p1 = 0;
let p2 = diveS.length - 1;
console.log(p2)
while(p1 < p2){
if(s[p1] !== s[p2]){
return false;
}
p1++
p2--
}
return true
};
isPalindromo();
```
```js
let nums = [-4,-1,0,3,10];
nums = nums.map((n) => Math.pow(n,2));
```
```js
const isVowels = (n) => {
if(n === "a" || n === "e" || n === "i" || n === "o" || n === "u"){
return true;
};
return false;
};
//------------//
function reverseVowels(s){
let arr = s.split('');
let p1 = 0;
let p2 = arr.length - 1;
while(p1 < p2){
let left = arr[p1];
let right = arr[p2];
if(!isVowels(left)){
p1++;
}else if(!isVowels(right)){
p2--;
}else{
arr[p1] = right;
p1++;
arr[p2] = left;
p2--;
}
}
return arr.join('');
}
```
```js
function revertString(){
let s = ["H", "a", "n", "n", "a", "h"]
let p1 = 0;
let p2 = s.length - 1;
while(p1 < p2){
if(s[p1] <= s[p2]){
[s[p1], s[p2]] = [s[p2], s[p1]]
p1++
}
p2--
}
return s;
}
revertString()
```
`function sortColor(){`
`let nums = [1,2,0,2,1,1,0,2,0,1,2,0,1,1,0,0,2,1];`
`let red = 0;`
`let blanc = 1;`
`let blue = 2;`
`let longitud = nums.length - 1;`
`let p1 = 0;`
`let p2 = 0;`
` `
`while(p2 <= longitud){`
` if(nums[p2] === red){`
` [nums[p1], nums[p2]] = [nums[p2], nums[p1]]`
` p1++;`
` p2++;`
` }`
` if(nums[p2] === blue ){`
` [nums[p2], nums[longitud]] = [nums[longitud], nums[p2]]`
` longitud--`
` `
` }`
` if(nums[p2] === blanc ){ `
` p2++`
` `
` }`
`}`
` return nums;`
`}`
`sortColor();`
por qué cuando inserto manualmente mas numeros (1,2,3) cualquiera no respeta el orden...
```js
let nums = [0,1,0,3,12];
let p1 = 0;
let p2 = 0;
while(p2 < nums.length){
if(nums[p2] !== 0){
[nums[p1], nums[p2]] = [nums[p2], nums[p1]]
p1++
}
p2++
}
return nums;
```
**Mis soluciones en C++**
Moviendo ceros al final:
```js
// Online C++ compiler to run C++ program online
#include <iostream>
using namespace std;
int main() {
// Write C++ code here
int arreglo[]= {0,1,0,3,12};
int * p1 = & arreglo[0]; //apuntando a los numeros > 0
int * p2 = & arreglo[1];
int longitud_arr = sizeof(arreglo) / sizeof(arreglo[0]);
for (int i = 0; i < longitud_arr - 1; i++) {
while (*p2 == 0){
*p2++;
}
if (p2 > &arreglo[0] + longitud_arr - 1) break;
if (*p1 == 0) {
//cout << *p1 << * p2 << endl;
int swap = *p1;
*p1 = *p2;
*p2 = swap;
//cout << *p1 << * p2 << endl;
}
p1++;
p2++;
}
for (auto x:arreglo) {
cout << x << '\n';
}
return 0;
}
```Invertir string:
```js
#include <iostream>
#include <cstring>
using namespace std;
int main() {
char str[] = "Hola Mundo, me llamo Samuel";
int longitud = strlen(str);
// cout << str;
char * p1 = &str[0];
char * p2 = &str[longitud-1];
//cout << *(p2-1) << endl;
while (p1 < p2) {
char aux = * p1;
*p1= *p2;
*p2= aux;
p1++;
p2--;
}
cout << str << endl;
}
```Reordenar Colores
```js
#include <iostream>
using namespace std;
int main() {
int arr[] = {2,0,2,1,1,0};
// buble sort por que no se implementar quick sort xd
int len = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < len - 1; i++) {
for (int j = i; j < len; j++ ) {
if (arr[i] > arr[j]) {
int aux = arr[i];
arr[i] = arr[j];
arr[j] = aux;
}
}
}
for (auto x: arr) {
cout << x << " ";
}
}
```Invertir Vocales
```js
#include <iostream>
#include <cstring>
using namespace std;
bool esVocal(char caracter) {
caracter = tolower(caracter);
return caracter == 'a' || caracter == 'e' || caracter == 'i' || caracter == 'o' || caracter == 'u';
}
int main() {
char palabra[] = "leet code";
char * p1 = &palabra[0];
char * p2 = &palabra[strlen(palabra) - 1];
while(p1 < p2){
while (esVocal(*p1) != true) {
p1++;
}
while (esVocal(*p2) != true) {
p2--;
}
if (p1 < p2){
char aux = *p1;
*p1 = *p2;
*p2 = aux;
}
p1++;
p2--;
}
cout << palabra;
}
```Cuadrados de un arreglo ordenado
```js
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int arr[] = {-4,-1,0,3,10};
int * p1 = &arr[0]; int * p2 = &arr[sizeof(arr)/sizeof(arr[0]) - 1];
vector <int> v;
while (p1 <= p2) {
int c = pow(*p1, 2);
v.push_back(c);
p1++;
}
sort(v.begin(), v.end());
for (auto x:v) {
cout << x << " ";
}
}
```Validar palindromos
```js
#include <iostream>
#include <cstring>
using namespace std;
int main() {
char palabra[] = "abca";
char * p1 = &palabra[0];
char * p2 = &palabra[strlen(palabra) - 1];
int verdad = 2;
while (p1 < p2) {
if (*p1 != *p2) verdad--;
p1++;
p2--;
}
if (verdad > 0) cout << "Es palindromo" << endl;
else cout << "No es palindromo" << endl;
}
```Interseccion (Sol parcial con bitsets)
```js
#include <iostream>
#include <vector>
#include <utility>
#include <bitset>
#include <cmath>
using namespace std;
int main() {
vector<pair<int, int>> l1 = {{0,2},{5,10},{13,23},{24,25}};
vector<pair<int, int>> l2 = {{1,5},{8,12},{15,24},{25,26}};
//constexpr int maximo1 = l1[l1.size() - 1].second + 1;
// constexpr int maximo2 = l2[l2.size() - 1].second + 1;
// el bitset molesta mucho, usare las variables de este caso especifico
bitset<27> b1;
bitset<27> b2;
for (auto rango : l1) {
for (int i = rango.first; i <= rango.second; ++i) {
b1.set(i); // Establecer el bit en la posición i
}
}
// Iterar sobre los rangos en l2
for (auto rango : l2) {
for (int i = rango.first; i <= rango.second; ++i) {
b2.set(i); // Establecer el bit en la posición i
}
}
bitset<27> c = b1 & b2;
// falta transformarlo a rangos
cout << c;
}
```
Moviendo ceros al final:
```java
public class MoveZerosToEnd {
public static void main(String[] args) {
int[] testArray = {1,0,2,0,3,0,4,0,5,0,6,0,7,9,0,8,0};
moveZerosToEnd(testArray);
for (int j : testArray) {
System.out.println(j);
}
}
private static void moveZerosToEnd(int[] testArray) {
int posicionNoCero = 0;
for(int i = 0; i < testArray.length; i++) {
if(testArray[i] != 0) {
int temp = testArray[i];
testArray[i] = testArray[posicionNoCero];
testArray[posicionNoCero] = temp;
posicionNoCero++;
}
}
}
}
```invirtiendo String:
```java
public class InvertirString {
public static void main(String[] args) {
char[] testArray = {'h','o','l','a',' ','m','u','n','d','o'};
invertirString(testArray);
for (char j : testArray) {
System.out.print(j);
}
}
private static void invertirString(char[] testArray) {
int start = 0;
int end = testArray.length - 1;
while(start < end) {
char temp = testArray[start];
testArray[start] = testArray[end];
testArray[end] = temp;
start++;
end--;
}
}
}
```Reorganizando colores:
```java
public class ReordenarColores {
public static void main(String[] args) {
int[] colores = {2,0,1,2,1,0};
ordenarColores(colores);
for (int color : colores) {
System.out.println(color);
}
}
private static void ordenarColores(int[] colores) {
int low = 0;
int mid = 0;
int high = colores.length - 1;
int temp;
while(mid<= high) {
switch(colores[mid]) {
case 0:
temp = colores[low];
colores[low] = colores[mid];
colores[mid] = temp;
low++;
mid++;
break;
case 1:
mid++;
break;
case 2:
temp = colores[mid];
colores[mid] = colores[high];
colores[high] = temp;
high--;
break;
}
}
}
}
```Invirtiendo Vocales:
```java
public class InvertirVocales {
public static void main(String[] args) {
String testString = "Hola Mundo";
System.out.println(invertirVocales(testString));
}
private static String invertirVocales(final String testString) {
final char[] testStringArray = testString.toCharArray();
int start = 0;
int end = testStringArray.length - 1;
while(start<end){
char leftLetter = testStringArray[start];
char rightLetter = testStringArray[end];
if(!isVowel(leftLetter)) {
start++;
}
if(!isVowel(rightLetter)) {
end--;
}
if(isVowel(leftLetter) && isVowel(rightLetter)){
testStringArray[start] = rightLetter;
testStringArray[end] = leftLetter;
start++;
end--;
}
}
return new String(testStringArray);
}
private static boolean isVowel(char letter) {
String vowels = "aeiouAEIOU";
return vowels.contains(String.valueOf(letter));
}
}
```Cuadrados de un arreglo ordenado:
```js
public class CuadradosDeUnArregloOrdenado {
public static void main(String[] args) {
int[] testArray = {-4,-1,0,3,10};
int[] result = sortedSquares(testArray);
for (int j : result) {
System.out.println(j);
}
}
private static int[] sortedSquares(int[] testArray) {
int[] result = new int[testArray.length];
int left = 0;
int right = testArray.length - 1;
int index = testArray.length - 1;
while(left <= right) {
int leftSquare = testArray[left] * testArray[left];
int rightSquare = testArray[right] * testArray[right];
if(leftSquare > rightSquare) {
result[index] = leftSquare;
left++;
} else {
result[index] = rightSquare;
right--;
}
index--;
}
return result;
}
}
```
My solution using javascript. I wasn’t able to make it linear in time, I used two nested loops.
<code>var nums = [2, 0, 2, 1, 1, 0];
var left = 0;
var right = 1;
while (left < nums.length) {
right=left+1;
while (right < nums.length) {
if (nums[left] > nums[right]) {
let temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
right++;
}
left++;
}
console.log(nums);
Mi solución para invertir string en Python
<code>
s = ["h","e","l","l","o"]
long = len(s);
i = 0
while i<long//2: # T=O(n) S=O(1)
s[i],s[long-1-i] = s[long-1-i],s[i]
i+=1
print(s)
MOVE ZEROS TO THE END BY ME
import java.util.Arrays;
public class Ceros {
public static void main(String[] args){
// int[] nums= {1,3,0,8,0,9,0,0,0,1,5,2,6,3,0,0,3,0,1,5,9};
int[] nums= {1,3,0,8,0,9,0,0,0,1,5,2,6,3,0,0,3,0,1,5,9,1,2,0,0,0,3,4,5,6,7,0,1};
int p1; int zeros=0;
for(int p2 = nums.length - 1; p2>=0; p2--){
if(nums[p2]!=0){
continue;
}
for(p1 = p2; p1 < nums.length-zeros-1; p1++){
nums[p1]=nums[p1+1];
}
nums[p1]=0;
zeros ++;
// System.out.println(Arrays.toString(nums));
}
System.out.println(Arrays.toString(nums));
}
}
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.
function reverseVowels(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 vowel
if (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++;
} else if (!dictionary[string[right]]) {
// No vowel on right, decrease pointer.
right--;
}
}
return string.join("");
}
Mi aporte para el ejercicio “Invertir string”
function reverseList(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;
}
Mi aporte para el ejercicio “Mover ceros al final”:
function rearrangeList(numbers) {
let left = 0;
let right = 1;
while (right < numbers.length) {
if (numbers[left] === 0 && numbers[right] != 0) {
numbers[left] = numbers[right];
numbers[right] = 0;
left++;
right++;
} else if (numbers[left] === 0 && numbers[right] === 0) {
right++;
}
}
return numbers;
}
Mi aporte para el 2 ejemplo:
public static void InvertString(char[] text)
{
int left = 0;
int right = text.Length - 1;
while (left < right)
{
var leftVal = text[left];
var rightVal = text[right];
text[left] = rightVal;
text[right] = leftVal;
left++;
right--;
}
}
Adjunto mi posible solucion para el ejemplo 1
public static void MoveZerosFinal(int[] numbers)
{
int arrayLength = numbers.Length;
int startPointer = 0;
int endPointer = numbers.Length - 1;
while (startPointer < endPointer)
{
var currentStartPointerValue = numbers[startPointer];
var currenteEndPointerValue = numbers[endPointer];
if (currentStartPointerValue == 0 && currenteEndPointerValue != 0)
{
if (numbers[startPointer + 1] < currenteEndPointerValue)
{
var nextStartPointerValue = numbers[startPointer + 1];
numbers[startPointer] = nextStartPointerValue;
numbers[startPointer + 1] = currenteEndPointerValue;
numbers[endPointer] = currentStartPointerValue;
startPointer++;
endPointer--;
}
else
{
var previousStartPointerValue = numbers[startPointer - 1];
numbers[startPointer] = previousStartPointerValue;
numbers[startPointer - 1] = currenteEndPointerValue;
numbers[endPointer] = currentStartPointerValue;
startPointer++;
endPointer--;
}
}
else
{
startPointer++;
}
}
}
}
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?