Programación

Vamos a resolver ejercicios de programación que aparecen en algunos sitios web. Son problemas que son complicados a propósito, que hacen foco en alguna habilidad específica, como manejo de arrays, strings, o cómo plantear un algoritmo para resolver un problema que requiere muchos pasos.

Problema 1

Te dan dos listas simplemente enlazadas que representan dos números enteros positivos. Los dígitos están almacenados en orden inverso, y cada uno de los nodos contiene solamente un dígito. Sumar ambos números y devolver como una lista simplemente enlazada.

Se puede asumir que los dos números no contienen ningún cero adelante, salvo el número 0 en sí.

Ejemplo:


Entrada: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Salida: 7 -> 0 -> 8
Explicación: 342 + 465 = 807.

Como ayuda extra, nos dan la definición de “nodo de lista”, el cual es en sí una lista que tenemos que recorrer de adelante para atrás.


/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/

El tema con las listas, es que puede ser un número de longitud arbitraria. No tengo que contar con la posibilidad de armar números enteros con un determinado tipo de datos con el contenido de las listas, porque una lista suficientemente grande se iría del tamaño que permite ese tipo de datos. Así que tengo que sumar dígito a dígito y listo, como hacíamos en la escuela.

Acá se hace útil el hecho de que el dígito menos significativo es el primero tanto en los argumentos como en el resultado. Eso hace que el algoritmo sea relativamente simple.

Acarreo=0.
Mientras alguno de los dos números tenga dígitos:
*Si tengo un dígito en el primer argumento, tomarlo.
*Si tengo un dígito en el segundo argumento, tomarlo.
*Sumar los dos dígitos: si da más de 10, tengo un dígito de acarreo.
*Anotar el dígito del resultado en la lista.

*Si al final hay un acarreo, crear un nuevo nodo con él.

En java sería:

package ar.com.strellis.problemas;

public class AddNumbers 
{
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) 
	{
		ListNode pointer1=l1;
		ListNode pointer2=l2;
		ListNode resultado=null;
		ListNode pointerResultado=null;
		int acarreo=0;
		// Mientras alguno de los dos números tenga dígitos,
		while(pointer1!=null || pointer2!=null)
		{
			int valor1=0;
			int valor2=0;
			// Si tengo un dígito en el primer argumento, tomarlo.
			if(pointer1!=null)
				valor1=pointer1.val;
			// Si tengo un dígito en el segundo argumento, tomarlo.
			if(pointer2!=null)
				valor2=pointer2.val;
			// Calculo la suma y el acarreo.
			int resultado1=(valor1+valor2+acarreo)%10;
			acarreo=(valor1+valor2+acarreo)/10;
			// Me guardo el resultado.
			ListNode digitoResultado=new ListNode(resultado1);
			digitoResultado.next=null;
			if(resultado==null) // estoy en el primer nodo
			{
				resultado=digitoResultado;
				pointerResultado=digitoResultado;
			}
			else
			{
				pointerResultado.next=digitoResultado;
				pointerResultado=pointerResultado.next;
			}
			if(pointer1!=null)
				pointer1=pointer1.next;
			if(pointer2!=null)
				pointer2=pointer2.next;
		}
		// Si hay un acarreo, crear un nuevo nodo con él.
		if(acarreo>0)
		{
			ListNode digitoResultado=new ListNode(acarreo);
			digitoResultado.next=null;
			pointerResultado.next=digitoResultado;
		}
		return resultado;
	}
}

Problema 2

Hay una gran pila de medias y hay que armar pares por color. Dado un array de enteros que representan el color de cada media, determinar cuántos pares de medias con igual color hay.

Por ejemplo hay n=7 medias, de colores ar=[1,2,1,2,1,3,2]. Hay un par de color 1 y un par de color 2. Quedan 3 medias sueltas, una de cada color. El número de pares es 2.

Se puede asumir que habrá una cantidad de medias entre 1 y 100, y que el número de color estará entre 0 y 100.

Planteo. Para esto, podemos ir guardando las cantidades que encontramos en una HashTable cuyo índice es el número de color y el valor es la cantidad de medias de ese color encontradas. No hace falta guardar exactamente qué par fue encontrado, solamente hace falta grabar que si de un color hay 2, me quedo con que hay 1 par, y voy sumando en contadores.

Por cada item leído:
*Buscar en la tabla si ya lo tengo. Si es así, incrementar la cantidad.
*Si esa cantidad es 2, contar un par y volver el número a cero.
*Si el color no existía, agregarlo.

En java sería:

package ar.com.strellis.problemas;

import java.util.Hashtable;

public class SockMerchant {
	// Complete the sockMerchant function below.
	public int sockMerchant(int n, int[] ar) 
	{
		Hashtable<Integer,Integer> colores=new Hashtable<Integer,Integer>();
		int cantidad_pares=0;
		for(int i=0;i<n;i++)
		{
			// Busco el color en la tabla.
			if(colores.containsKey(ar[i]))
			{
				int cantActual=colores.get(ar[i]);
				cantActual++;
				if(cantActual==2)
				{
					cantidad_pares++;
					colores.put(ar[i], 0);
				}
				else
				{
					colores.put(ar[i], cantActual);
				}
			}
			else
				colores.put(ar[i],1);
		}
		return cantidad_pares;
	}

}

Problema 3

Gary es un escalador. Registra cuidadosamente sus recorridos, prestándole atención a la topografía. Durante su último recorrido, dio n pasos, por cada paso que dio, registró que si era en subida, era U, y si era en bajada, D. El recorrido de Gary empieza y termina al nivel del mar, y cada paso en subida o en bajada representa un cambio de altura de 1 metro. Definimos estos términos:

  • Una montaña es una secuencia de pasos consecutivos sobre el nivel del mar, que comienzan con una subida por encima del nivel del mar y terminan con un paso en bajada hacia el nivel del mar.
  • Un valle es una secuencia de pasos consecutivos por debajo del nivel del mar, que comienzan con una bajada por debajo del nivel del mar, y terminan con una subida hacia el nivel del mar.

Dada la secuencia de pasos de Gary, hallar el número de VALLES que atravesó. Por ejemplo, si el camino de Gary es B=[DDUUUUDD], primero entra en un valle de 2 metros de profundidad, luego trepa a una montaña de 2 metros de altura. Finalmente, regresa al nivel del mar.

Se debe asumir que la cantidad de pasos estará entre 1 y un MILLÓN!!!!. Tener cuidado con el rango de los enteros.

Planteo. Asumimos que el nivel del mar es cero, y tenemos que contar los pasos. Al recibir una D, restamos. Si bajamos por debajo del nivel del mar, hay que contar un valle al subir. Si subimos por encima del nivel del mar, no hay que contar nada. O sea que si al hacer el paso bajé del nivel del mar, tengo que considerar que estoy en un valle, y me mantengo así hasta que llego al nivel del mar, en ese momento cuento el valle.

Acá va la solución en java:

package ar.com.strellis.problemas;

public class Hiker 
{
	public int countingValleys(int n, String s) 
	{
		int valles=0;
		int nivelDelMar=0;
		int nivelActual=0;
		boolean enValle=false;
		// Empezamos recortando de a un caracter la String que me mandan.
		for(int i=0;i<s.length();i++)
		{
			char c=s.charAt(i);
			if(c=='D')
				nivelActual--;
			if(c=='U')
				nivelActual++;
			// Ya tenemos el nivel. Comparamos con el nivel del mar.
			if(nivelActual<nivelDelMar)
			{
				// Entré en un valle.
				enValle=true;
			}
			// Si estaba en un valle y ahora estoy al nivel del mar,
			if(enValle && nivelActual==nivelDelMar)
			{
				enValle=false;
				valles++;
			}
		}
		return valles;
	}
}

Problema 4

Emma juega a un nuevo juego que comienza con nubes que tienen números consecutivos. Algunas nubes son de tormenta y otras no. Ella puede saltar a cualquier nube normal cuyo número sea igual al de la nube actual más 1 o 2. Tiene que evitar las de tormenta. Determinar el número mínimo de saltos que Emma tiene que hacer para partir de la primera nube hasta la última. Siempre es posible ganar el juego.

Para cada juego, Emma va a recibir un array de nubes numeradas 0 si son seguras y 1 si hay que evitarlas. Por ejemplo, c=[0,1,0,0,0,1,0] indexadas de 0 a 6. El número de cada nube es su índice, así que tiene que evitar aquellas de índice 1 y 5. Puede seguir los caminos 0->2->4->6, o 0->2->3->4->6. El primer camino es de 3 saltos mientras que el segundo es de 4.

Restricciones: el número de nubes está entre 2 y 100, y la primera y última nube siempre son seguras.

Planteo. Me parece que aquí nos viene bien el “Backtracking”, donde en un un array paralelo voy a ir llevando la distancia que recorrí hasta esa nube. O sea: para todas las nubes a las que puedo saltar, si no tengo una distancia recorrida, la anoto. Si llego a una nube por la que ya pasé, y tengo un camino de menor cantidad de nubes recorrido, reemplazo esa distancia por la que llevo, y la anoto como la mínima. Si el camino que voy llevando es mayor al de la cantidad anotada en la nube, retrocedo, no vale la pena continuar.

Dicho así, parece confuso pero veamos con un algoritmo. Como de mi nube puedo saltar a la nube+1 o nube+2, no hay muchos caminos posibles.

Saltar:
* Si llegué a la última nube, y el camino que recorrí es menor al mínimo, lo anoto.
* Si no es la última,
** me fijo si puedo ir a la nube n+1. Si puedo, me fijo si esa nube tiene un valor anotado que es mayor al que voy llevando. Si es mayor, sumo 1 a la cantidad de nubes, anoto el nuevo valor y salto.
** me fijo si puedo ir a la nube n+2. Si puedo, hago lo mismo que antes.

Me garantizan que siempre hay un camino, ya que siempre puedo ganar. O sea que no tengo que considerar ningún caso raro. Ya habrán notado que esta función es recursiva!!

Veamos una implementación en java.

package ar.com.strellis.problemas;

public class JumpingOnClouds 
{
	private int[] distancias;
	private int[] nubes;
	private int valorMinimo;
	public int jumpingOnClouds(int[] c) 
	{
		valorMinimo=Integer.MAX_VALUE;
		int distanciaActual=0;
		// Genero el array de distancias.
		distancias=new int[c.length];
		nubes=c;
		int nubeActual=0;
		saltarRecursivo(nubeActual,distanciaActual);
		return valorMinimo;
	}
	private void saltarRecursivo(int nubeActual,int distanciaActual)
	{
		// Si no estoy en la última nube, tengo que probar si puedo saltar.
		if(nubeActual!=nubes.length-1)
		{
			if(nubeActual+1<nubes.length && nubes[nubeActual+1]==0
					&& (
							distancias[nubeActual+1]==0 
							||
							distancias[nubeActual+1]!=0 && distanciaActual+1<distancias[nubeActual+1]
						) 
					) // Si puedo ir a la nube +1,
			{
				// Si la próxima nube tiene un valor anotado mayor al que voy llevando,
				// Anoto la distancia.
				distancias[nubeActual+1]=distanciaActual+1;
				// Realizo el salto.
				saltarRecursivo(nubeActual+1,distanciaActual+1);
			}
			if(nubeActual+2<nubes.length && nubes[nubeActual+2]==0
					&& (
							distancias[nubeActual+2]==0
							||
							distancias[nubeActual+2]!=0 && distanciaActual+1<distancias[nubeActual+2]
						) 
					) // Si puedo ir a la nube +2,
			{
				// Hago lo mismo que antes.
				distancias[nubeActual+2]=distanciaActual+1;
				// Realizo el salto.
				saltarRecursivo(nubeActual+2,distanciaActual+1);
			}
		}
		else
		{
			// Llegué a la última nube.
			if(distanciaActual<valorMinimo)
				valorMinimo=distanciaActual;
		}
	}
}

Problema 5

Mark y Jane están muy felices luego de tener su primer hijo. A su hijo le encantan los juguetes, así que Mark quiere comprar algunos. Tiene a disposición muchos juguetes con sus precios, pero tiene una cierta cantidad para gastar, y quiere maximizar el número de juguetes con su plata.

Dada una lista de precios y un monto para gastar, cuál es la máxima cantidad de juguetes que Mark puede comprar? Por ejemplo, si Mark tiene 7 para gastar, y los precios de los items son [1,2,3,4], Mark puede comprar los items 1,2,3 por 6 o 3,4 por 7. Pero elegiría el primer grupo.

Planteo. Acá se habla de maximizar el número de juguetes, no me impone ninguna otra restricción. Así que simplemente compraría los items desde el más barato hasta el más caro, hasta que se me acabe la plata. Para eso tengo que ordenar el array, sumar los precios, y contar los items.

* Ordenar el array.
* Mientras tenga items y me sobre plata:
** Contar un item y sumar su precio.
** Si me quedé sin plata, me detengo.

Notaron que la ciencia de este algoritmo está en la parte de ordenar, no es cierto????? En ningún lado me dicen que no puedo aprovecharme del lenguaje para eso, así que simplemente hago que Java haga el esfuerzo: “Arrays.sort(prices)”. No es genial?!?!?!!?!?

Solución en java:

package ar.com.strellis.problemas;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class MarkAndToys 
{
	public int maximumToys(int[] prices, int k) 
	{
		// En ningún lado dice que no me puedo aprovechar del lenguaje, y
		// el Java ya sabe cómo ordenar el array, así que voy a intentar hacer eso.
		
		Arrays.sort(prices);
		// Ahora sumo todos los elementos más bajos hasta que se alcance el monto k.
		long suma=0;
		int cantidadItems=0;
		boolean fin=false;
		int i=0;
		while(i<prices.length && !fin)
		{
			// Sumo lo que cuesta, y si supera la suma al presupuesto, me detengo.
			// Si no, cuento el item.
			Integer integer=prices[i];
			suma+=integer;
			if(suma>k)
				fin=true;
			else
				cantidadItems++;
		}
		return cantidadItems;
	}
}

Problema 6

Con un array de ceros y una lista de operaciones, para cada operación sumar un valor a cada elemento entre los dos índices dados, inclusive. Una vez que hayan sido hechas todas las operaciones, devolver el máximo valor del Array. Por ejemplo, si la longitud del Array de ceros es n=10, la lista de operaciones es como sigue:


a b k
1 5 3
4 8 7
6 9 1

Sumar los valores de k entre a y b inclusive:


index-> 1 2 3 4 5 6 7 8 9 10
[0,0,0, 0, 0,0,0,0,0, 0]
[3,3,3, 3, 3,0,0,0,0, 0]
[3,3,3,10,10,7,7,7,0, 0]
[3,3,3,10,10,8,8,8,1, 0]

El valor máximo es 10

Planteo. Problema retorcido, si los hay. Se me ocurrió que este sería un uso genial para las Streams: puedo tomar el array, y ponerlo dentro de un Stream. A ese Stream le puedo aplicar filtros!!! y obtener los elementos de él que vaya necesitando.

Por ejemplo, digamos que pongo todas las operaciones en un Stream. Al Stream lo puedo filtrar para obtener los valores que necesito. Podría usar alguna clase de Map, pero usar un Stream se hace más ágil.

En el primer filtro, pedimos las operaciones que son mayores al comienzo del intervalo donde hay que sumar, y con otro filtro, las operaciones que son menores al final del intervalo.

Acá va el código:

package ar.com.strellis.problemas;

import java.util.Arrays;
import java.util.stream.IntStream;

public class ArrayManipulation 
{
	public long arrayManipulation(int n, int[][] queries) 
	{
		long maximo;
		// Entre los indices a, b de un array de n ceros,
		// hay que sumar valores
		// El array queries tiene el siguiente formato:
		// n[0][0] es el primer indice.
		// n[0][1] es el segundo indice.
		// n[0][2] es el numero a sumar.
		
		long[] resultados=new long[n];
		IntStream.rangeClosed(1, n).forEach(a->{
			resultados[a-1]=Arrays.stream(queries).filter(o->o[0]<=a).filter(o->o[1]>=a).mapToLong(o->o[2]).sum();
		});
		// Ahora busco el máximo dentro del array de resultados!!!
		maximo=Arrays.stream(resultados).parallel().max().orElse(0);
		return maximo;
	}
}

Be the first to comment

Leave a Reply

Your email address will not be published.


*