一些有意思的算法代码
jopen 12年前
<p> Keith Schwarz 是一个斯坦福大学计算机科学系的硕士研究生。他对编程充满了热情。他的主页上他自己正在实现各种各样的有意思的算法和数据结构，<a href="/misc/goto?guid=4958201805834039645">http://www.keithschwarz.com/interesting/</a>， 目前这个网页上有88个（见下面的列表），但这位大哥要干135个，你可以看看他的 <a href="/misc/goto?guid=4958201805834039645" target="_blank">To-Do List</a>。</p> <p> 从这个列表上，我们可以看到，他从去年7月份就在自己实现这些东西了，我把他实现的这些算法转过来，</p> <ul> <li>一方面我们可以学习一下这些算法和代码，因为很多东西对我来说都比较新，我以前<a href="/misc/goto?guid=4958201807272412903" target="_blank">列举过一些经典的算法</a>，<a title="链接：算法和数据结构词典" href="/misc/goto?guid=4958201808013483705" rel="bookmark">算法和数据结构词典</a>，还有<a title="链接：可视化的数据结构和算法" href="/misc/goto?guid=4958201808759563659" rel="bookmark">可视化的数据结构和算法</a>， 不过感觉都没有这个全。</li> </ul> <ul> <li>另一方面我希望这个事可以影响到一些正在学习编程的人。看看别人是怎么学习编程的，希望对你有借鉴作用。</li> </ul> <table style="width:100%;" class="ke-zeroborder" border="0" cellspacing="0" cellpadding="6"> <thead> <tr> <td>Name</td> <td>Link</td> <td>Date Added</td> <td>Language</td> <td>Description</td> </tr> </thead> <tbody> <tr> <td>Binomial Heap</td> <td><a href="/misc/goto?guid=4958201809495235185">(link)</a></td> <td>7‑24‑2010</td> <td>C++</td> <td>An implementation of a <a href="/misc/goto?guid=4958201810236864644">binomial heap</a> data structure for use as a priority queue.</td> </tr> <tr> <td>Bounded Priority Queue</td> <td><a href="/misc/goto?guid=4958201810975074073">(link)</a></td> <td>7‑24‑2010</td> <td>C++</td> <td>An implementation of a <a href="/misc/goto?guid=4958201811718581969">priority queue</a> with a fixed upper limit to its size..</td> </tr> <tr> <td>Matrix</td> <td><a href="/misc/goto?guid=4958201812457322513">(link)</a></td> <td>7‑24‑2010</td> <td>C++</td> <td>A collection of classes for manipulating <a href="/misc/goto?guid=4958201813206105936">matrices</a>.</td> </tr> <tr> <td>VList</td> <td><a href="/misc/goto?guid=4958201813952388160">(link)</a></td> <td>8‑16‑2010</td> <td>Java</td> <td>An implementation of the <tt>List</tt> abstraction backed by a <a href="/misc/goto?guid=4958201814688643461">VList</a>.</td> </tr> <tr> <td>Function Wrapper</td> <td><a href="/misc/goto?guid=4958201815428514782">(link)</a></td> <td>8‑16‑2010</td> <td>C++</td> <td>A C++ wrapper class around unary functions.</td> </tr> <tr> <td>String</td> <td><a href="/misc/goto?guid=4958201816157528488">(link)</a></td> <td>8‑17‑2010</td> <td>C++</td> <td>An implementation of a <a href="/misc/goto?guid=4958201816896020110">string</a> abstraction that uses the small string optimization.</td> </tr> </tbody> </table> <p>——————————</p> <table class="ke-zeroborder"> <tbody> <tr> <td>nstream</td> <td><a href="/misc/goto?guid=4958201817631260948">(link)</a></td> <td>8‑31‑2010</td> <td>C++</td> <td>An stream class that sends and receives data over a network.</td> </tr> <tr> <td>Snake</td> <td><a href="/misc/goto?guid=4958201818379272697">(link)</a></td> <td>8‑31‑2010</td> <td>C++</td> <td>An implementation of the game <a href="/misc/goto?guid=4958201819120844751"><em>Snake</em></a> with a rudimentary AI.</td> </tr> <tr> <td>Mergesort</td> <td><a href="/misc/goto?guid=4958201819868812841">(link)</a></td> <td>9‑14‑2010</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201820603877824">mergesort</a> algorithm.</td> </tr> <tr> <td>Next Permutation</td> <td><a href="/misc/goto?guid=4958201821342023074">(link)</a></td> <td>10‑6‑2010</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201822088048009"><tt>next_permutation</tt></a> STL algorithm.</td> </tr> <tr> <td>Interval Heap</td> <td><a href="/misc/goto?guid=4958201822822131887">(link)</a></td> <td>10‑17‑2010</td> <td>Java</td> <td>An implementation of a <a href="/misc/goto?guid=4958201823554320996">double-ended priority queue</a> using an <a href="/misc/goto?guid=4958201824301089506">interval heap</a>.</td> </tr> <tr> <td>Linear-Time Selection</td> <td><a href="/misc/goto?guid=4958201825040638072">(link)</a></td> <td>10‑18‑2010</td> <td>C++</td> <td>A deterministic, linear-time <a href="/misc/goto?guid=4958201825781684938">selection algorithm</a> using the <a href="/misc/goto?guid=4958201826525307879">median-of-medians</a> algorithm.</td> </tr> <tr> <td>Heapsort</td> <td><a href="/misc/goto?guid=4958201827259704567">(link)</a></td> <td>10‑18‑2010</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201828003973491">heapsort</a> algorithm.</td> </tr> <tr> <td>Union-Find</td> <td><a href="/misc/goto?guid=4958201828938392399">(link)</a></td> <td>10‑19‑2010</td> <td>Java</td> <td>An implementation of a <a href="/misc/goto?guid=4958201829692554795">disjoint-set data structure</a> using a disjoint set forest.</td> </tr> <tr> <td>Radix Sort</td> <td><a href="/misc/goto?guid=4958201830436552287">(link)</a></td> <td>10‑19‑2010</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201831186579934">radix sort</a> algorithm.</td> </tr> <tr> <td>Rational</td> <td><a href="/misc/goto?guid=4958201831926313743">(link)</a></td> <td>10‑23‑2010</td> <td>C++</td> <td>A data structure representing a <a href="/misc/goto?guid=4958201832654823132">rational number</a>.</td> </tr> <tr> <td>DPLL</td> <td><a href="/misc/goto?guid=4958201833401010955">(link)</a></td> <td>10‑23‑2010</td> <td>Haskell</td> <td>An implementation of the <a href="/misc/goto?guid=4958201834143461317">DPLL algorithm</a> for solving <a href="/misc/goto?guid=4958201834868695794">CNF-SAT</a>.</td> </tr> <tr> <td>Smoothsort</td> <td><a href="/misc/goto?guid=4958201835610611958">(link)</a></td> <td>10‑27‑2010</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201836338637842">smoothsort algorithm</a>, an adaptive heapsort variant.</td> </tr> <tr> <td>Extendible Array</td> <td><a href="/misc/goto?guid=4958201837074733518">(link)</a></td> <td>10‑28‑2010</td> <td>Java</td> <td>A <a href="/misc/goto?guid=4958201837828010826">dynamic array</a> class with O (1) worst-case runtime lookup and append.</td> </tr> <tr> <td>In-Place Merge</td> <td><a href="/misc/goto?guid=4958201838566636497">(link)</a></td> <td>10‑29‑2010</td> <td>C++</td> <td>An implementation of a <a href="/misc/goto?guid=4958201839297515129">merge algorithm</a> that runs <a href="/misc/goto?guid=4958201840039009889">in-place</a>.</td> </tr> <tr> <td>Random Shuffle</td> <td><a href="/misc/goto?guid=4958201840778142363">(link)</a></td> <td>10‑29‑2010</td> <td>C++</td> <td>An algorithm for generating a <a href="/misc/goto?guid=4958201841517510886">random permutation</a> of a set of elements.</td> </tr> <tr> <td>Random Sample</td> <td><a href="/misc/goto?guid=4958201842253210679">(link)</a></td> <td>10‑29‑2010</td> <td>C++</td> <td>An O (n) time, O (1) space algorithm for randomly choosing k elements out of a stream with uniform probability.</td> </tr> <tr> <td>Natural Mergesort</td> <td><a href="/misc/goto?guid=4958201842994452077">(link)</a></td> <td>10‑30‑2010</td> <td>C++</td> <td>An implementation of <a href="/misc/goto?guid=4958201843727991519">natural mergesort</a>, an <a href="/misc/goto?guid=4958201844469947003">adaptive</a> variant of <a href="/misc/goto?guid=4958201845206208053">mergesort</a>.</td> </tr> <tr> <td>Interpolation Search</td> <td><a href="/misc/goto?guid=4958201845949316212">(link)</a></td> <td>10‑31‑2010</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201846681519750">interpolation search</a> algorithm.</td> </tr> <tr> <td>Introsort</td> <td><a href="/misc/goto?guid=4958201847418113062">(link)</a></td> <td>10‑31‑2010</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201848149564394">introsort</a> algorithm, a fast hybrid of <a href="/misc/goto?guid=4958201848898154185">quicksort</a>, <a href="/misc/goto?guid=4958201828003973491">heapsort</a>, and<a href="/misc/goto?guid=4958201850307178486">insertion sort</a>.</td> </tr> <tr> <td>Hashed Array Tree</td> <td><a href="/misc/goto?guid=4958201851045402679">(link)</a></td> <td>11‑3‑2010</td> <td>Java</td> <td>An implementation of a dynamic array backed by a <a href="/misc/goto?guid=4958201851783595992">hashed array tree</a>.</td> </tr> <tr> <td>Recurrence Solver</td> <td><a href="/misc/goto?guid=4958201852527178353">(link)</a></td> <td>11‑13‑2010</td> <td>C++</td> <td>A fast algorithm for generating terms of a sequence defined by a <a href="/misc/goto?guid=4958201853264263921">linear recurrence relation</a>.</td> </tr> <tr> <td>Fibonacci Heap</td> <td><a href="/misc/goto?guid=4958201854008188205">(link)</a></td> <td>11‑15‑2010</td> <td>Java</td> <td>An implementation of a priority queue backed by a <a href="/misc/goto?guid=4958201854735173376">Fibonacci heap</a>.</td> </tr> <tr> <td>Dijkstra’s Algorithm</td> <td><a href="/misc/goto?guid=4958201855480420935">(link)</a></td> <td>11‑16‑2010</td> <td>Java</td> <td>An implementation of <a href="/misc/goto?guid=4958201856214562071">Dijkstra’s algorithm</a> for single-source shortest paths.</td> </tr> <tr> <td>Prim’s Algorithm</td> <td><a href="/misc/goto?guid=4958201856956340589">(link)</a></td> <td>11‑17‑2010</td> <td>Java</td> <td>An implementation of <a href="/misc/goto?guid=4958201857685480969">Prim’s algorithm</a> for computing <a href="/misc/goto?guid=4958201858428056159">minimum spanning trees</a>.</td> </tr> <tr> <td>Kruskal’s Algorithm</td> <td><a href="/misc/goto?guid=4958201859170320025">(link)</a></td> <td>11‑17‑2010</td> <td>Java</td> <td>An implementation of <a href="/misc/goto?guid=4958201859915264920">Kruskal’s algorithm</a> for computing <a href="/misc/goto?guid=4958201858428056159">minimum spanning trees</a>.</td> </tr> <tr> <td>Majority Element</td> <td><a href="/misc/goto?guid=4958201861318748140">(link)</a></td> <td>11‑17‑2010</td> <td>C++</td> <td>A fast, linear-time algorithm for finding the <a href="/misc/goto?guid=4958201862060446003">majority element</a> of a data set.</td> </tr> <tr> <td>Haar Transform</td> <td><a href="/misc/goto?guid=4958201862791571867">(link)</a></td> <td>11‑17‑2010</td> <td>C++</td> <td>A set of functions to decompose a sequence of values into a sum of <a href="/misc/goto?guid=4958201863520504797">Haar wavelets</a>.</td> </tr> <tr> <td>Argmax</td> <td><a href="/misc/goto?guid=4958201864264265782">(link)</a></td> <td>11‑19‑2010</td> <td>C++</td> <td>A pair of functions to compute the <a href="/misc/goto?guid=4958201864999928324">arg min or max</a> of a function on some range.</td> </tr> <tr> <td>Derivative</td> <td><a href="/misc/goto?guid=4958201865731824573">(link)</a></td> <td>11‑19‑2010</td> <td>C++</td> <td>A <a href="/misc/goto?guid=4958201866471940684">function object</a> that approximates the <a href="/misc/goto?guid=4958201867210257704">derivative</a> of a function.</td> </tr> <tr> <td>Levenshtein Distance</td> <td><a href="/misc/goto?guid=4958201867948015491">(link)</a></td> <td>11‑19‑2010</td> <td>C++</td> <td>An algorithm for computing the <a href="/misc/goto?guid=4958201868685564792">Levenshtein distance</a> between two sequences.</td> </tr> <tr> <td>Skiplist</td> <td><a href="/misc/goto?guid=4958201869422646808">(link)</a></td> <td>11‑20‑2010</td> <td>C++</td> <td>An implementation of a <a href="/misc/goto?guid=4958201870165049559">skip list</a>, a randomized data structure for maintaining a sorted collection.</td> </tr> <tr> <td>van Emde Boas Tree</td> <td><a href="/misc/goto?guid=4958201870902882206">(link)</a></td> <td>11‑26‑2010</td> <td>C++</td> <td>An implementation of a sorted associative array backed by a <a href="/misc/goto?guid=4958201871629232475">van Emde Boas tree</a>.</td> </tr> <tr> <td>Cuckoo HashMap</td> <td><a href="/misc/goto?guid=4958201872378239003">(link)</a></td> <td>11‑27‑2010</td> <td>Java</td> <td>An implementation of a <a href="/misc/goto?guid=4958201873110005853">hash table</a> using <a href="/misc/goto?guid=4958201873847479001">cuckoo hashing</a>.</td> </tr> <tr> <td>Needleman-Wunsch Algorithm</td> <td><a href="/misc/goto?guid=4958201874586485675">(link)</a></td> <td>11‑28‑2010</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201875326201425">Needleman-Wunsch</a> algorithm for optimal string alignment.</td> </tr> <tr> <td>Treap</td> <td><a href="/misc/goto?guid=4958201876059891653">(link)</a></td> <td>11‑28‑2010</td> <td>C++</td> <td>An implementation of a sorted associative array backed by a <a href="/misc/goto?guid=4958201876797912757">treap</a>.</td> </tr> <tr> <td>Floyd-Warshall Algorithm</td> <td><a href="/misc/goto?guid=4958201877538373769">(link)</a></td> <td>12‑10‑2010</td> <td>Java</td> <td>An implementation of the <a href="/misc/goto?guid=4958201878477913824">Floyd-Warshall algorithm</a> for all-pairs shortest paths in a graph.</td> </tr> <tr> <td>Power Iteration</td> <td><a href="/misc/goto?guid=4958201879227425289">(link)</a></td> <td>12‑10‑2010</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201879974551654">power iteration</a> algorithm for finding dominant eigenvectors.</td> </tr> <tr> <td>Edmonds’s Matching Algorithm</td> <td><a href="/misc/goto?guid=4958201880717953758">(link)</a></td> <td>12‑15‑2010</td> <td>Java</td> <td>An implementation of <a href="/misc/goto?guid=4958201881461417288">Edmonds’s matching algorithm</a> for finding <a href="/misc/goto?guid=4958201882205534620">maximum matchings</a> in undirected graphs.</td> </tr> <tr> <td>Kosaraju’s Algorithm</td> <td><a href="/misc/goto?guid=4958201882957536116">(link)</a></td> <td>12‑15‑2010</td> <td>Java</td> <td>An implementation of <a href="/misc/goto?guid=4958201883681818029">Kosaraju’s algorithm</a> algorithm for finding <a href="/misc/goto?guid=4958201884428471684">strongly connected components</a> of a directed graph.</td> </tr> <tr> <td>2-SAT</td> <td><a href="/misc/goto?guid=4958201885175607374">(link)</a></td> <td>12‑15‑2010</td> <td>Java</td> <td>A linear-time algorithm for solving <a href="/misc/goto?guid=4958201885919499486">2-SAT</a>.</td> </tr> <tr> <td>Bellman-Ford Algorithm</td> <td><a href="/misc/goto?guid=4958201886655046326">(link)</a></td> <td>12‑17‑2010</td> <td>Java</td> <td>An implementation of the <a href="/misc/goto?guid=4958201887393792883">Bellman-Ford</a> algorithm for single-source shortest paths.</td> </tr> <tr> <td>Topological Sort</td> <td><a href="/misc/goto?guid=4958201888128854333">(link)</a></td> <td>12‑17‑2010</td> <td>Java</td> <td>An algorithm for computing a <a href="/misc/goto?guid=4958201888880788618">topological sort</a> of a directed acyclic graph.</td> </tr> <tr> <td>Graham Scan</td> <td><a href="/misc/goto?guid=4958201889620736975">(link)</a></td> <td>12‑19‑2010</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201890359908886">Graham scan</a> for finding convex hulls in 2D space.</td> </tr> <tr> <td>Bipartite Testing</td> <td><a href="/misc/goto?guid=4958201891104674940">(link)</a></td> <td>12‑19‑2010</td> <td>Java</td> <td>A linear-time algorithm for checking whether a directed graph is <a href="/misc/goto?guid=4958201891847045993">bipartite</a>.</td> </tr> <tr> <td>Johnson’s Algorithm</td> <td><a href="/misc/goto?guid=4958201892585872853">(link)</a></td> <td>12‑19‑2010</td> <td>Java</td> <td>An implementation of <a href="/misc/goto?guid=4958201893335129684">Johnson’s algorithm</a> for all-pairs shortest paths.</td> </tr> <tr> <td>Strassen Algorithm</td> <td><a href="/misc/goto?guid=4958201894071805894">(link)</a></td> <td>12‑20‑2010</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201894814729505">Strassen algorithm</a> for fast matrix multiplication.</td> </tr> <tr> <td>Cartesian Tree Sort</td> <td><a href="/misc/goto?guid=4958201895554893925">(link)</a></td> <td>12‑21‑2010</td> <td>C++</td> <td>An implementation of <a href="/misc/goto?guid=4958201896289604573">Cartesian tree sort</a>, an adaptive, out-of-place heapsort variant.</td> </tr> <tr> <td>Ford-Fulkerson Algorithm</td> <td><a href="/misc/goto?guid=4958201897028490238">(link)</a></td> <td>12‑21‑2010</td> <td>Java</td> <td>An implementation of the <a href="/misc/goto?guid=4958201897782575245">Ford-Fulkerson</a> maximum-flow algorithm.</td> </tr> <tr> <td>Scaling Ford-Fulkerson</td> <td><a href="/misc/goto?guid=4958201898524101512">(link)</a></td> <td>12‑22‑2010</td> <td>Java</td> <td>An modification of the <a href="/misc/goto?guid=4958201897782575245">Ford-Fulkerson</a> maximum-flow algorithm that uses scaling to achieve polynomial time..</td> </tr> <tr> <td>Splay Tree</td> <td><a href="/misc/goto?guid=4958201899951237312">(link)</a></td> <td>12‑27‑2010</td> <td>C++</td> <td>An implementation of a sorted associative array backed by a <a href="/misc/goto?guid=4958201900692925294">splay tree</a>.</td> </tr> <tr> <td>Ternary Search Tree</td> <td><a href="/misc/goto?guid=4958201901436963525">(link)</a></td> <td>12‑28‑2010</td> <td>C++</td> <td>An implementation of a sorted set of strings backed by a <a href="/misc/goto?guid=4958201902173540683">ternary search tree</a>.</td> </tr> <tr> <td>Ring Buffer</td> <td><a href="/misc/goto?guid=4958201902920422234">(link)</a></td> <td>12‑30‑2010</td> <td>Java</td> <td>An implementation of a FIFO queue using a <a href="/misc/goto?guid=4958201903657725515">ring buffer</a>.</td> </tr> <tr> <td>AVL Tree</td> <td><a href="/misc/goto?guid=4958201904399454683">(link)</a></td> <td>12‑30‑2010</td> <td>C++</td> <td>A sorted associative container backed by an <a href="/misc/goto?guid=4958201905143501619">AVL tree</a>.</td> </tr> <tr> <td>Rabin-Karp Algorithm</td> <td><a href="/misc/goto?guid=4958201905877871580">(link)</a></td> <td>1‑1‑2011</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201906617813290">Rabin-Karp algorithm</a> for string matching.</td> </tr> <tr> <td>RPN Evaluator</td> <td><a href="/misc/goto?guid=4958201907375864375">(link)</a></td> <td>1‑18‑2011</td> <td>C++ / strain</td> <td>A library to tokenize and evaluate simple arithmetic expressions in <a href="/misc/goto?guid=4958201908110157371">reverse Polish notation</a>.</td> </tr> <tr> <td>Shunting-Yard Algorithm</td> <td><a href="/misc/goto?guid=4958201908872169874">(link)</a></td> <td>1‑18‑2011</td> <td>C++ / strain</td> <td>An implementation of Dijkstra’s <a href="/misc/goto?guid=4958201909598544556">shunting-yard algorithm</a> for converting infix expressions to reverse-Polish notation.</td> </tr> <tr> <td>Skew Binomial Heap</td> <td><a href="/misc/goto?guid=4958201910334203316">(link)</a></td> <td>1‑20‑2011</td> <td>C++</td> <td>An implementation of a priority queue backed by a <a href="/misc/goto?guid=4958201911074076285">skew binomial heap</a>.</td> </tr> <tr> <td>2/3 Heap</td> <td><a href="/misc/goto?guid=4958201911824416510">(link)</a></td> <td>3‑1‑2011</td> <td>C++</td> <td>An implementation of a priority queue whose branching factor alternates at different levels to maximize performance.</td> </tr> <tr> <td>Zeckendorf Logarithm</td> <td><a href="/misc/goto?guid=4958201912555991722">(link)</a></td> <td>3‑10‑2011</td> <td>C++</td> <td>An algorithm based on <a href="/misc/goto?guid=4958201913306611122">Zeckendorf representations</a> that efficiently computes logarithms.</td> </tr> <tr> <td>Factoradic Permutations</td> <td><a href="/misc/goto?guid=4958201914045257114">(link)</a></td> <td>3‑17‑2011</td> <td>C++</td> <td>A set of algorithms for generating <a href="/misc/goto?guid=4958201914794237120">permutations</a> using the <a href="/misc/goto?guid=4958201915529238507">factoradic number system</a>.</td> </tr> <tr> <td>Binary Cyclic Subsets</td> <td><a href="/misc/goto?guid=4958201916282531648">(link)</a></td> <td>3‑20‑2011</td> <td>C++</td> <td>A set of algorithms for generating <a href="/misc/goto?guid=4958201917025397278">subsets</a> in <a href="/misc/goto?guid=4958201917762469311">lexicographical order</a> using <a href="/misc/goto?guid=4958201918495340149">binary numbers and cyclic shifts</a>.</td> </tr> <tr> <td>Fibonacci Iterator</td> <td><a href="/misc/goto?guid=4958201919241961400">(link)</a></td> <td>3‑22‑2011</td> <td>C++</td> <td>An STL-style iterator for iterating over the <a href="/misc/goto?guid=4958201919979965707">Fibonacci numbers</a>.</td> </tr> <tr> <td>Fibonacci Search</td> <td><a href="/misc/goto?guid=4958201920725576611">(link)</a></td> <td>3‑22‑2011</td> <td>C++</td> <td>An implementation of the <a href="/misc/goto?guid=4958201921465738430">Fibonacci search</a> algorithm.</td> </tr> <tr> <td>Euclid’s Algorithm</td> <td><a href="/misc/goto?guid=4958201922207808460">(link)</a></td> <td>4‑18‑2011</td> <td>Haskell</td> <td>An implementation of <a href="/misc/goto?guid=4958201922951335713">Euclid’s algorithm</a> and applications to <a href="/misc/goto?guid=4958201923691251038">continued fractions</a> and <a href="/misc/goto?guid=4958201924439658131">the extended Euclidean algorithm</a>.</td> </tr> <tr> <td>Find Duplicate</td> <td><a href="/misc/goto?guid=4958201925171677471">(link)</a></td> <td>4‑18‑2011</td> <td>Python</td> <td>An algorithm to find a repeated element in an array using <a href="/misc/goto?guid=4958201925923062012">Floyd’s cycle-finding algorithm</a>.</td> </tr> <tr> <td>Permutation Generator</td> <td><a href="/misc/goto?guid=4958201926656251733">(link)</a></td> <td>4‑19‑2011</td> <td>Python</td> <td>A <a href="/misc/goto?guid=4958201927397993829">generator</a> for producing all <a href="/misc/goto?guid=4958201914794237120">permutations</a> of a list of elements.</td> </tr> <tr> <td>Matrix Find</td> <td><a href="/misc/goto?guid=4958201928821397514">(link)</a></td> <td>4‑19‑2011</td> <td>Python</td> <td>A solution to the classic interview question of searching a sorted matrix for a particular value.</td> </tr> <tr> <td>Binary GCD</td> <td><a href="/misc/goto?guid=4958201929565932186">(link)</a></td> <td>4‑23‑2011</td> <td>Scheme</td> <td>An implementation of the <a href="/misc/goto?guid=4958201930304980063">binary GCD algorithm</a> for computing greatest common divisors of nonnegative integers.</td> </tr> <tr> <td>Knuth-Morris-Pratt Algorithm</td> <td><a href="/misc/goto?guid=4958201931037194665">(link)</a></td> <td>5‑3‑2011</td> <td>Python</td> <td>An implementation of the <a href="/misc/goto?guid=4958201931781271592">Knuth-Morris-Pratt algorithm</a> for fast string matching.</td> </tr> <tr> <td>Kadane’s Algorithm</td> <td><a href="/misc/goto?guid=4958201932519384796">(link)</a></td> <td>5‑7‑2011</td> <td>C++</td> <td>An implementation of Kadane’s algorithm for solving the <a href="/misc/goto?guid=4958201933269692850">maximum-weight subarray problem</a>.</td> </tr> <tr> <td>Karatsuba’s Algorithm</td> <td><a href="/misc/goto?guid=4958201934011203946">(link)</a></td> <td>8‑15‑2011</td> <td>Python</td> <td>An implementation of <a href="/misc/goto?guid=4958201934765211614">Karatsuba’s algorithm</a> for fast integer multiplication.</td> </tr> <tr> <td>Min-Stack</td> <td><a href="/misc/goto?guid=4958201935495256678">(link)</a></td> <td>8‑15‑2011</td> <td>C++</td> <td>An implementation of a <a href="/misc/goto?guid=4958201936233734680">LIFO stack</a> that supports O (1) push, pop, and find-minimum.</td> </tr> <tr> <td>Random Bag</td> <td><a href="/misc/goto?guid=4958201936982926507">(link)</a></td> <td>8‑15‑2011</td> <td>Python</td> <td>A data structure that supports insertion and removal of a uniformly-random element.</td> </tr> <tr> <td>Min-Queue</td> <td><a href="/misc/goto?guid=4958201937728599024">(link)</a></td> <td>8‑15‑2011</td> <td>C++</td> <td>An implementation of a <a href="/misc/goto?guid=4958201938475010265">FIFO queue</a> that supports O (1) push, pop, and find-minimum.</td> </tr> <tr> <td>Lights-Out Solver</td> <td><a href="/misc/goto?guid=4958201939209590380">(link)</a></td> <td>8‑29‑2011</td> <td>C++</td> <td>A solver for the game <a href="/misc/goto?guid=4958201939956441016">Lights Out</a> using <a href="/misc/goto?guid=4958201940691761524">Gaussian elimination</a> over <a href="/misc/goto?guid=4958201941435911948">GF (2)</a>.</td> </tr> <tr> <td>Maximum Single-Sell Profit</td> <td><a href="/misc/goto?guid=4958201942169018099">(link)</a></td> <td>11‑9‑2011</td> <td>Python</td> <td>Four algorithms for the <a href="/misc/goto?guid=4958201942911459385">maximum single-sell profit problem</a>, each showing off a different algorithmic technique.</td> </tr> <tr> <td>Generalized Kadane’s Algorithm</td> <td><a href="/misc/goto?guid=4958201943645132398">(link)</a></td> <td>11‑10‑2011</td> <td>C++</td> <td>A generalization of <a href="/misc/goto?guid=4958201933269692850">Kadane’s algorithm</a> for solving the maximum subarray problem subject to a <a href="/misc/goto?guid=4958201945071313022">length restriction</a>.</td> </tr> <tr> <td>Longest Range</td> <td><a href="/misc/goto?guid=4958201945808736739">(link)</a></td> <td>11‑19‑2011</td> <td>Java</td> <td>An algorithm for solving the <a href="/misc/goto?guid=4958201946555899692">longest contiguous range</a> problem.</td> </tr> <tr> <td>Egyptian Fractions</td> <td><a href="/misc/goto?guid=4958201947295608235">(link)</a></td> <td>11‑20‑2011</td> <td>Python</td> <td>An implementation of the <a href="/misc/goto?guid=4958201948229381905">greedy algorithm</a> for finding <a href="/misc/goto?guid=4958201948962724100">Egyptian fractions</a>.</td> </tr> <tr> <td>LL (1) Parser Generator</td> <td><a href="/misc/goto?guid=4958201949700514058">(link)</a></td> <td>11‑21‑2011</td> <td>Java</td> <td>An <a href="/misc/goto?guid=4958201950440922420">LL (1) parser generator</a>.</td> </tr> <tr> <td>LR (0) Parser Generator</td> <td><a href="/misc/goto?guid=4958201951162380055">(link)</a></td> <td>11‑23‑2011</td> <td>Java</td> <td>An <a href="/misc/goto?guid=4958201951894261720">LR (0) parser generator</a>.</td> </tr> <tr> <td>Word Ladders</td> <td><a href="/misc/goto?guid=4958201952615401652">(link)</a></td> <td>11‑27‑2011</td> <td>JavaScript</td> <td>A program for finding <a href="/misc/goto?guid=4958201953338789190">word ladders</a> between two words.</td> </tr> </tbody> </table> <br /> 来自: <a id="link_source2" href="/misc/goto?guid=4958201954063750847" target="_blank">coolshell.cn</a>