Un poco de magia algorítmica antigua o resolver una secuencia intrigante de tareas de LeetCode

Hace algún tiempo, me encontré con una serie de tareas divertidas en el sitio web leetcode.com. Las tareas en sí no son demasiado difíciles, pero sus soluciones son bastante intrigantes. Además, problemas de este tipo suelen aparecer en entrevistas en empresas importantes y comprender los métodos para resolverlos puede resultar muy beneficioso.

La primera tarea es 136. Número único (fácil)

Dada una matriz de números enteros no vacía donde cada elemento aparece dos veces excepto uno, es necesario encontrar el elemento sin par. Resuelva el problema en una complejidad de tiempo O (n) y con memoria adicional constante.

Ejemplo 1:

Entrada: números = [1, 3, 3, 2, 6, 2, 1]

Salida: 6

Ejemplo 2:

Entrada: números = [12, 1, 1, 7, 1, 12, 1]

Salida: 7

Ejemplo 3:

Entrada: números = [6]

Salida: 6

Aprovecharemos la propiedad de la función XOR, que produce 1 solo cuando sus operandos son diferentes. Al atravesar todos los elementos de la matriz y realizar XOR bit a bit en ellos, pondremos a cero todos los valores de bits idénticos. Como resultado, lo que quedará será el resultado deseado.

Aquí hay un breve código de solución Python3:

 def single_number(nums: list) -> int: result = 0 for el in nums: result ^= el return result

Usamos solo tanta memoria adicional como la que ocupa un número entero y encontramos la solución en un solo paso a través de la matriz dada, lo que nos da una complejidad O(n). Esta es una solución concisa y elegante.

El segundo problema es 137. Número único II (dificultad media)

Dada una matriz de números enteros no vacía donde cada elemento aparece tres veces excepto uno, y solo un elemento aparece una vez, necesitamos encontrar este elemento único. Resuelva el problema en una complejidad de tiempo O (n) y con memoria adicional constante.

Ejemplo 1:

Entrada: números = [3, 1, 3, 3]

Salida: 1

Ejemplo 2:

Entrada: números = [12, 1, 1, 5, 1, 12, 12]

Salida: 5

Ejemplo 3:

Entrada: números = [6]

Salida: 6

Desafortunadamente, no podemos usar el truco anterior en este caso ya que no podemos convertir los bits emparejados en la posición requerida en ceros. Sería tentador transformar la matriz dada al formato de la tarea anterior y luego resolverla de manera similar.

Razonando de esta manera, es fácil notar que si supiéramos que ya hemos encontrado el número N dos veces (o tres) mientras atravesamos la matriz, podríamos agregar un XOR adicional con N a la suma que estamos obteniendo. Esto haría que el XOR final con este número fuera par, eliminándolo así de la suma final, y lo que queda sería nuestra respuesta.

 def single_number_ii(nums: list) -> int: mem = {} result = 0 for el in nums: if not mem.get(el, False): mem[el] = 1 else: mem[el] += 1 if mem[el] == 2: result ^= el result ^= el return result

Desafortunadamente, esta solución requeriría un máximo de (len(nums)-1)/3 en términos de memoria, lo que no puede considerarse un consumo constante, por lo que tendremos que buscar otra solución.

Intentemos cambiar nuestro enfoque.

Anteriormente, usamos XOR (que representa la suma módulo 2). Si hubiéramos implementado la suma módulo 3, podríamos haber aplicado fácilmente el truco del ejemplo anterior.

Si podemos poner un número en la respuesta la primera vez que la encontramos, ponerlo en el acumulador la segunda vez y poner a cero tanto la respuesta como el acumulador la tercera vez, nos ayudaría a resolver el problema de una sola vez. la lista con un consumo de memoria adicional exactamente igual a dos números enteros, cumpliendo con los requisitos de la tarea.

Entonces, apliquemos un poco más de magia bit a bit:

 def single_number_137_ii(nums: list) -> int: ans, acc = 0, 0 for n in nums: ans = ans ^ n & ~acc acc = acc ^ n & ~ans return ans

De esta manera, todos los números triples se ponen a cero y solo nos queda el número que aparece solo una vez.

La tercera tarea es 260. Número único III (dificultad media)

Dada una matriz de números enteros no vacía donde cada elemento aparece dos veces, excepto dos elementos que aparecen solo una vez, necesitamos encontrar estos elementos únicos. El objetivo es resolver el problema en una complejidad de tiempo O(n) y con memoria adicional constante, y el orden de los elementos únicos no importa.

Ejemplo 1:

Entrada: números = [1, 2, 1, 3, 2, 5]

Salida: [3, 5]

Ejemplo 2:

Entrada: números = [1, -2]

Salida: [-2, 1]

Obviamente, podemos eliminar fácilmente todos los números emparejados usando la operación XOR, como lo hicimos al resolver la primera tarea. La complejidad de la tarea radica entonces en identificar cualquiera de los números únicos, después de lo cual el segundo se puede calcular fácilmente aplicando XOR con nuestra suma XOR.

Para lograr esto, solo necesitamos encontrar cualquier bit diferente entre estos números únicos. Luego, volvemos a iterar a través de la matriz, realizando la suma XOR y dividiendo los resultados en dos grupos: para los números donde está establecido este bit y para aquellos donde es 0. Como resultado, obtenemos los elementos únicos deseados.

 def single_number_260(nums: list) -> int: res1, res2 = 0, 0 glob_xor = 0 for n in nums: glob_xor ^= n diff_bit = glob_xor & ~(glob_xor - 1) for n in nums: if n & diff_bit: res1 ^= n else: res2 ^= n return [res1, res2]

A pesar de tener que recorrer la matriz dos veces, la complejidad sigue siendo O(n) y el consumo de memoria es de solo 2 enteros.

NB: A pesar de que int en Python no es exactamente igual que int en otros lenguajes, consideraremos su tamaño como una constante.