Articles of Algorithmus

Suchen Sie den kürzesten Pfad in einem Diagramm, das bestimmte Knoten aufruft

Ich habe einen ungerichteten Graphen mit ungefähr 100 Knoten und ungefähr 200 Kanten. Ein Knoten ist mit “Start”, einer mit “Ende” und etwa ein Dutzend mit “Must-Pass” gekennzeichnet. Ich muss den kürzesten Pfad durch diesen Graphen finden, der bei “Start” beginnt, bei “Ende” endet und alle “Muss” -Knoten durchläuft (in beliebiger Reihenfolge). ( http://3e.org/local/maize-graph.png / […]

Notwendigkeit eines vorhersagbaren Zufallsgenerators

Ich bin ein Entwickler von Web-Spielen und habe ein Problem mit Zufallszahlen. Nehmen wir an, ein Spieler hat eine Chance von 20%, einen kritischen Treffer mit seinem Schwert zu erzielen. Das heißt, 1 von 5 Treffern sollte kritisch sein. Das Problem ist, dass ich sehr schlechte Ergebnisse im wirklichen Leben habe – manchmal bekommen die […]

Suchen Sie die kleinste Ganzzahl, die nicht in einer Liste enthalten ist

Eine interessante Interviewfrage, die ein Kollege von mir benutzt: Angenommen, Sie erhalten eine sehr lange, unsortierte Liste von 64-Bit-Ganzzahlen ohne Vorzeichen. Wie finden Sie die kleinste nicht negative Ganzzahl, die nicht in der Liste vorkommt? FOLLOW-UP: Nun, da die offensichtliche Lösung durch Sortierung vorgeschlagen wurde, können Sie es schneller als O (n log n) machen? […]

“Online” (Iterator) -Algorithmen zur Schätzung von statistischem Median, Modus, Schiefe, Kurtosis?

Gibt es einen Algorithmus, um den Median, den Modus, die Schiefe und / oder die Kurtosis einer Menge von Werten zu schätzen, aber das erfordert NICHT das Speichern aller Werte im Speicher auf einmal? Ich möchte die grundlegenden Statistiken berechnen: Mittelwert: arithmetischer Durchschnitt Varianz: Durchschnitt der quadrierten Abweichungen vom Mittelwert Standardabweichung: Quadratwurzel der Varianz Median: […]

Was würde einen Algorithmus veranlassen, O (log n) -Komplexität zu haben?

Mein Wissen über Big-O ist begrenzt, und wenn Log-Begriffe in der Gleichung auftauchen, wirft es mich noch mehr ab. Kann mir jemand einfach erklären, was ein O(log n) –Algorithmus ist? Woher kommt der Logarithmus? Das kam besonders auf, als ich versuchte, diese Zwischenfrage zu lösen: Lassen Sie X (1..n) und Y (1..n) zwei Listen von […]

C ++ string :: Komplexität finden

Warum verwendet der in c ++ implementierte string::find() nicht den KMP-Algorithmus (und läuft nicht in O(N + M) ) und läuft in O(N * M) ? Ist das in C ++ 0x korrigiert? Wenn die Komplexität des aktuellen Fundes nicht O(N * M) , was ist das? PS: Entschuldigung ich meine string::find() Also, welcher Algorithmus […]

Wie kann ich in Java die Nachkommen eines Baumknotens effizient und elegant streamen?

Angenommen, wir haben eine Sammlung von Objekten, die durch eindeutige String , zusammen mit einer class Tree , die eine Hierarchie für sie definiert. Diese class wird unter Verwendung einer Map von Knoten (dargestellt durch ihre IDs) zu Collection der jeweiligen Kinder-IDs implementiert. class Tree { private Map<String, Collection> edges; // … public Stream descendants(String […]

Algorithmus, der Zahlen oder Wörter nimmt und alle möglichen Kombinationen findet

Ich suche nach einem Algorithmus, der Zahlen oder Wörter nimmt und alle möglichen Variationen von ihnen zusammen findet und ich auch definieren kann, wie viele Werte zusammen zu suchen sind. Beispiel lässt uns sagen, die Zeichenfolge oder das Array ist: cat dog fish dann könnten die Ergebnisse für einen Wert von 2 sein: cat dog […]

Binärsuche in Array

Wie würde ich eine binäre Suche mit nur einem Array implementieren?

In Order Successor im binären Suchbaum

Bei einem Knoten in einem BST: Wie findet man den nächsthöheren Schlüssel?