Eliminar Elementos Específicos de un Array
Este problema consiste en eliminar todas las ocurrencias de un valor específico dentro de un array y devolver la nueva longitud del array modificado. Los elementos restantes deben mantenerse en su posición original.
Método 1: Punteros Dobles (Iteración Directa)
Utilizamos dos punteros. El puntero i rastrea la posición donde debe colocarse el próximo elemento que no coincida con el valor a eliminar. El puntero j itera a través de todo el array. Si nums\[j\] no es el valor a eliminar, se copia a nums\[i\] y se incrementa i. Al final, i representa la nueva longitud del array.
public int eliminarValor(int[] nums, int valorAEliminar) {
int indiceInsercion = 0;
for (int indiceActual = 0; indiceActual < nums.length; indiceActual++) {
if (nums[indiceActual] != valorAEliminar) {
nums[indiceInsercion] = nums[indiceActual];
indiceInsercion++;
}
}
return indiceInsercion;
}
Método 2: Punterso Dobles (Optimización de Intercambio)
En este enfoque, left apunta al inicio y right al final (no inclusivo) del array. Mientras left sea menor que right, si nums\[left\] es el valor a eliminar, lo reemplazamos con el elemento en nums\[right-1\] y decrementamos right. Si nums\[left\] no es el valor a eliminar, incrementamos left para pasar al siguiente elemento.
public int eliminarValorOptimizado(int[] nums, int valorAEliminar) {
int left = 0;
int right = nums.length;
while (left < right) {
if (nums[left] == valorAEliminar) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
Eliminar Duplicados de un Array Ordenado
Dado un array ordenado, elimina los duplicados de forma que cada elemento aparezca solo una vez. La operación debe realizarse in-place y devolver la nueva longitud del array. Los elementos más allá de la nueva longitud no importan.
Método con Punteros Dobles
Se utilizan dos punteros: fast y slow. slow indica la posición del último elemento único encontrado. fast recorre el array. Si nums\[fast\] es diferente de nums\[slow-1\], significa que hemos encontrado un nuevo elemento único; lo copiamos a nums\[slow\] y avanzamos slow. fast siempre avanza.
public int eliminarDuplicadosOrdenados(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
int punteroLento = 1;
int punteroRapido = 1;
while (punteroRapido < nums.length) {
if (nums[punteroLento - 1] != nums[punteroRapido]) {
nums[punteroLento] = nums[punteroRapido];
punteroLento++;
}
punteroRapido++;
}
return punteroLento;
}
Comparar Cadenas con Caracteres de Borrado (Backspace)
Dadas dos cadenas s y t que pueden contener caracteres normales y '#', donde '#' simula una operación de borrado (backspace), determina si ambas cadenas resultan en la misma cadena final después de procesar todos los caracteres de borrado.
Método 1: Reconstrucción de Cadenas
Se crea una función auxiliar reBuild que procesa una cadena. Utiliza un StringBuffer para construir la cadena resultante. Si encuentra un carácter normal, lo añade. Si encuentra '#', elimina el último carácter del StringBuffer (si no está vacío). Finalmente, se comparan las cadenas reconstruidas.
public boolean compararConBackspace(String s, String t) {
return reconstruirCadena(s).equals(reconstruirCadena(t));
}
private String reconstruirCadena(String cadena) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < cadena.length(); i++) {
char c = cadena.charAt(i);
if (c != '#') {
sb.append(c);
} else if (sb.length() > 0) {
sb.deleteCharAt(sb.length() - 1);
}
}
return sb.toString();
}
Método 2: Punteros Dobles (Comparación desde el Final)
Se utilizan punteros i y j que comienzan desde el final de s y t respectivamente. bsS y bsT cuentan los caracteres de borrado pendientes. Los bucles internos avanzan los punteros saltando caracteres de borrado y los caracteres que serán borrados. Luego, se comparan los caracteres actuales si ambos punteros son válidos. Si no son iguales, las cadenas son diferentes. Si uno de los punteros llega al final antes que el otro, son diferentes.
public boolean compararConBackspace2(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
int borradosS = 0, borradosT = 0;
while (i >= 0 || j >= 0) {
// Avanzar puntero s saltando backspaces y caracteres a borrar
while (i >= 0) {
if (s.charAt(i) == '#') {
borradosS++;
i--;
} else if (borradosS > 0) {
borradosS--;
i--;
} else {
break; // Carácter válido encontrado
}
}
// Avanzar puntero t saltando backspaces y caracteres a borrar
while (j >= 0) {
if (t.charAt(j) == '#') {
borradosT++;
j--;
} else if (borradosT > 0) {
borradosT--;
j--;
} else {
break; // Carácter válido encontrado
}
}
// Comparar caracteres válidos
if (i >= 0 && j >= 0) {
if (s.charAt(i) != t.charAt(j)) {
return false;
}
} else {
// Si uno tiene caracteres restantes y el otro no, son diferentes
if (i >= 0 || j >= 0) {
return false;
}
}
// Mover punteros al siguiente carácter potencial
i--;
j--;
}
return true; // Ambas cadenas procesadas y son iguales
}
Longitud Mínima de Subarray con Suma Mayor o Igual a un Objetivo
Dado un array de enteros positivos nums y un entero target, encuentra la longitud mínima de un subarray contiguo cuya suma sea mayor o igual a target. Si no existe tal subarray, devuelve 0.
Mi Solución (Usando Sumas Prefijas y Ventana Deslizante)
Primero, precalculamos las sumas prefijas. Luego, usamos una ventana deslizante con punteros left y right. Expandimos la ventana (right++) hasta que la suma dentro de la ventana (sum\[right\] - sum\[left\]) sea mayor o igual a target. Cuando se cumple la condición, actualizamos la longitud mínima (minlen) y contraemos la ventana (left++).
public int longitudMinimaSubarray(int target, int[] nums) {
int n = nums.length;
int[] sumPrefija = new int[n + 1];
for (int i = 0; i < n; i++) {
sumPrefija[i + 1] = sumPrefija[i] + nums[i];
}
int longitudMinima = Integer.MAX_VALUE;
int left = 0;
for (int right = 1; right <= n; right++) {
while (left < right && sumPrefija[right] - sumPrefija[left] >= target) {
longitudMinima = Math.min(longitudMinima, right - left);
left++;
}
}
return longitudMinima == Integer.MAX_VALUE ? 0 : longitudMinima;
}
Solución Oficial (Ventana Deslizante Directa)
Esta solución utiliza una ventana deslizante sin precalcular sumas prefijas. start y end definen la ventana. Expandimos la ventana (end++) sumando nums\[end\]. Mientras la suma de la ventana (sum) sea mayor o igual a target, actualizamos la longitud mínima y contraemos la ventana (sum -= nums\[start\], start++).
public int longitudMinimaSubarrayOficial(int target, int[] nums) {
if (nums.length == 0) {
return 0;
}
int longitudMinima = Integer.MAX_VALUE;
int sumaVentana = 0;
int start = 0, end = 0;
while (end < nums.length) {
sumaVentana += nums[end];
while (sumaVentana >= target) {
longitudMinima = Math.min(longitudMinima, end - start + 1);
sumaVentana -= nums[start];
start++;
}
end++;
}
return longitudMinima == Integer.MAX_VALUE ? 0 : longitudMinima;
}
Subcadena Mínima que Cubre Todos los Caracteres de Otra Cadena
Dado dos cadenas s (la cadena principal) y t (la cadena de patrones), encuentra la subcadena más corta en s que contenga todos los caracteres de t, incluyendo sus duplicados. Si no existe tal subcadena, devuelve una cadena vacía.
import java.util.HashMap;
import java.util.Map;
import java.util.Iterator;
class SolucionMinimaCobertura {
Map<character integer=""> patrones = new HashMap<>();
Map<character integer=""> ventana = new HashMap<>();
public String ventanaMinima(String s, String t) {
for (char c : t.toCharArray()) {
patrones.put(c, patrones.getOrDefault(c, 0) + 1);
}
int r = 0, l = 0;
int longitudMin = Integer.MAX_VALUE;
int resL = -1, resR = -1;
while (r < s.length()) {
char charR = s.charAt(r);
if (patrones.containsKey(charR)) {
ventana.put(charR, ventana.getOrDefault(charR, 0) + 1);
}
// Comprobar si la ventana actual cumple los requisitos
while (hayCobertura() && l <= r) {
if (r - l + 1 < longitudMin) {
longitudMin = r - l + 1;
resL = l;
resR = r;
}
// Contraer la ventana desde la izquierda
char charL = s.charAt(l);
if (patrones.containsKey(charL)) {
ventana.put(charL, ventana.get(charL) - 1);
}
l++;
}
r++;
}
return resL == -1 ? "" : s.substring(resL, resR + 1);
}
// Verifica si la ventana actual contiene todos los caracteres del patrón con sus frecuencias
private boolean hayCobertura() {
for (Map.Entry<character integer=""> entry : patrones.entrySet()) {
char key = entry.getKey();
int valorRequerido = entry.getValue();
if (ventana.getOrDefault(key, 0) < valorRequerido) {
return false;
}
}
return true;
}
}
</character></character></character>
Fruta en el Recolector (Ventana Máxima)
Este problema es análogo al de la subcadena mínima que cubre, pero busca la ventana deslizante de longitud máxima que satisface una condición determinada. Por ejemplo, recolectar la máxima cantidad de frutas de dos tipos distintos.
Plantilla de Ventana Deslizante Máxima
La estrategia general es expandir la ventana (j++) y, si la condición deja de cumplirse, contraerla (i++) hasta que se cumpla de nuevo. Los resultados se actualizan después de asegurar que la ventana es válida.
# Ejemplo conceptual en Python
# j: puntero derecho, i: puntero izquierdo
# while j < len(nums):
# # Expandir ventana [i, j]
# # Comprobar si [i, j] cumple la condición
# while condition_is_not_met(i, j): # Condición para contraer
# i += 1 # Contraer ventana
# # Actualizar resultado con la ventana válida [i, j]
# j += 1
Permutación de Cadena en Otra Cadena (Ventana Fija)
Verifica si la cadena s2 contiene alguna permutación de la cadena s1 como subcadena. Se utiliza un enfoque de ventana deslizante con tamaño fijo igual a la longitud de s1.
import java.util.Arrays;
class SolucionPermutacion {
public boolean incluyePermutacion(String s1, String s2) {
int n = s1.length();
int m = s2.length();
if (n > m) {
return false;
}
int[] conteo1 = new int[26];
int[] conteo2 = new int[26];
// Inicializar la primera ventana
for (int i = 0; i < n; i++) {
conteo1[s1.charAt(i) - 'a']++;
conteo2[s2.charAt(i) - 'a']++;
}
if (Arrays.equals(conteo1, conteo2)) {
return true;
}
// Deslizar la ventana
for (int i = n; i < m; i++) {
conteo2[s2.charAt(i) - 'a']++; // Añadir nuevo carácter
conteo2[s2.charAt(i - n) - 'a']--; // Eliminar carácter antiguo
if (Arrays.equals(conteo1, conteo2)) {
return true;
}
}
return false;
}
}
Contiene Duplicados Cercanos
Dado un array de enteros nums y un entero k, determina si existen dos elementos distintos en el array que sean iguales y cuya distancia de índice sea menor o igual a k.
Método 1: Usando un HashMap
Iteramos por el array. Mantenemos un HashMap que almacena el último índice visto de cada número. Si encontramos un número que ya está en el mapa y la diferencia entre el índice actual y el índice almacenado es menor o igual a k, devolvemos true.
import java.util.HashMap;
import java.util.Map;
class SolucionDuplicadosCercanos {
public boolean contieneDuplicadosCercanos(int[] nums, int k) {
Map<integer integer=""> ultimoIndice = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (ultimoIndice.containsKey(nums[i]) && i - ultimoIndice.get(nums[i]) <= k) {
return true;
}
ultimoIndice.put(nums[i], i);
}
return false;
}
}
</integer>
Método 2: Usando un Conjunto (HashSet) y Ventana Deslizante
Mantenemos un HashSet que contiene los elementos dentro de una ventana de tamaño k. Iteramos por el array. Si i > k, eliminamos el elemento nums\[i-k-1\] del conjunto (fuera de la ventana). Si al intentar añadir nums\[i\] al conjunto este ya existe, significa que hay un duplicado dentro de la distancia k.
import java.util.HashSet;
import java.util.Set;
class SolucionDuplicadosCercanosSet {
public boolean contieneDuplicadosCercanos(int[] nums, int k) {
Set<integer> ventana = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
// Eliminar el elemento que sale de la ventana de tamaño k
if (i > k) {
ventana.remove(nums[i - k - 1]);
}
// Si el elemento ya está en la ventana, es un duplicado cercano
if (!ventana.add(nums[i])) {
return true;
}
}
return false;
}
}
</integer>
Subcadena Sin Repetir Más Larga
Encuentra la longitud de la subcadena más larga sin caracteres repetidos.
Método 1: Usando Lista y Eliminación
Iteramos por la cadena. Mantenemos una lista de caracteres de la subcadena actual. Si el carácter actual ya está en la lista, eliminamos elementos del principio de la lista hasta que se elimine la primera ocurrencia del carácter repetido. Luego añadimos el carácter actual. La longitud máxima se actualiza en cada paso.
import java.util.LinkedList;
import java.util.List;
class SolucionSubcadenaSinRepetir {
public int longitudSubcadenaSinRepetir(String s) {
if (s == null || s.length() == 0) {
return 0;
}
List<character> ventana = new LinkedList<>();
int longitudMax = 0;
for (int i = 0; i < s.length(); i++) {
char currentChar = s.charAt(i);
if (ventana.contains(currentChar)) {
int index = ventana.indexOf(currentChar);
// Eliminar elementos hasta la primera ocurrencia del duplicado
for (int j = 0; j <= index; j++) {
ventana.remove(0);
}
}
ventana.add(currentChar);
longitudMax = Math.max(longitudMax, ventana.size());
}
return longitudMax;
}
}
</character>
Método 2: Usando HashSet y Ventana Deslizante
Similar al método anterior, pero usando un HashSet para una comprobación de contains más eficiente. El puntero right expande la ventana, y i (el puntero izquierdo) se mueve cuando se encuentra un duplicado.
import java.util.HashSet;
import java.util.Set;
class SolucionSubcadenaSinRepetirSet {
public int longitudSubcadenaSinRepetir(String s) {
int n = s.length();
if (n <= 1) {
return n;
}
Set<character> ventana = new HashSet<>();
int right = 0;
int longitudMax = 0;
for (int i = 0; i < n; i++) {
// Si no es el primer elemento, eliminar el que sale de la ventana
if (i != 0) {
ventana.remove(s.charAt(i - 1));
}
// Expandir la ventana hacia la derecha mientras no haya duplicados
while (right < n && !ventana.contains(s.charAt(right))) {
ventana.add(s.charAt(right));
right++;
}
// Actualizar la longitud máxima
longitudMax = Math.max(longitudMax, right - i);
}
return longitudMax;
}
}
</character>
Encontrar Todas las Ocurrencias de Anagramas de una Cadena
Dadas dos cadenas s y p, encuentra todos los inicios de las subcadenas en s que son anagramas de p.
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
class SolucionAnagramas {
public List<integer> encontrarAnagramas(String s, String p) {
List<integer> resultados = new ArrayList<>();
int n = s.length();
int m = p.length();
if (n < m) {
return resultados;
}
int[] conteoP = new int[26];
int[] conteoS = new int[26];
// Inicializar la primera ventana y los conteos
for (int i = 0; i < m; i++) {
conteoP[p.charAt(i) - 'a']++;
conteoS[s.charAt(i) - 'a']++;
}
// Comprobar la primera ventana
if (Arrays.equals(conteoP, conteoS)) {
resultados.add(0);
}
// Deslizar la ventana
for (int i = 0; i < n - m; i++) {
conteoS[s.charAt(i) - 'a']--; // Eliminar el carácter que sale
conteoS[s.charAt(i + m) - 'a']++; // Añadir el carácter que entra
if (Arrays.equals(conteoP, conteoS)) {
resultados.add(i + 1); // Añadir el índice de inicio de la ventana
}
}
return resultados;
}
}
</integer></integer>
Reemplazo de Caracteres para la Cadena Repetitiva Más Larga
Dado una cadena s y un entero k, puedes reemplazar cualquier carácter en la cadena por otro carácter (tú eliges cuál) un número ilimitado de veces, pero solo puedes realizar k reemplazos en total. Encuentra la longitud de la subcadena más larga que contendría el mismo carácter después de realizar como máximo k reemplazos.
import java.util.HashMap;
import java.util.Map;
class SolucionReemplazo {
public int longitudReemplazoCaracter(String s, int k) {
int n = s.length();
int[] conteoCaracteres = new int[26];
int maxFrecuencia = 0;
int longitudMax = 0;
int left = 0;
for (int right = 0; right < n; right++) {
// Añadir el carácter actual a la ventana y actualizar su conteo
int indiceActual = s.charAt(right) - 'A';
conteoCaracteres[indiceActual]++;
// Actualizar la frecuencia máxima en la ventana actual
maxFrecuencia = Math.max(maxFrecuencia, conteoCaracteres[indiceActual]);
// Verificar si la ventana actual excede el tamaño permitido (maxFrecuencia + k)
// Si es así, contraer la ventana desde la izquierda
int longitudVentana = right - left + 1;
if (longitudVentana > maxFrecuencia + k) {
conteoCaracteres[s.charAt(left) - 'A']--; // Decrementar el conteo del carácter que sale
left++; // Mover el puntero izquierdo
}
// La longitud máxima es el tamaño de la ventana válida más grande encontrada
longitudMax = Math.max(longitudMax, right - left + 1);
}
return longitudMax;
}
}