Algoritmos Greedy (Voraces)
La estrategia voraz o "greedy" implica tomar la mejor decisión local en cada paso con la esperanza de que esta serie de decisiones óptimas a nivel local conduzca a una solución óptima a nivel global.
Problemas de Asignación
455. Asignar Galletas
Explicación: Para satisfacer a la mayor cantidad posible de niños, ordenamos tanto los tamaños de las galletas como los factores de codicia de los niños de menor a mayor. Luego, intentamos asignar la galleta más pequeña posible que pueda satisfacer al niño con el factor de codicia más bajo, y así sucesivamente.
class Solucion {
public:
int encontrarNiñosSatisfechos(std::vector<int>& factoresCodicia, std::vector<int>& tamañosGalletas) {
std::sort(factoresCodicia.begin(), factoresCodicia.end());
std::sort(tamañosGalletas.begin(), tamañosGalletas.end());
int indiceNiño = 0;
int indiceGalleta = 0;
int niñosSatisfechos = 0;
while (indiceNiño < factoresCodicia.size() && indiceGalleta < tamañosGalletas.size()) {
if (tamañosGalletas[indiceGalleta] >= factoresCodicia[indiceNiño]) {
niñosSatisfechos++;
indiceNiño++;
}
indiceGalleta++;
}
return niñosSatisfechos;
}
};
</int></int>
135. Repartir Caramelos
Explicación: Primero, asignamos un caramelo a cada niño. Luego, realizamos dos pasadas: una de izquierda a derecha, asegurando que si un niño tiene una calificación más alta que su vecino izquierdo, reciba al menos un caramelo más que él. Después, una pasada de derecha a izquierda, ajustando los caramelos para que si un niño tiene una calificación más alta que su vecino derecho, reciba al menos un caramelo más que él, sin disminuir la cantidad ya asignada.
class Solucion {
public:
int calcularCaramelos(std::vector<int>& calificaciones) {
int numNiños = calificaciones.size();
if (numNiños <= 1) {
return numNiños;
}
std::vector<int> caramelos(numNiños, 1);
// Primera pasada: de izquierda a derecha
for (int i = 1; i < numNiños; ++i) {
if (calificaciones[i] > calificaciones[i - 1]) {
caramelos[i] = caramelos[i - 1] + 1;
}
}
// Segunda pasada: de derecha a izquierda
for (int i = numNiños - 2; i >= 0; --i) {
if (calificaciones[i] > calificaciones[i + 1]) {
caramelos[i] = std::max(caramelos[i], caramelos[i + 1] + 1);
}
}
// Sumar todos los caramelos
long long totalCaramelos = 0;
for (int c : caramelos) {
totalCaramelos += c;
}
return static_cast<int>(totalCaramelos);
}
};
</int></int></int>
Problemas de Intervalos
435. Intervalos sin solapamiento
Explicación: Para minimizar el número de intervalos a eliminar, maximizamos el número de intervalos no superpuestos. Esto se logra ordenando los intervalos por su punto final. Luego, iteramos, seleccionando el intervalo con el punto final más pequeño que no se superponga con el intervalo previamente seleccionado.
class Solucion {
public:
int borrarIntervalosSuperpuestos(std::vector<:vector>>& intervalos) {
if (intervalos.empty()) {
return 0;
}
// Ordenar los intervalos por su punto final
std::sort(intervalos.begin(), intervalos.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
return a[1] < b[1];
});
int numEliminados = 0;
int ultimoFin = intervalos[0][1]; // El punto final del primer intervalo seleccionado
// Iterar a partir del segundo intervalo
for (size_t i = 1; i < intervalos.size(); ++i) {
if (intervalos[i][0] < ultimoFin) { // Si el inicio del intervalo actual es menor que el fin del último seleccionado
numEliminados++; // Se superpone, hay que eliminarlo
} else {
ultimoFin = intervalos[i][1]; // No se superpone, este es el nuevo intervalo a considerar
}
}
return numEliminados;
}
};
</int></int></:vector>
Ejercicios Prácticos
605. Puedes plantar flores
Explicación: Iteramos por cada parcela. Para plantar una flor en una parcela i, debe estar vacía y tanto su parcela izquierda (i-1) como su parcela derecha (i+1) también deben estar vacías. Los límites del arreglo (0 y size-1) se tratan como parcelas vacías. Si se puede plantar, incrementamos el contador de flores plantadas y marcamos la parcela como ocupada.
class Solucion {
public:
bool puedePlantarse(std::vector<int>& lechoDeFlores, int nFlores) {
int floresPlantadas = 0;
int totalParcelas = lechoDeFlores.size();
for (int i = 0; i < totalParcelas; ++i) {
// Verificar si la parcela actual está vacía
if (lechoDeFlores[i] == 0) {
// Verificar si las parcelas adyacentes están vacías o si son los límites
bool izquierdaVacia = (i == 0) || (lechoDeFlores[i - 1] == 0);
bool derechaVacia = (i == totalParcelas - 1) || (lechoDeFlores[i + 1] == 0);
if (izquierdaVacia && derechaVacia) {
lechoDeFlores[i] = 1; // Plantar flor
floresPlantadas++;
}
}
if (floresPlantadas >= nFlores) {
return true;
}
}
return floresPlantadas >= nFlores;
}
};
</int>
452. Explotar globos con flechas mínimas
Explicación: Similar al problema de "Intervalos sin solapamiento". Ordenamos los globos por su punto final (coordenada x_end). Luego, iteramos, disparando una flecha a través del punto final del primer globo. Cualquier globo que comience antes o en ese punto final puede ser reventado con la misma flecha. Si encontramos un globo que comianza después de nuestro punto de flecha actual, necesitamos una nueva flecha, y establecemos su punto de disparo en el punto final de este nuevo globo.
class Solucion {
public:
int encontrarMinimasFlechas(std::vector<:vector>>& puntos) {
if (puntos.empty()) {
return 0;
}
// Ordenar los globos por su coordenada de fin
std::sort(puntos.begin(), puntos.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
return a[1] < b[1];
});
int numeroFlechas = 1;
int puntoDisparoActual = puntos[0][1]; // La primera flecha se dispara en el fin del primer globo
for (size_t i = 1; i < puntos.size(); ++i) {
// Si el globo actual comienza después del punto de disparo actual, necesitamos una nueva flecha
if (puntos[i][0] > puntoDisparoActual) {
numeroFlechas++;
puntoDisparoActual = puntos[i][1]; // El nuevo punto de disparo es el fin de este globo
}
}
return numeroFlechas;
}
};
</int></int></:vector>
763. Partición de etiquetas
Explicación: Primero, determinamos la última aparición de cada carácter en la cadena. Luego, recorremos la cadena, manteniendo un registro del final más lejano (maxReach) que cualquier carácter dentro del segmento actual debe alcanzar. Cuando el índice actual i llega a maxReach, significa que hemos encontrado un segmento válido que puede ser particionado.
class Solucion {
public:
std::vector<int> particionarEtiquetas(const std::string& s) {
int ultimaPosicion[26]; // Almacena la última posición de cada letra 'a'-'z'
for (int i = 0; i < s.length(); ++i) {
ultimaPosicion[s[i] - 'a'] = i;
}
std::vector<int> resultadoParticiones;
int inicioSegmento = 0;
int alcanceMaximo = 0; // El índice más lejano que debe alcanzar el segmento actual
for (int i = 0; i < s.length(); ++i) {
alcanceMaximo = std::max(alcanceMaximo, ultimaPosicion[s[i] - 'a']);
// Si el índice actual 'i' ha alcanzado el alcance máximo, podemos particionar
if (i == alcanceMaximo) {
resultadoParticiones.push_back(i - inicioSegmento + 1);
inicioSegmento = i + 1; // Establecer el inicio del próximo segmento
}
}
return resultadoParticiones;
}
};
</int></int>
122. Mejor momento para comprar y vender acciones II
Explicación: Se trata de encontrar el máximo beneficio total. Dado que podemos realizar múltiples transacciones, simplemente sumamos todas las ganancias posibles. Si el precio de hoy es mayor que el de ayer, compramos ayer y vendemos hoy, obteniendo una ganancia. No hay penalización por mantener una acción de un día para otro, así que cualquier incremento de precio diario contribuye al beneficio total.
class Solucion {
public:
int maximoBeneficio(const std::vector<int>& precios) {
int beneficioTotal = 0;
for (size_t i = 1; i < precios.size(); ++i) {
// Si el precio actual es mayor que el precio del día anterior, sumamos la diferencia
beneficioTotal += std::max(0, precios[i] - precios[i - 1]);
}
return beneficioTotal;
}
};
</int>
406. Reconstruir cola por altura
Explicación: La clave es ordenar las personas de forma que el criterio de "personas delante con igual o mayor altura" sea más fácil de manejar. Ordenamos por altura descendente, y si las alturas son iguales, por el número de personas delante ascendente. Luego, insertamos cada persona en la posición k de una nueva lista. Debido al ordenamiento, cuando insertamos a una persona, todas las personas ya insertadas son más altas o tienen su misma altura, y el índice k ya considera a las personas "más altas" correctamente.
class Solucion {
public:
std::vector<:vector>> reconstruirCola(std::vector<:vector>>& personas) {
// Ordenar: primero por altura descendente, luego por k ascendente
std::sort(personas.begin(), personas.end(), [](const std::vector<int>& p1, const std::vector<int>& p2) {
if (p1[0] != p2[0]) {
return p1[0] > p2[0]; // Altura descendente
}
return p1[1] < p2[1]; // K ascendente si las alturas son iguales
});
std::vector<:vector>> colaReconstruida;
for (const auto& persona : personas) {
// Insertar cada persona en la posición indicada por su k
colaReconstruida.insert(colaReconstruida.begin() + persona[1], persona);
}
return colaReconstruida;
}
};
</:vector></int></int></:vector></:vector>
665. Secuencia no decreciente
Explicación: Recorremos la secuencia e identificamos las violaciones de la condición no decreciente (nums[i] < nums[i-1]). Si encontramos una violación, intentamos corregirla. Tenemos dos opciones: reducir nums[i-1] a nums[i] o aumentar nums[i] a nums[i-1]. La elección depende de nums[i-2]. Si nums[i] es mayor o igual que nums[i-2], podemos reducir nums[i-1]. De lo contrario, debemos aumentar nums[i]. Si encontramos más de una violación, es imposible hacer la secuencia no decreciente.
class Solucion {
public:
bool verificarPosibilidad(std::vector<int>& numeros) {
int numViolaciones = 0;
int tam = numeros.size();
for (int i = 1; i < tam; ++i) {
if (numeros[i] < numeros[i - 1]) {
numViolaciones++;
if (numViolaciones > 1) {
return false; // Más de una violación, imposible de corregir
}
// Intentar corregir la violación
// Opción 1: Reducir numeros[i-1]
if (i == 1 || numeros[i] >= numeros[i - 2]) {
numeros[i - 1] = numeros[i];
} else { // Opción 2: Aumentar numeros[i]
numeros[i] = numeros[i - 1];
}
}
}
return true; // Cero o una violación corregida
}
};
</int>
Punteros Dobles
La técnica de punteros dobles utiliza dos punteros que se mueven a través de una estructura de datos (como un arreglo o una lista enlazada) para resolver problemas de manera eficiente. Pueden moverse en la misma dirección a diferentes velocidades (punteros lentos y rápidos) o en direcciones opuestas.
Suma de Dos Números
167. Suma de Dos Números II - Entrada Array Ordenado
Explicación: Dado un arreglo ordenado, usamos dos punteros: uno al principio (izquierda) y otro al final (derecha). Sumamos los valores a los que apuntan. Si la suma es igual al objetivo, hemos encontrado los números. Si la suma es menor que el objetivo, movemos izquierda a la derecha para aumentar la suma. Si la suma es mayor, movemos derecha a la izquierda para disminuir la suma.
class Solucion {
public:
std::vector<int> sumaDos(const std::vector<int>& numeros, int objetivo) {
int punteroIzquierdo = 0;
int punteroDerecho = numeros.size() - 1;
while (punteroIzquierdo < punteroDerecho) {
int sumaActual = numeros[punteroIzquierdo] + numeros[punteroDerecho];
if (sumaActual == objetivo) {
return {punteroIzquierdo + 1, punteroDerecho + 1}; // Devolver índices basados en 1
} else if (sumaActual < objetivo) {
punteroIzquierdo++;
} else {
punteroDerecho--;
}
}
return {}; // No se encontró ninguna pareja (aunque el problema garantiza que existe)
}
};
</int></int>
Fusión de Arrays
88. Fusionar Dos Arrays Ordenados
Explicación: Para fusionar nums2 en nums1 sin usar espacio adicional y sin sobrescribir elementos de nums1 que aún no han sido procesados, comenzamos a llenar nums1 desde su final. Usamos tres punteros: uno para el final de nums1 real (idx1), otro para el final de nums2 (idx2), y uno para la posición donde se colocará el elemento fusionado (idxMerge). Comparamos los elementos en idx1 y idx2, colocando el mayor en idxMerge y moviendo el puntero correspondiente. Una vez que uno de los arreglos se agota, simplemente copiamos los elementos restantes del otro.
class Solucion {
public:
void fusionarArrays(std::vector<int>& array1, int m, std::vector<int>& array2, int n) {
int indiceArray1 = m - 1; // Puntero al último elemento válido de array1
int indiceArray2 = n - 1; // Puntero al último elemento de array2
int indiceFusion = m + n - 1; // Puntero a la última posición del array1 fusionado
// Mover elementos desde el final para evitar sobrescribir
while (indiceArray1 >= 0 && indiceArray2 >= 0) {
if (array1[indiceArray1] > array2[indiceArray2]) {
array1[indiceFusion--] = array1[indiceArray1--];
} else {
array1[indiceFusion--] = array2[indiceArray2--];
}
}
// Si quedan elementos en array2, copiarlos al principio de array1
while (indiceArray2 >= 0) {
array1[indiceFusion--] = array2[indiceArray2--];
}
}
};
</int></int>
Punteros Lento y Rápido
142. Ciclo en Lista Enlazada II
Explicación: Este problema utiliza el algoritmo de detección de ciclos de Floyd (tortuga y liebre). Un puntero lento avanza un paso a la vez, y un puntero rápido avanza dos pasos. Si se encuentran, hay un ciclo. Para encontrar el inicio del ciclo, movemos el puntero rápido de vuelta al inicio de la lista y lo hacemos avanzar un paso a la vez, al igual que el puntero lento. El punto donde se encuentran de nuevo es el inicio del ciclo.
// Definición para un nodo de lista enlazada.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solucion {
public:
ListNode *detectarCiclo(ListNode *cabeza) {
ListNode* punteroLento = cabeza;
ListNode* punteroRapido = cabeza;
// Fase 1: Detectar ciclo
while (punteroRapido != nullptr && punteroRapido->next != nullptr) {
punteroLento = punteroLento->next;
punteroRapido = punteroRapido->next->next;
if (punteroLento == punteroRapido) { // Ciclo detectado
break;
}
}
// Si no hay ciclo, punteroRapido llegará al final
if (punteroRapido == nullptr || punteroRapido->next == nullptr) {
return nullptr;
}
// Fase 2: Encontrar el nodo de inicio del ciclo
punteroRapido = cabeza; // Resetear punteroRapido al inicio
while (punteroLento != punteroRapido) {
punteroLento = punteroLento->next;
punteroRapido = punteroRapido->next;
}
return punteroRapido; // Ambos punteros se encuentran en el inicio del ciclo
}
};
Ventana Deslizante
76. Subcadena mínima de ventana
Explicación: Usamos una ventana deslizante y dos mapas de frecuencia (o arreglos de frecuencia para ASCII extendido). Uno para contar los caracteres necesarios (mapaBase) y otro para los caracteres en la ventana actual (mapaVentana). Expandimos la ventana (punteroDerecho) y actualizamos mapaVentana. Cuando la ventana contiene todos los caracteres necesarios de t, intentamos contraerla (punteroIzquierdo) para encontrar la subcadena mínima, mientras mantenemos la condición de que todos los caracteres de t estén presentes.
class Solucion {
public:
std::string ventanaMinima(const std::string& s, const std::string& t) {
int conteoCaracteresObjetivo[128] = {0}; // Frecuencia de caracteres en t
for (char c : t) {
conteoCaracteresObjetivo[c]++;
}
int conteoVentanaActual[128] = {0}; // Frecuencia de caracteres en la ventana actual
int inicioVentana = 0;
int finVentana = 0;
int caracteresCoincidentes = 0; // Número de caracteres de t que se han encontrado en la ventana
int longitudMinima = s.length() + 1;
int indiceInicioResultado = 0;
while (finVentana < s.length()) {
char caracterDerecho = s[finVentana];
conteoVentanaActual[caracterDerecho]++;
// Si el caracter actual es necesario y su conteo en la ventana no excede lo requerido, incrementamos coincidencias
if (conteoCaracteresObjetivo[caracterDerecho] > 0 && conteoVentanaActual[caracterDerecho] <= conteoCaracteresObjetivo[caracterDerecho]) {
caracteresCoincidentes++;
}
finVentana++; // Expandir la ventana hacia la derecha
// Si la ventana actual contiene todos los caracteres de t
while (caracteresCoincidentes == t.length()) {
// Actualizar la longitud mínima si esta ventana es más pequeña
if (finVentana - inicioVentana < longitudMinima) {
longitudMinima = finVentana - inicioVentana;
indiceInicioResultado = inicioVentana;
}
char caracterIzquierdo = s[inicioVentana];
conteoVentanaActual[caracterIzquierdo]--;
// Si el caracter que se remueve era esencial y su conteo en la ventana cae por debajo de lo requerido, decrementamos coincidencias
if (conteoCaracteresObjetivo[caracterIzquierdo] > 0 && conteoVentanaActual[caracterIzquierdo] < conteoCaracteresObjetivo[caracterIzquierdo]) {
caracteresCoincidentes--;
}
inicioVentana++; // Contraer la ventana desde la izquierda
}
}
return (longitudMinima > s.length()) ? "" : s.substr(indiceInicioResultado, longitudMinima);
}
};
Ejercicios Prácticos
633. Suma de cuadrados
Explicación: Utilizamos dos punteros para buscar a^2 + b^2 = c. Un puntero a comienza en 0 y b comienza en sqrt(c). Sumamos sus cuadrados. Si la suma es c, retornamos true. Si es menor, aumentamos a (para aumentar la suma). Si es mayor, disminuimos b (para disminuir la suma). Como a y b se mueven hacia el centro, garantizamos la exploración de todas las parejas posibles.
class Solucion {
public:
bool esSumaDeCuadrados(int c) {
long long a = 0;
long long b = static_cast<long long="">(std::sqrt(c)); // b inicializado al valor entero de la raíz cuadrada de c
while (a <= b) {
long long sumaCuadrados = a * a + b * b;
if (sumaCuadrados == c) {
return true;
} else if (sumaCuadrados < c) {
a++; // Necesitamos una suma mayor, aumentamos a
} else {
b--; // Necesitamos una suma menor, disminuimos b
}
}
return false;
}
};
</long>
680. Palíndromo válido II
Explicación: Empleamos dos punteros, uno al inicio y otro al final de la cadena. Si encontramos caracteres que no coinciden (s[izq] != s[der]), sabemos que podemos eliminar a lo sumo uno de ellos. Por lo tanto, intentamos dos posibilidades recursivas: 1) eliminar s[izq] y verificar si el resto es un palíndromo (izq + 1, der), o 2) eliminar s[der] y verificar si el resto es un palíndromo (izq, der - 1). Si alguna de estas es válida, la cadena original es un palíndromo válido con una eliminación.
class Solucion {
private:
// Función auxiliar para verificar si una subcadena es un palíndromo
bool verificarEsPalindromo(const std::string& str, int inicio, int fin) {
while (inicio < fin) {
if (str[inicio] != str[fin]) {
return false;
}
inicio++;
fin--;
}
return true;
}
public:
bool validarPalindromo(const std::string& s) {
int punteroIzquierdo = 0;
int punteroDerecho = s.length() - 1;
while (punteroIzquierdo < punteroDerecho) {
if (s[punteroIzquierdo] != s[punteroDerecho]) {
// Si hay una discrepancia, intentamos eliminar el caracter izquierdo o derecho
return verificarEsPalindromo(s, punteroIzquierdo + 1, punteroDerecho) ||
verificarEsPalindromo(s, punteroIzquierdo, punteroDerecho - 1);
}
punteroIzquierdo++;
punteroDerecho--;
}
return true; // La cadena ya es un palíndromo o está vacía/un solo caracter
}
};
524. Encontrar la palabra más larga en el diccionario eliminando caracteres
Explicación: Primero, ordenamos el diccionario de palabras: las palabras más largas primero, y si tienen la misma longitud, en orden lexicográfico ascendente. Luego, iteramos a través del diccionario. Para cada palabra del diccionario, usamos dos punteros para verificar si es una subcadena de la cadena s (es decir, si se puede formar eliminando caracteres de s). La primera palabra que cumpla esta condición será la respuesta debido a nuestro ordenamiento.
class Solucion {
private:
// Función auxiliar para verificar si 'sub' es una subcadena de 'principal'
bool esSubcadena(const std::string& principal, const std::string& sub) {
int i = 0, j = 0; // Punteros para principal y sub
while (i < principal.length() && j < sub.length()) {
if (principal[i] == sub[j]) {
j++; // Avanzar en la subcadena si hay coincidencia
}
i++; // Siempre avanzar en la cadena principal
}
return j == sub.length(); // Si j alcanzó el final de sub, entonces es una subcadena
}
public:
std::string encontrarPalabraMasLarga(const std::string& s, std::vector<:string>& diccionario) {
// Ordenar el diccionario:
// 1. Por longitud descendente (palabras más largas primero)
// 2. Si las longitudes son iguales, por orden lexicográfico ascendente
std::sort(diccionario.begin(), diccionario.end(), [](const std::string& a, const std::string& b) {
if (a.length() != b.length()) {
return a.length() > b.length();
}
return a < b;
});
for (const std::string& palabraDict : diccionario) {
if (esSubcadena(s, palabraDict)) {
return palabraDict; // La primera palabra que cumple es la respuesta
}
}
return ""; // No se encontró ninguna palabra
}
};
</:string>
340. Subcadena más larga con a lo sumo K caracteres distintos
Explicación: Se utiliza el patrón de ventana deslizante. Mantenemos una ventana [izq, der] y un conteo de la frecuencia de caracteres dentro de ella (conteoCaracteres). Expandimos la ventana (der). Si el número de caracteres distintos en la ventana excede K, contraemos la ventana desde izq hasta que el número de caracteres distintos sea K o menos. En cada paso, actualizamos la longitud máxima de la subcadena válida.
class Solucion {
public:
int longitudDeSubcadenaConKDistintos(const std::string& s, int k) {
if (s.empty() || k == 0) {
return 0;
}
int punteroIzquierdo = 0;
int punteroDerecho = 0;
int conteoDistintos = 0; // Número de caracteres distintos en la ventana
int frecuencias[256] = {0}; // Almacena las frecuencias de los caracteres ASCII
int longitudMaxima = 0;
while (punteroDerecho < s.length()) {
char caracterActual = s[punteroDerecho];
if (frecuencias[caracterActual] == 0) {
conteoDistintos++; // Nuevo caracter distinto
}
frecuencias[caracterActual]++;
punteroDerecho++; // Expandir la ventana
// Si el número de caracteres distintos excede k, contraer la ventana
while (conteoDistintos > k) {
char caracterAQuitar = s[punteroIzquierdo];
frecuencias[caracterAQuitar]--;
if (frecuencias[caracterAQuitar] == 0) {
conteoDistintos--; // El caracter ya no está en la ventana
}
punteroIzquierdo++; // Contraer la ventana
}
// Actualizar la longitud máxima de la subcadena válida
longitudMaxima = std::max(longitudMaxima, punteroDerecho - punteroIzquierdo);
}
return longitudMaxima;
}
};
Búsqueda Binaria
La búsqueda binaria es un algoritmo eficiente para encontrar un elemento en una lista ordenada. Funciona dividiendo repetidamente por la mitad la parte de la lista que podría contener el elemento, eliminando así la mitad de los datos restantes en cada paso.
Cálculo de Raíz Cuadrada
69. Raíz cuadrada(x)
Explicación: Realizamos una búsqueda binaria en el rango [0, x] para encontrar el número entero k tal que k*k <= x y (k+1)*(k+1) > x. Definimos un límite inferior izq y un límite superior der. En cada iteración, calculamos el punto medio med y verificamos si med*med es igual, menor o mayor que x para ajustar los límites.
class Solucion {
public:
int miSqrt(int x) {
if (x == 0) return 0;
int limiteInferior = 1;
int limiteSuperior = x; // La raíz cuadrada de x no puede ser mayor que x
int respuesta = 0;
while (limiteInferior <= limiteSuperior) {
int puntoMedio = limiteInferior + (limiteSuperior - limiteInferior) / 2;
// Usamos long long para evitar desbordamiento al calcular puntoMedio * puntoMedio
if ((long long)puntoMedio * puntoMedio <= x) {
respuesta = puntoMedio; // puntoMedio podría ser la respuesta, intentamos buscar una mayor
limiteInferior = puntoMedio + 1;
} else {
limiteSuperior = puntoMedio - 1; // puntoMedio es demasiado grande
}
}
return respuesta;
}
};
Búsqueda de Intervalos
34. Buscar rango de un elemento en un array ordenado
Explicación: Para encontrar la primera y la última posición de un elemento objetivo en un arreglo ordenado, realizamos dos búsquedas binarias separadas. Una búsqueda binaria para encontrar el límite inferior (la primera ocurrencia del objetivo) y otra para encontrar el límite superior (la última ocurrencia del objetivo). Cada búsqueda ajusta los punteros izq y der de manera ligeramente diferente para encontrar el límite preciso.
class Solucion {
private:
// Función auxiliar para encontrar el límite inferior (primera ocurrencia)
int buscarLimiteInferior(const std::vector<int>& numeros, int objetivo) {
int indice = -1;
int izq = 0, der = numeros.size() - 1;
while (izq <= der) {
int med = izq + (der - izq) / 2;
if (numeros[med] >= objetivo) {
if (numeros[med] == objetivo) {
indice = med; // Podría ser la primera ocurrencia, pero buscaremos aún más a la izquierda
}
der = med - 1;
} else {
izq = med + 1;
}
}
return indice;
}
// Función auxiliar para encontrar el límite superior (última ocurrencia)
int buscarLimiteSuperior(const std::vector<int>& numeros, int objetivo) {
int indice = -1;
int izq = 0, der = numeros.size() - 1;
while (izq <= der) {
int med = izq + (der - izq) / 2;
if (numeros[med] <= objetivo) {
if (numeros[med] == objetivo) {
indice = med; // Podría ser la última ocurrencia, pero buscaremos aún más a la derecha
}
izq = med + 1;
} else {
der = med - 1;
}
}
return indice;
}
public:
std::vector<int> buscarRango(const std::vector<int>& nums, int target) {
if (nums.empty()) {
return {-1, -1};
}
int primer = buscarLimiteInferior(nums, target);
if (primer == -1) { // Si el objetivo no se encuentra, no hay necesidad de buscar el segundo
return {-1, -1};
}
int ultimo = buscarLimiteSuperior(nums, target);
return {primer, ultimo};
}
};
</int></int></int></int>
Búsqueda en Array Rotado
81. Buscar en array rotado ordenado II
Explicación: Es una variante de la búsqueda binaria en un arreglo rotado, pero con la complicación de que puede haber duplicados. Esto puede dificultar determinar qué lado está ordenado. Si nums[med] == nums[der], no podemos saber qué lado está ordenado, así que simplemente reducimos der en uno para eliminar ese duplicado y continuar la búsqueda. De lo contrario, procedemos como en la búsqueda binaria en un arreglo rotado sin duplicados, comparando el objetivo con los extremos y el medio para decidir qué mitad contiene el objetivo.
class Solucion {
public:
bool buscarEnRotadoConDuplicados(const std::vector<int>& numeros, int objetivo) {
int izq = 0, der = numeros.size() - 1;
while (izq <= der) {
int med = izq + (der - izq) / 2;
if (numeros[med] == objetivo) {
return true;
}
// Manejar duplicados: si nums[med] == nums[izq] y nums[med] == nums[der]
// No podemos saber qué lado está ordenado, simplemente reducimos los punteros
if (numeros[izq] == numeros[med] && numeros[med] == numeros[der]) {
izq++;
der--;
} else if (numeros[izq] <= numeros[med]) { // El lado izquierdo está ordenado
if (objetivo >= numeros[izq] && objetivo < numeros[med]) {
der = med - 1;
} else {
izq = med + 1;
}
} else { // El lado derecho está ordenado
if (objetivo > numeros[med] && objetivo <= numeros[der]) {
izq = med + 1;
} else {
der = med - 1;
}
}
}
return false;
}
};
</int>
Ejercicios Prácticos
154. Encontrar el mínimo en array rotado ordenado II
Explicación: Similar al problema 81, la presencia de duplicados añade un caso especial. Si nums[med] == nums[der], no podemos determinar el lado ordenado. En este caso, simplemente podemos descartar nums[der] y mover der a la izquierda, ya que nums[der] es un duplicado y no puede ser el mínimo único si nums[med] también tiene el mismo valor (o nums[l] si nums[l] == nums[med] == nums[r]). Si nums[med] > nums[der], el mínimo está en el lado derecho. Si nums[med] < nums[der], el mínimo está en el lado izquierdo (incluyendo med).
class Solucion {
public:
int encontrarMinimoEnRotadoConDuplicados(const std::vector<int>& numeros) {
int punteroIzquierdo = 0;
int punteroDerecho = numeros.size() - 1;
while (punteroIzquierdo < punteroDerecho) {
int puntoMedio = punteroIzquierdo + (punteroDerecho - punteroIzquierdo) / 2;
if (numeros[puntoMedio] > numeros[punteroDerecho]) {
// El mínimo está en el lado derecho (medio a derecho)
punteroIzquierdo = puntoMedio + 1;
} else if (numeros[puntoMedio] < numeros[punteroDerecho]) {
// El mínimo está en el lado izquierdo (izquierdo a medio)
punteroDerecho = puntoMedio;
} else { // numeros[puntoMedio] == numeros[punteroDerecho]
// No podemos saber qué lado contiene el mínimo. Descartamos el punteroDerecho.
// Esto es seguro porque numeros[punteroDerecho] no puede ser el mínimo único
// si es igual a numeros[puntoMedio].
punteroDerecho--;
}
}
return numeros[punteroIzquierdo]; // Cuando punteroIzquierdo == punteroDerecho, hemos encontrado el mínimo
}
};
</int>
540. Elemento único en array ordenado
Explicación: Se utiliza búsqueda binaria, aprovechando la propiedad de que los elementos duplicados siempre aparecen en parejas, y el elemento único romperá este patrón. Si el índice medio med es par, su par esperado está en med+1. Si med es impar, su par esperado está en med-1. Si nums[med] coincide con su par esperado, el elemento único debe estar a la derecha. De lo contrario, está a la izquierda (incluido med).
class Solucion {
public:
int elementoUnico(const std::vector<int>& numeros) {
int izq = 0;
int der = numeros.size() - 1;
while (izq < der) {
int med = izq + (der - izq) / 2;
// Asegurarse de que 'med' sea un índice par.
// Si 'med' es impar, lo movemos a la izquierda para que sea el inicio de una pareja.
if (med % 2 == 1) {
med--;
}
// Comprobar si los elementos en med y med+1 forman un par
if (numeros[med] == numeros[med + 1]) {
// Si coinciden, el elemento único debe estar a la derecha de este par.
izq = med + 2;
} else {
// Si no coinciden, el elemento único debe estar en med o a su izquierda.
der = med;
}
}
return numeros[izq]; // izq (o der) apuntará al elemento único.
}
};
</int>
4. Mediana de dos arrays ordenados
Explicación: Este es un problema avanzado que se resuelve con una búsqueda binaria en uno de los arrays para encontrar la partición correcta. El objetivo es dividir ambos arrays en dos partes (izquierda y derecha) de tal manera que todos los elementos en izquierda sean menores o iguales que todos los elementos en derecha, y las longitudes de las partes sean correctas para formar la mediana. La búsqueda binaria se realiza sobre el índice de corte en el array más pequeño.
class Solucion {
public:
double encontrarMedianaDeDosArraysOrdenados(const std::vector<int>& nums1, const std::vector<int>& nums2) {
// Asegurarse de que nums1 es el array más corto para optimizar la búsqueda binaria
if (nums1.size() > nums2.size()) {
return encontrarMedianaDeDosArraysOrdenados(nums2, nums1);
}
int m = nums1.size();
int n = nums2.size();
int izq = 0, der = m; // Rango para la partición en nums1
// halfLen es la longitud de la parte izquierda de la mediana combinada
int halfLen = (m + n + 1) / 2;
while (izq <= der) {
int i = izq + (der - izq) / 2; // Partición en nums1
int j = halfLen - i; // Partición en nums2
// Ajustar particiones si son inválidas
if (i < m && nums2[j-1] > nums1[i]) {
// i es demasiado pequeño, necesitamos moverlo a la derecha
izq = i + 1;
} else if (i > 0 && nums1[i-1] > nums2[j]) {
// i es demasiado grande, necesitamos moverlo a la izquierda
der = i - 1;
} else { // Particiones correctas
// Determinar el valor máximo de la mitad izquierda
int maxIzquierda;
if (i == 0) { maxIzquierda = nums2[j-1]; }
else if (j == 0) { maxIzquierda = nums1[i-1]; }
else { maxIzquierda = std::max(nums1[i-1], nums2[j-1]); }
// Si la longitud total es impar, maxIzquierda es la mediana
if ((m + n) % 2 == 1) {
return maxIzquierda;
}
// Determinar el valor mínimo de la mitad derecha
int minDerecha;
if (i == m) { minDerecha = nums2[j]; }
else if (j == n) { minDerecha = nums1[i]; }
else { minDerecha = std::min(nums1[i], nums2[j]); }
// Si la longitud total es par, la mediana es el promedio de maxIzquierda y minDerecha
return (maxIzquierda + minDerecha) / 2.0;
}
}
return 0.0; // No debería alcanzarse si los arrays son válidos
}
};
</int></int>
Ordenamiento
Selección Rápida (Quickselect)
215. K-ésimo elemento más grande en un array
Explicación: Este problema se puede resolver eficientemente usando el algoritmo Quickselect, que es una variante del Quicksort. La función std::nth_element en C++ implementa este algoritmo. Reorganiza los elementos de un rango de manera que el elemento en la posición n-ésima (que correspondería al k-ésimo más grande) sea el que estaría allí si el rango estuviera ordenado. Todos los elementos antes de él son menores o iguales, y todos los elementos después son mayores o iguales.
class Solucion {
public:
int encontrarKthMasGrande(std::vector<int>& numeros, int k) {
// La función nth_element coloca el elemento que estaría en la posición
// (numeros.size() - k) si el array estuviera ordenado.
// Después de la llamada, este elemento es el k-ésimo más grande.
std::nth_element(numeros.begin(), numeros.begin() + numeros.size() - k, numeros.end());
// Retornar el elemento en la posición calculada
return numeros[numeros.size() - k];
}
};
</int>
Ordenamiento por Cubetas (Bucket Sort)
347. K elementos más frecuentes
Explicación: Utilizamos un mapa para contar la frecuencia de cada número. Luego, para agrupar los números por su frecuencia, empleamos una técnica similar al ordenamiento por cubetas. Creamos un arreglo de vectores (cubetas), donde el índice de cada vector representa una frecuencia y el vector contiene los números que aparecen con esa frecuencia. Finalmente, iteramos desde la frecuencia más alta hasta la más baja, agregando números al resultado hasta que hayamos recolectado k elementos.
class Solucion {
public:
std::vector<int> topKMasFrecuentes(const std::vector<int>& numeros, int k) {
// 1. Contar la frecuencia de cada número
std::unordered_map<int int=""> mapaFrecuencias;
int maximaFrecuencia = 0;
for (int num : numeros) {
mapaFrecuencias[num]++;
maximaFrecuencia = std::max(maximaFrecuencia, mapaFrecuencias[num]);
}
// 2. Usar un array de "cubetas" donde el índice es la frecuencia
// y el valor es una lista de números con esa frecuencia
std::vector<:vector>> cubetas(maximaFrecuencia + 1);
for (const auto& par : mapaFrecuencias) {
cubetas[par.second].push_back(par.first);
}
// 3. Recolectar los k elementos más frecuentes, empezando por las frecuencias más altas
std::vector<int> resultado;
for (int freq = maximaFrecuencia; freq >= 0 && resultado.size() < k; --freq) {
if (!cubetas[freq].empty()) {
for (int num : cubetas[freq]) {
resultado.push_back(num);
if (resultado.size() == k) {
return resultado;
}
}
}
}
return resultado;
}
};
</int></:vector></int></int></int>
Ejercicios Prácticos
451. Ordenar caracteres por frecuencia
Explicación: Similar al problema de los "K elementos más frecuentes". Primero, contamos la frecuencia de cada carácter en la cadena. Luego, usamos un arreglo de cubetas, donde cada índice de cubeta representa una frecuencia, y los caracteres con esa frecuencia se almacenan en el vector correspondiente. Finalmente, construimos la cadena resultante iterando desde las cubetas de mayor frecuencia a menor, añadiendo cada carácter su número de veces correspondiente a la cadena.
class Solucion {
public:
std::string ordenarPorFrecuencia(const std::string& s) {
// 1. Contar la frecuencia de cada carácter
std::unordered_map<char int=""> frecuenciasCaracteres;
int frecuenciaMaxima = 0;
for (char c : s) {
frecuenciasCaracteres[c]++;
frecuenciaMaxima = std::max(frecuenciaMaxima, frecuenciasCaracteres[c]);
}
// 2. Usar un array de "cubetas" para agrupar caracteres por su frecuencia
std::vector<:vector>> cubetas(frecuenciaMaxima + 1);
for (const auto& par : frecuenciasCaracteres) {
cubetas[par.second].push_back(par.first);
}
// 3. Construir la cadena resultante
std::string cadenaOrdenada = "";
for (int freq = frecuenciaMaxima; freq >= 0; --freq) {
if (!cubetas[freq].empty()) {
// Los caracteres dentro de una misma cubeta pueden estar en cualquier orden
for (char c : cubetas[freq]) {
for (int i = 0; i < freq; ++i) {
cadenaOrdenada += c;
}
}
}
}
return cadenaOrdenada;
}
};
</:vector></char>
75. Clasificar colores
Explicación: Este es el problema de la Bandera Holandesa de Dijkstra. Utilizamos tres punteros: low para los 0s, high para los 2s, y current para iterar. Si nums[current] es 0, lo intercambiamos con nums[low] y movemos low y current. Si nums[current] es 2, lo intercambiamos con nums[high] y movemos high (pero no current, ya que el elemento recién intercambiado podría ser un 0 o un 1 que debe procesarse). Si es 1, simplemente avanzamos current.
class Solucion {
public:
void clasificarColores(std::vector<int>& numeros) {
int punteroBajo = 0; // Apunta al siguiente 0 (o al primer no-0)
int punteroAlto = numeros.size() - 1; // Apunta al siguiente 2 (o al último no-2)
int punteroActual = 0; // Puntero de iteración
while (punteroActual <= punteroAlto) {
if (numeros[punteroActual] == 0) {
std::swap(numeros[punteroActual], numeros[punteroBajo]);
punteroBajo++;
punteroActual++;
} else if (numeros[punteroActual] == 2) {
std::swap(numeros[punteroActual], numeros[punteroAlto]);
punteroAlto--;
// NO incrementamos punteroActual aquí, ya que el elemento intercambiado
// desde punteroAlto podría ser un 0 o un 1 y debe ser revisado.
} else { // numeros[punteroActual] == 1
punteroActual++;
}
}
}
};
</int>
Búsqueda
Búsqueda en Profundidad (DFS)
695. Área máxima de isla
Explicación: Recorremos la cuadrícula. Cuando encontramos un 1 (parte de una isla) que no ha sido visitado, iniciamos una DFS desde ese punto. La DFS explora recursivamente todos los 1s conectados, marcándolos como visitados (por ejemplo, cambiándolos a 2) y contando el área de la isla. Después de cada DFS, actualizamos el área máxima encontrada.
class Solucion {
private:
int filas, columnas;
// Direcciones para moverse (arriba, abajo, izquierda, derecha)
const std::vector<int> dx = {-1, 1, 0, 0};
const std::vector<int> dy = {0, 0, -1, 1};
// Función DFS para explorar y contar el área de la isla
int explorarIsla(int r, int c, std::vector<:vector>>& cuadrilla) {
// Condiciones de borde: fuera de la cuadrícula o no es tierra (0 o ya visitado 2)
if (r < 0 || r >= filas || c < 0 || c >= columnas || cuadrilla[r][c] != 1) {
return 0;
}
cuadrilla[r][c] = 2; // Marcar como visitado
int areaActual = 1; // Contar la parcela actual
// Explorar vecinos
for (int i = 0; i < 4; ++i) {
areaActual += explorarIsla(r + dx[i], c + dy[i], cuadrilla);
}
return areaActual;
}
public:
int areaMaximaDeIsla(std::vector<:vector>>& cuadrilla) {
if (cuadrilla.empty() || cuadrilla[0].empty()) {
return 0;
}
filas = cuadrilla.size();
columnas = cuadrilla[0].size();
int maximoArea = 0;
for (int i = 0; i < filas; ++i) {
for (int j = 0; j < columnas; ++j) {
if (cuadrilla[i][j] == 1) { // Encontrar una nueva isla no visitada
maximoArea = std::max(maximoArea, explorarIsla(i, j, cuadrilla));
}
}
}
return maximoArea;
}
};
</:vector></:vector></int></int>
547. Número de provincias
Explicación: Este problema es equivalente a encontrar el número de componentes conectados en un grafo, donde las ciudades son nodos y las conexiones son aristas. Podemos usar DFS para recorrer el grafo. Iteramos sobre cada ciudad; si una ciudad no ha sido visitada (es decir, no forma parte de una provincia ya contada), incrementamos el contador de provincias y lanzamos una DFS desde esa ciudad para visitar todas las ciudades conectadas a ella, marcándolas como visitadas.
class Solucion {
private:
// Función DFS para visitar todas las ciudades conectadas a 'ciudadActual'
void visitarCiudadesConectadas(int ciudadActual, std::vector<:vector>>& matrizAdyacencia, std::vector<bool>& visitado) {
visitado[ciudadActual] = true;
for (int vecino = 0; vecino < matrizAdyacencia.size(); ++vecino) {
// Si hay una conexión y el vecino no ha sido visitado
if (matrizAdyacencia[ciudadActual][vecino] == 1 && !visitado[vecino]) {
visitarCiudadesConectadas(vecino, matrizAdyacencia, visitado);
}
}
}
public:
int encontrarNumeroDeProvincias(std::vector<:vector>>& estaConectado) {
if (estaConectado.empty()) {
return 0;
}
int numCiudades = estaConectado.size();
std::vector<bool> ciudadesVisitadas(numCiudades, false);
int totalProvincias = 0;
for (int i = 0; i < numCiudades; ++i) {
if (!ciudadesVisitadas[i]) { // Si la ciudad no ha sido visitada, es el inicio de una nueva provincia
totalProvincias++;
visitarCiudadesConectadas(i, estaConectado, ciudadesVisitadas);
}
}
return totalProvincias;
}
};
</bool></:vector></bool></:vector>
417. Problema de flujo de agua del Pacífico Atlántico
Explicación: En lugar de simular el flujo de agua desde el interior hacia los océanos, podemos invertir el problema y simular el "flujo inverso" desde los océanos hacia el interior. Realizamos dos DFS separadas: una desde todas las celdas adyacentes al Pacífico y otra desde todas las celdas adyacentes al Atlántico. Cada DFS marca las celdas que pueden alcanzar ese océano. Las celdas que son alcanzables tanto por el Pacífico como por el Atlántico son nuestra respuesta. El agua "fluye" hacia arriba, por lo que en el flujo inverso, solo podemos movernos a celdas con una altura igual o mayor.
class Solucion {
private:
int numFilas, numColumnas;
std::vector<:vector>> alcanzablePacifico; // Celdas que pueden alcanzar el Pacífico
std::vector<:vector>> alcanzableAtlantico; // Celdas que pueden alcanzar el Atlántico
std::vector<:vector>> resultado; // Almacena las celdas que cumplen ambas condiciones
// Direcciones para DFS: arriba, abajo, izquierda, derecha
const std::vector<int> dr = {-1, 1, 0, 0};
const std::vector<int> dc = {0, 0, -1, 1};
void dfsInverso(int r, int c, std::vector<:vector>>& alturas, std::vector<:vector>>& matrizAlcanzable) {
if (matrizAlcanzable[r][c] == 1) { // Ya visitado y marcado como alcanzable
return;
}
matrizAlcanzable[r][c] = 1; // Marcar como alcanzable
// Si esta celda es alcanzable por ambos océanos, añadir al resultado
if (alcanzablePacifico[r][c] == 1 && alcanzableAtlantico[r][c] == 1) {
resultado.push_back({r, c});
}
// Explorar vecinos
for (int i = 0; i < 4; ++i) {
int nuevaFila = r + dr[i];
int nuevaColumna = c + dc[i];
// Validar límites y condición de altura (el agua "fluye" a una celda mayor o igual)
if (nuevaFila >= 0 && nuevaFila < numFilas && nuevaColumna >= 0 && nuevaColumna < numColumnas &&
alturas[nuevaFila][nuevaColumna] >= alturas[r][c]) {
dfsInverso(nuevaFila, nuevaColumna, alturas, matrizAlcanzable);
}
}
}
public:
std::vector<:vector>> pacificoAtlantico(std::vector<:vector>>& alturas) {
if (alturas.empty() || alturas[0].empty()) {
return {};
}
numFilas = alturas.size();
numColumnas = alturas[0].size();
alcanzablePacifico = std::vector<:vector>>(numFilas, std::vector<int>(numColumnas, 0));
alcanzableAtlantico = std::vector<:vector>>(numFilas, std::vector<int>(numColumnas, 0));
// Iniciar DFS desde las fronteras del Pacífico (fila 0 y columna 0)
for (int r = 0; r < numFilas; ++r) {
dfsInverso(r, 0, alturas, alcanzablePacifico);
}
for (int c = 0; c < numColumnas; ++c) {
dfsInverso(0, c, alturas, alcanzablePacifico);
}
// Iniciar DFS desde las fronteras del Atlántico (última fila y última columna)
for (int r = 0; r < numFilas; ++r) {
dfsInverso(r, numColumnas - 1, alturas, alcanzableAtlantico);
}
for (int c = 0; c < numColumnas; ++c) {
dfsInverso(numFilas - 1, c, alturas, alcanzableAtlantico);
}
return resultado; // El resultado se acumula en dfsInverso
}
};
</int></:vector></int></:vector></:vector></:vector></:vector></:vector></int></int></:vector></:vector></:vector>
Backtracking (Vuelta Atrás)
46. Permutaciones
Explicación: El backtracking se usa para generar todas las permutaciones. En cada paso, elegimos un número no utilizado de los restantes y lo añadimos a nuestra permutación parcial. Luego, recursivamente llamamos a la función para llenar la siguiente posición. Una vez que la permutación está completa (su tamaño es igual al tamaño del arreglo original), la agregamos a nuestro resultado. Después de cada llamada recursiva, "deshacemos" la elección (backtrack) para probar otras posibilidades.
class Solucion {
private:
std::vector<:vector>> todasLasPermutaciones;
void generarPermutaciones(std::vector<int>& numeros, int indiceInicio) {
// Caso base: si hemos llegado al final del array, hemos formado una permutación completa
if (indiceInicio == numeros.size() - 1) {
todasLasPermutaciones.push_back(numeros);
return;
}
// Para cada posición, intercambiar el elemento actual con todos los elementos siguientes
for (int i = indiceInicio; i < numeros.size(); ++i) {
std::swap(numeros[indiceInicio], numeros[i]); // Elegir: colocar numeros[i] en la posición indiceInicio
generarPermutaciones(numeros, indiceInicio + 1); // Explorar
std::swap(numeros[indiceInicio], numeros[i]); // Deshacer: restaurar el array para otras permutaciones
}
}
public:
std::vector<:vector>> permutar(std::vector<int>& nums) {
generarPermutaciones(nums, 0);
return todasLasPermutaciones;
}
};
</int></:vector></int></:vector>
77. Combinaciones
Explicación: Para generar todas las combinaciones de k números a partir de n números, también usamos backtracking. En cada paso recursivo, intentamos añadir un número a nuestra combinación parcial. Solo podemos añadir números que sean mayores que el último número añadido para evitar duplicados y mantener el orden. Cuando la combinación parcial tiene k números, la agregamos al resultado. Luego, "deshacemos" la adición (backtrack) para probar otras opciones.
class Solucion {
private:
std::vector<:vector>> todasLasCombinaciones;
// Función de backtracking para generar combinaciones
void buscarCombinaciones(int inicio, int nTotal, int kObjetivo, std::vector<int>& caminoActual) {
// Caso base: si hemos encontrado k elementos para la combinación
if (caminoActual.size() == kObjetivo) {
todasLasCombinaciones.push_back(caminoActual);
return;
}
// Iterar desde 'inicio' hasta 'nTotal'
for (int i = inicio; i <= nTotal; ++i) {
caminoActual.push_back(i); // Elegir: añadir 'i' a la combinación actual
buscarCombinaciones(i + 1, nTotal, kObjetivo, caminoActual); // Explorar recursivamente
caminoActual.pop_back(); // Deshacer: quitar 'i' para probar otras opciones
}
}
public:
std::vector<:vector>> combinar(int n, int k) {
std::vector<int> combinacionParcial;
buscarCombinaciones(1, n, k, combinacionParcial);
return todasLasCombinaciones;
}
};
</int></:vector></int></:vector>
79. Búsqueda de palabra
Explicación: Usamos DFS con backtracking para buscar la palabra. Desde cada celda de la cuadrícula, intentamos hacer coincidir el primer carácter de la palabra. Si coincide, marcamos la celda como visitada (modificando temporalmente su valor, por ejemplo, a un carácter especial) y recursivamente buscamos el siguiente carácter en las celdas adyacentes. Si la búsqueda es exitosa, retornamos true. Si no lo es, o si todas las rutas desde esa celda fallan, "desmarcamos" la celda (restauramos su valor original) y hacemos backtracking.
class Solucion {
private:
int numFilas, numColumnas;
// Direcciones para moverse: arriba, abajo, izquierda, derecha
const std::vector<int> dr = {-1, 1, 0, 0};
const std::vector<int> dc = {0, 0, -1, 1};
// Función DFS para buscar la palabra
bool dfsBuscar(std::vector<:vector>>& tablero, const std::string& palabra, int fila, int col, int indicePalabra) {
// Caso base: si hemos encontrado todos los caracteres de la palabra
if (indicePalabra == palabra.length()) {
return true;
}
// Condiciones de borde: fuera de los límites o el carácter no coincide
if (fila < 0 || fila >= numFilas || col < 0 || col >= numColumnas || tablero[fila][col] != palabra[indicePalabra]) {
return false;
}
char caracterOriginal = tablero[fila][col]; // Guardar el caracter original
tablero[fila][col] = '#'; // Marcar como visitado temporalmente
// Explorar vecinos
for (int i = 0; i < 4; ++i) {
if (dfsBuscar(tablero, palabra, fila + dr[i], col + dc[i], indicePalabra + 1)) {
tablero[fila][col] = caracterOriginal; // Deshacer (backtrack) antes de retornar
return true;
}
}
tablero[fila][col] = caracterOriginal; // Deshacer (backtrack) si no se encontró la palabra
return false;
}
public:
bool existe(std::vector<:vector>>& tablero, const std::string& palabra) {
numFilas = tablero.size();
numColumnas = tablero[0].size();
for (int i = 0; i < numFilas; ++i) {
for (int j = 0; j < numColumnas; ++j) {
if (dfsBuscar(tablero, palabra, i, j, 0)) {
return true;
}
}
}
return false;
}
};
</:vector></:vector></int></int>
51. Problema de las N Reinas
Explicación: Este clásico problema de backtracking busca todas las configuraciones posibles de N reinas en un tablero N x N de modo que ninguna reina se ataque entre sí. Utilizamos arreglos booleanos para realizar un seguimiento de las columnas ocupadas, las diagonales principales (fila - columna) y las diagonales secundarias (fila + columna). La función recursiva intenta colocar una reina en cada fila; si se encuentra una posición segura, se marca y se llama recursivamente para la siguiente fila. Si no se puede colocar una reina, se hace backtracking y se prueba otra posición.
class Solucion {
public:
std::vector<:vector>> resolverNReinas(int n) {
std::vector<:vector>> soluciones;
std::vector<:string> tablero(n, std::string(n, '.')); // Tablero actual
// Vectores para rastrear posiciones atacadas
std::vector<bool> columnaOcupada(n, false);
std::vector<bool> diagonalPrincipalOcupada(2 * n - 1, false); // fila - columna + n - 1 para mapear a índice positivo
std::vector<bool> diagonalSecundariaOcupada(2 * n - 1, false); // fila + columna
// Función lambda recursiva para el backtracking
std::function<void> colocarReina = [&](int filaActual) {
// Caso base: Si todas las reinas han sido colocadas
if (filaActual == n) {
soluciones.push_back(tablero);
return;
}
// Probar cada columna en la fila actual
for (int colActual = 0; colActual < n; ++colActual) {
// Calcular índices de diagonales
int idxDiagPrincipal = filaActual - colActual + n - 1;
int idxDiagSecundaria = filaActual + colActual;
// Verificar si la posición es segura
if (!columnaOcupada[colActual] &&
!diagonalPrincipalOcupada[idxDiagPrincipal] &&
!diagonalSecundariaOcupada[idxDiagSecundaria]) {
// Colocar reina
tablero[filaActual][colActual] = 'Q';
columnaOcupada[colActual] = true;
diagonalPrincipalOcupada[idxDiagPrincipal] = true;
diagonalSecundariaOcupada[idxDiagSecundaria] = true;
// Explorar la siguiente fila
colocarReina(filaActual + 1);
// Deshacer (backtrack)
tablero[filaActual][colActual] = '.';
columnaOcupada[colActual] = false;
diagonalPrincipalOcupada[idxDiagPrincipal] = false;
diagonalSecundariaOcupada[idxDiagSecundaria] = false;
}
}
};
colocarReina(0); // Iniciar el proceso desde la primera fila
return soluciones;
}
};
</void></bool></bool></bool></:string></:vector></:vector>
Búsqueda en Amplitud (BFS)
934. Puente más corto
Explicación: Este problema se resuelve en dos fases: Primero, usamos DFS para encontrar y marcar una de las dos islas. Durante la DFS, todas las celdas de la primera isla se marcan (por ejemplo, con 2) y se añaden a una cola para la BFS. Segundo, usamos BFS desde todas las celdas de la primera isla para expandirnos capa por capa. El nivel en el que encontramos una celda de la segunda isla (1) representa la longitud del puente más corto. Cada nivel de la BFS incrementa la distancia del puente.
class Solucion {
public:
// Direcciones para moverse (arriba, abajo, izquierda, derecha)
const std::vector<int> dr = {-1, 1, 0, 0};
const std::vector<int> dc = {0, 0, -1, 1};
int puenteMasCorto(std::vector<:vector>>& cuadrilla) {
int n = cuadrilla.size();
std::queue<:pair int="">> colaBFS; // Cola para la fase BFS
// Función DFS para encontrar la primera isla y llenarla en la cola BFS
// Usamos una lambda para capturar colaBFS y n
std::function<void int=""> dfsIdentificarIsla =
[&](int r, int c) {
if (r < 0 || r >= n || c < 0 || c >= n || cuadrilla[r][c] != 1) {
return; // Fuera de límites o no es parte de la isla (0 o ya marcado como 2)
}
cuadrilla[r][c] = 2; // Marcar como parte de la primera isla
colaBFS.push({r, c}); // Añadir a la cola para la BFS de expansión
// Explorar vecinos
for (int k = 0; k < 4; ++k) {
dfsIdentificarIsla(r + dr[k], c + dc[k]);
}
};
// Fase 1: Encontrar la primera isla usando DFS
bool islaEncontrada = false;
for (int i = 0; i < n && !islaEncontrada; ++i) {
for (int j = 0; j < n && !islaEncontrada; ++j) {
if (cuadrilla[i][j] == 1) {
dfsIdentificarIsla(i, j);
islaEncontrada = true; // Solo necesitamos identificar una isla
}
}
}
// Fase 2: Expandir desde la primera isla usando BFS para encontrar la segunda
int distanciaPuente = 0;
while (!colaBFS.empty()) {
int nivelActualTamaño = colaBFS.size();
for (int h = 0; h < nivelActualTamaño; ++h) {
std::pair<int int=""> celdaActual = colaBFS.front();
colaBFS.pop();
int r = celdaActual.first;
int c = celdaActual.second;
// Explorar vecinos
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
// Validar límites
if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
if (cuadrilla[nr][nc] == 1) {
return distanciaPuente; // Encontramos la segunda isla, esta es la distancia
}
if (cuadrilla[nr][nc] == 0) {
cuadrilla[nr][nc] = 2; // Marcar como visitado (parte de la expansión)
colaBFS.push({nr, nc});
}
}
}
}
distanciaPuente++; // Incrementamos la distancia después de explorar todo un nivel
}
return -1; // No se debería alcanzar si siempre hay dos islas
}
};
</int></void></:pair></:vector></int></int>