Articles of Algorithmus

Wie finde ich die Entfernung von der geografischen Breite und Länge zweier Orte?

Ich habe eine Reihe von Breiten und Längen von Orten. Wie finde ich die Entfernung von einem Ort zum anderen? Gibt es eine Formel?

nth hässliche Nummer

Zahlen, deren einzige Primfaktoren 2, 3 oder 5 sind, heißen hässliche Zahlen. Beispiel: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … 1 kann als 2 ^ 0 betrachtet werden. Ich arbeite daran, n hässliche Nummer zu finden. Beachten Sie, dass diese Zahlen extrem spärlich verteilt sind, wenn n groß wird. Ich […]

Auswahlalgorithmen auf sortierter Matrix

Dies ist eine Google-Interviewfrage: Gegeben eine N * N-Matrix. Alle Zeilen sind sortiert und alle Spalten sind sortiert. Finde das K-größte Element der Matrix. tu es in n ^ 2 ist einfach und wir können es mit haufen oder merge sort (n lg n) sortieren und dann bekommen, aber gibt es einen besseren ansatz, besser […]

Wahrscheinlichkeit einer Kollision bei Verwendung eines 32-Bit-Hash

Ich habe ein 10-stelliges Zeichenfolgenschlüsselfeld in einer database. Ich habe CRC32 verwendet, um dieses Feld zu hashen, aber ich mache mir Sorgen um Duplikate. Könnte mir jemand die Wahrscheinlichkeit einer Kollision in dieser Situation zeigen? ps mein String-Feld ist einzigartig in der database. Wenn die Anzahl der Stringfelder 1 Million ist, wie groß ist dann […]

Neue Länge, Breite von alten + n Metern berechnen

Ich möchte 2 neue Längengrade und 2 neue Breiten basierend auf einer Koordinate und einer Entfernung in Metern erstellen. Ich möchte eine schöne Begrenzungsbox um einen bestimmten Punkt erstellen. Sein kleiner Maßstab und max 1500 Meter + und 1500 Meter -. So ist es für einen Teil einer Stadt, ich denke nicht, dass die Krümmung […]

Finden Sie die fehlenden und doppelten Elemente in einem Array in linearer Zeit und konstantem Raum

Sie erhalten ein Array von N 64-Bit-Ganzzahlen. N kann sehr groß sein. Sie wissen, dass jede Ganzzahl 1..N einmal im Array erscheint, außer dass eine ganze Zahl fehlt und eine ganze Zahl dupliziert ist. Schreibe einen linearen Zeitalgorithmus, um die fehlenden und duplizierten Zahlen zu finden. Außerdem sollte Ihr Algorithmus in einem kleinen konstanten Bereich […]

Wie man mögliche Kombination für Münzproblem zählt

Ich versuche, ein Münzproblem zu implementieren, Problembeschreibung ist so Erstellen Sie eine function, um alle möglichen Kombinationen von Münzen zu zählen, die für einen bestimmten Betrag verwendet werden können. All possible combinations for given amount=15, coin types=1 6 7 1) 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 2) 1,1,1,1,1,1,1,1,1,6, 3) 1,1,1,1,1,1,1,1,7, 4) 1,1,1,6,6, 5) 1,1,6,7, 6) 1,7,7, functionsprototyp: int findCombinationsCount(int amount, […]

Bei einem Array ermitteln Sie das nächste kleinere Element für jedes Element

Bei einem gegebenen Array suchen Sie das nächste kleinere Element im Array für jedes Element, ohne die ursprüngliche Reihenfolge der Elemente zu ändern. Angenommen, das angegebene Array ist 4,2,1,5,3. Die resultierende Anordnung wäre 2,1, -1,3, -1. Diese Frage wurde mir in einem Interview gestellt, aber ich konnte mir keine bessere Lösung als die triviale O […]

Was ist die Zeitkomplexität von Average Regex-Algorithmen?

Ich bin nicht neu in der Verwendung von regulären Ausdrücken, und ich verstehe die grundlegende Theorie, auf der sie basieren – Finite-State-Maschinen. Ich bin jedoch nicht so gut in der algorithmischen Analyse und verstehe nicht, wie eine Regex zu vergleichen ist, eine einfache lineare Suche. Ich frage, weil es auf der Oberfläche wie eine lineare […]

Iterative DFS vs Recursive DFS und verschiedene Reihenfolge der Elemente

Ich habe einen rekursiven DFS-Algorithmus geschrieben, um ein Diagramm zu durchlaufen: void Graph::DFS(Node n) { std::cout << ReadNode(n) << " "; MarkVisited(n); NodeList adjnodes = Adjacent(n); NodeList::position pos = adjnodes.FirstPosition(); while(!adjnodes.End(pos)) { Node adj = adjnodes.ReadList(pos); if(!IsMarked(adj)) DFS(adj); pos = adjnodes.NextPosition(pos); } } Dann habe ich einen iterativen DFS-Algorithmus mit einem Stack geschrieben: template void […]