¿Cuáles son algunos de tus algoritmos favoritos?

El algoritmo de búsqueda de ciclos de Floyd , también llamado “algoritmo de tortuga y liebre”. Aquí hay una implementación en C ++.

bool has_cycle(ListNode *start) { if (start == NULL) return false; ListNode *slow = start; // tortoise ListNode *fast = start; // hare while ((fast->next != NULL) && (fast->next->next != NULL)) { fast = fast->next->next; // hare jumps by 2 steps slow = slow->next; // tortoise jump by 1 step if (slow == fast) // they meet each other return true; } // they didn't meet return false; } 

También se puede encontrar el punto de inicio del ciclo fácilmente una vez que se detecta el ciclo.

Uno de mi problema favorito con este algoritmo es:

Dada una matriz de solo lectura de n + 1 enteros, cada uno en el rango de 1 a n, encuentre un entero que se repita.

Editar: Ver comentario para la respuesta.

Uno de mis favoritos es el algoritmo A * ,

En ciencias de la computación, A * (pronunciado “Una estrella”) es un algoritmo informático que se usa ampliamente en la búsqueda de rutas y el recorrido de gráficos, el proceso de trazar una ruta eficientemente transitable entre puntos, llamados nodos.

El secreto de su éxito es que combina las piezas de información que usa el algoritmo de Dijkstra (favoreciendo los vértices que están cerca del punto de partida) e información que usa Greedy Best-First-Search (favoreciendo los vértices que están cerca de la meta).

A * se usa comúnmente para el problema de búsqueda de ruta común en aplicaciones como juegos, pero originalmente se diseñó como un algoritmo de recorrido de gráfico general.

Para obtener más información sobre este algoritmo, consulte este artículo Introducción a A *

Además del hallazgo de unión mencionado por Jackson Davis, considero que la solución de Kadane para Max Subarray Sum es uno de los usos más elegantes de la programación dinámica hasta ahora.

 #impl lang: python, almost reads like a pseudo-code (: def max_subarray(A): max_so_far = max_ending_here = 0 for x in A: max_ending_here = max(0, max_ending_here + x) max_so_far = max(max_so_far, max_ending_here) return max_so_far 

Algoritmo de Maxflow. El algoritmo en sí mismo ya es muy interesante, pero lo que me parece más interesante es la gran multitud de problemas que puede resolver después de modelarlos como red de flujo y arrojar el algoritmo maxflow. Ok, tal vez el modelado me parece más hermoso que la implementación real del algoritmo, pero aún así, ¡todo es un paquete completo! = Dhttp: //en.wikipedia.org/wiki/Maximum_flow_problem

Algoritmo Rabin karp para búsqueda de subcadenas … Se supone que busca una subcadena dentro de una cadena en tiempo lineal. Me gusta por su naturaleza matemática. Idealmente es una solución basada en hashing.

Union-find, si quieres llamarlo algoritmo. Si se debe creer en wikipedia, la estructura de datos se llama en realidad estructura de datos de conjunto disjunto y el algoritmo se llama Unión de búsqueda. De cualquier manera, es increíble.

Cualquier algoritmo de envoltura de regalos me hace sentir nervioso. La simplicidad y complejidad simultáneas de los algoritmos de envoltura convexa / envoltura de regalos es simplemente alegre.

Divide y conquistaras

Xorshift y sus versiones mejoradas realmente me dejaron boquiabierto .