Introducci贸n

1

Arrays y Strings para resolver algoritmos avanzados

2

Arrays y Strings en detalle

Dos Apuntadores

3

Patr贸n de Dos Apuntadores

4

Verifying Alien Dictionary: an谩lisis del problema

5

Soluci贸n de Verifying Alien Dictionary

6

Playground: Verifying Alien Dictionary

7

Programando Verifying Alien Dictionary con JavaScript

8

Merge Two Sorted Lists: an谩lisis del problema

9

Soluci贸n de Merge Two Sorted Lists

10

Playground: Merge Two Sorted Lists

11

Programando Merge Two Sorted Lists con Python

12

Container With Most Water: an谩lisis del problema

13

Soluci贸n de Container With Most Water

14

Playground: Container with Most Water

15

Programando Container With Most Water con Java

16

Reto: Trapping Rain Water

17

Ejercicios recomendados de Dos Apuntadores

18

Ejercicios resueltos de Dos Apuntadores

Ventana Deslizante

19

Patr贸n de Ventana Deslizante

20

Longest Substring Without Repeating Characters: an谩lisis del problema

21

Soluci贸n de Longest Substring Without Repeating Characters

22

Playground: Longest Substring Without Repeating Characters

23

Programando Longest Substring Without Repeating Characters con Python

24

Ejercicios recomendados de Ventana Deslizante

25

Ejercicios resueltos de Ventana Deslizante

B煤squeda Binaria

26

Algoritmo de B煤squeda Binaria

27

Search in Rotated Arrays: an谩lisis del problema

28

Soluci贸n de Search in Rotated Arrays

29

Playground: Search in Rotated Arrays

30

Programando Search in Rotated Arrays

31

Search 2D Array Matrix: an谩lisis del problema

32

Soluci贸n de Search 2D Array Matrix

33

Playground: Search 2D Array Matrix

34

Programando Search 2D Array Matrix

Pr贸ximos pasos

35

Toma el Curso Avanzado de Algoritmos: Estructuras de Datos Lineales

Aprende Ingl茅s, Programaci贸n, AI, Ciberseguridad y mucho m谩s.

Antes: $249

Currency
$209
Suscr铆bete

Termina en:

3 D铆as
9 Hrs
43 Min
0 Seg

Ejercicios recomendados de Dos Apuntadores

17/35

Lectura

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 13

Preguntas 0

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

Ejercicios de Dos Apuntadores

馃懆鈥嶐煉 Comparto la explicaci贸n de cada ejercicio (en ingl茅s). Tambi茅n coloco el nombre y c贸digo de c贸mo aparece en Leetcode (no me deja colocar el enlace 馃槢), es 煤til escribir el c贸digo ah铆 porque tiene varios tests para cada ejercicio.
.

  1. Mover ceros al final - 283. Move Zeroes
  2. Invertir string - 344. Reverse String
  3. Reordenar colores - 75. Sort Colors
  4. Invertir vocales - 345. Reverse Vowels of a String
  5. Cuadrados de un arreglo ordenado - 977. Squares of a Sorted Array
  6. Validar pal铆ndromo (con k reemplazos) - 680. Valid Palindrome II
  7. Intersecciones de la lista de intervalos - 986. Interval List Intersections

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]], []);
**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鈥檛 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));
    }
    
}

Soluciones:

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

Mi aporte para el ejercicio 鈥淚nvertir 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 鈥淚nvertir 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 鈥淢over 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++;
            }
        }
    }
}