- Casa Robada III (Programación Dinámica en Árbol)
En este problema, se utiliza programación dinámica en un árbol para calcular la máxima cantidad que se puede robar sin robar nodos adyacentes. La solución implica un recorrido DFS que devuelve dos valores: el máximo sin robar el nodo actual y el máximo robándolo.
class ArbolDP {
public int calcularRobo(TreeNode raiz) {
int[] ganancias = dfsRecursivo(raiz);
return Math.max(ganancias[0], ganancias[1]);
}
private int[] dfsRecursivo(TreeNode nodo) {
if (nodo == null) return new int[]{0, 0};
int[] izq = dfsRecursivo(nodo.left);
int[] der = dfsRecursivo(nodo.right);
int sinRobar = Math.max(izq[0], izq[1]) + Math.max(der[0], der[1]);
int conRobar = nodo.val + izq[0] + der[0];
return new int[]{sinRobar, conRobar};
}
}
- Casa Robada IV (Búsqueda Binaria + Programación Dinámica)
Se aplica búsqueda binaria para determinar la capacidad mínima necesaria para robar al menos k casas, validando con programación dinámica si es factible robar esa cantidad con un límite dado.
class CapacidadMinima {
public int minCapacidad(int[] nums, int k) {
if (nums.length == 1) return nums[0];
int inferior = Integer.MAX_VALUE, superior = Integer.MIN_VALUE;
for (int valor : nums) {
inferior = Math.min(inferior, valor);
superior = Math.max(superior, valor);
}
while (inferior < superior) {
int medio = inferior + (superior - inferior) / 2;
if (contarRobos(nums, medio) >= k) superior = medio;
else inferior = medio + 1;
}
return inferior;
}
private int contarRobos(int[] nums, int limite) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0] <= limite ? 1 : 0;
dp[1] = Math.max(dp[0], nums[1] <= limite ? 1 : 0);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + (nums[i] <= limite ? 1 : 0));
}
return dp[n - 1];
}
}
LCP 06. Tomar Monedas (Simulación Greedy)
Un problema sencillo que requiere sumar la mitad superior de cada cantidad de monedas, usando aritmética básica para calcular el mínimo de movimientos.
class Monedas {
public int minMovimientos(int[] monedas) {
int total = 0;
for (int cantidad : monedas) total += (cantidad + 1) / 2;
return total;
}
}
- Recoger Monedas en un Árbol (Ordenamiento Topológico)
Se emplea ordenamiento topológico para eliminar hojas sin monedas y luego capas externas, reduciendo el árbol a sus componentes esenciales. El resultado se calcula como el doble del número de aristas restantes.
class ColeccionMonedas {
public int recogerMonedas(int[] monedas, int[][] aristas) {
int n = monedas.length;
List<integer>[] grafo = new ArrayList[n];
Arrays.setAll(grafo, i -> new ArrayList<>());
int[] grado = new int[n];
for (int[] arista : aristas) {
int u = arista[0], v = arista[1];
grafo[u].add(v);
grafo[v].add(u);
grado[u]++;
grado[v]++;
}
int aristasRestantes = n - 1;
Queue<integer> cola = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (grado[i] == 1 && monedas[i] == 0) cola.offer(i);
}
while (!cola.isEmpty()) {
aristasRestantes--;
for (int vecino : grafo[cola.poll()]) {
if (--grado[vecino] == 1 && monedas[vecino] == 0) cola.offer(vecino);
}
}
for (int i = 0; i < n; i++) {
if (grado[i] == 1 && monedas[i] == 1) cola.offer(i);
}
aristasRestantes -= cola.size();
for (int nodo : cola) {
for (int vecino : grafo[nodo]) {
if (--grado[vecino] == 1) aristasRestantes--;
}
}
return Math.max(aristasRestantes * 2, 0);
}
}
</integer></integer>
- Distribuir Dinero a Máximo Niños (Clasificación por Casos)
Se resuelve mediante clasificación de casos para asignar dinero a los niños, maximizando la cantidad que recibe 8 dólares mientras se respetan las restricciones de distribución.
class DistribucionDinero {
public int maxNiñosConOcho(int dinero, int niños) {
if (dinero < niños) return -1;
dinero -= niños;
int maxOcho = Math.min(dinero / 7, niños);
int restante = dinero - maxOcho * 7;
if ((maxOcho == niños - 1 && restante == 3) || (maxOcho == niños && restante > 0)) return maxOcho - 1;
return maxOcho;
}
}
- Operaciones en un Árbol (Diseño de Estructura de Datos)
Se diseña una estructura de datos para manejar bloqueos, desbloqueos y actualizaciones en un árbol, utiliznado listas de adyacencia para rastrear hijos y operaciones recursivas para verificar ancestros y descendientes.
class ArbolBloqueable {
int[] padres;
int[] usuarioBloqueado;
List<integer>[] hijos;
public ArbolBloqueable(int[] padres) {
int n = padres.length;
this.padres = padres;
usuarioBloqueado = new int[n];
Arrays.fill(usuarioBloqueado, -1);
hijos = new List[n];
Arrays.setAll(hijos, i -> new ArrayList<>());
for (int i = 0; i < n; i++) {
if (padres[i] != -1) hijos[padres[i]].add(i);
}
}
public boolean bloquear(int nodo, int usuario) {
if (usuarioBloqueado[nodo] == -1) {
usuarioBloqueado[nodo] = usuario;
return true;
}
return false;
}
public boolean desbloquear(int nodo, int usuario) {
if (usuarioBloqueado[nodo] == usuario) {
usuarioBloqueado[nodo] = -1;
return true;
}
return false;
}
public boolean actualizar(int nodo, int usuario) {
boolean condicion = usuarioBloqueado[nodo] == -1 && !tieneAncestroBloqueado(nodo) && verificarDescendientes(nodo);
if (condicion) usuarioBloqueado[nodo] = usuario;
return condicion;
}
private boolean tieneAncestroBloqueado(int nodo) {
int actual = padres[nodo];
while (actual != -1) {
if (usuarioBloqueado[actual] != -1) return true;
actual = padres[actual];
}
return false;
}
private boolean verificarDescendientes(int nodo) {
boolean hayBloqueado = usuarioBloqueado[nodo] != -1;
usuarioBloqueado[nodo] = -1;
for (int hijo : hijos[nodo]) {
hayBloqueado |= verificarDescendientes(hijo);
}
return hayBloqueado;
}
}
</integer>
- Caché LRU (Implementación con Tabla Hash y Lista Doblemente Enlazada)
Se implementa una caché LRU utilizando una tabla hash para acceso rápido y una lista doblemente enlazada para mantener el orden de uso, donde el nodo más reciente está en la cabeza y el menos usado en la cola.
class CachéLRU {
class NodoDoble {
int clave;
int valor;
NodoDoble anterior;
NodoDoble siguiente;
public NodoDoble() {}
public NodoDoble(int clave, int valor) {
this.clave = clave;
this.valor = valor;
}
}
Map<Integer, NodoDoble> mapa = new HashMap<>();
int tamaño = 0;
int capacidad;
NodoDoble cabeza = new NodoDoble(), cola = new NodoDoble();
public CachéLRU(int capacidad) {
this.capacidad = capacidad;
cabeza.siguiente = cola;
cola.anterior = cabeza;
}
public int obtener(int clave) {
NodoDoble nodo = mapa.get(clave);
if (nodo == null) return -1;
moverACabeza(nodo);
return nodo.valor;
}
public void insertar(int clave, int valor) {
NodoDoble nodo = mapa.get(clave);
if (nodo == null) {
NodoDoble nuevoNodo = new NodoDoble(clave, valor);
mapa.put(clave, nuevoNodo);
agregarACabeza(nuevoNodo);
tamaño++;
if (tamaño > capacidad) {
NodoDoble ultimo = eliminarCola();
mapa.remove(ultimo.clave);
tamaño--;
}
} else {
nodo.valor = valor;
moverACabeza(nodo);
}
}
private void agregarACabeza(NodoDoble nodo) {
nodo.anterior = cabeza;
nodo.siguiente = cabeza.siguiente;
cabeza.siguiente.anterior = nodo;
cabeza.siguiente = nodo;
}
private void eliminarNodo(NodoDoble nodo) {
nodo.anterior.siguiente = nodo.siguiente;
nodo.siguiente.anterior = nodo.anterior;
}
private void moverACabeza(NodoDoble nodo) {
eliminarNodo(nodo);
agregarACabeza(nodo);
}
private NodoDoble eliminarCola() {
NodoDoble nodo = cola.anterior;
eliminarNodo(nodo);
return nodo;
}
}
- Caché LRU (Implementación con LinkedHashMap)
Alternativamente, se puede extender LinkedHashMap para implementar una caché LRU, sobrescribiendo el método para eliminar la entrada más antigua cuando se excede la capacidad.
class CachéLRU extends LinkedHashMap<Integer, Integer> {
private int capacidad;
public CachéLRU(int capacidad) {
super(capacidad, 0.75F, true);
this.capacidad = capacidad;
}
public int obtener(int clave) {
return super.getOrDefault(clave, -1);
}
public void insertar(int clave, int valor) {
super.put(clave, valor);
}
@Override
protected boolean eliminarEntradaAntigua(Map.Entry<Integer, Integer> entrada) {
return size() > capacidad;
}
}