Ich hatte vor kurzem an einem von einer Firma gesponserten Wettbewerb teilgenommen und es gab diese eine Frage, die ich nicht verstand, was ich gefragt hatte.
Hier ist die Frage:
Die Zeichenfolge "paypal ist der schnellere und sicherere Weg Geld zu senden" ist in a geschrieben Spiralmuster im Uhrzeigersinn innerhalb eines Quadrats beginnend mit der oberen linken Ecke: (Sie sollten dieses Muster zur besseren Lesbarkeit in einer festen Schriftart anzeigen).
%Vor%Lesen Sie Zeile für Zeile: PAYPALFERWAIAMONYSSDYETTRNESOHETSAFE
Schreiben Sie den Code, der eine Zeichenkette benötigt, und berechnen Sie das minimale Quadrat, das das wird enthalten Sie es und geben Sie die konvertierte Zeichenkette zurück:
String konvertieren (String Text);
Beispiel:
%Vor%Verstehen Sie, wie wir dieses Problem angehen können?
Ich glaube, dass die Frage, wie geschrieben, wie folgt interpretiert werden soll:
Sie erhalten eine Zeichenfolge und möchten diese Zeichenfolge als Spirale in ein quadratisches Gitter schreiben. Schreiben Sie eine Funktion, die das kleinste Quadrat findet, das die Zeichenfolge enthalten kann, schreibt die Zeichenfolge in das Raster, indem sie ihre Zeichen im Uhrzeigersinn spiralförmig um das Raster dreht und schließlich die Zeilen zusammenfügt.
Als Beispiel würde die Zeichenfolge "In einer Spirale" so aussehen:
%Vor%Um zu sehen, woher das Gitter kommt, beachten Sie, dass wenn Sie es so lesen:
%Vor%Sie erhalten den ursprünglichen Text zurück, und wenn Sie die Zeilen "INA", "ALS" und "RIP" in eine einzelne Zeichenfolge kleben, erhalten Sie "INAALSRIP" zurück.
Betrachten wir jedes Problem einzeln. Um die kleinste Größe eines Rechtecks zu sehen, das den Text enthalten kann, suchen Sie im Wesentlichen nach dem kleinsten perfekten Quadrat, das mindestens so groß ist wie die Länge Ihres Textes. Um dies zu finden, könnten Sie die Quadratwurzel der Länge Ihrer Zeichenkette nehmen und sie auf die nächste Ganzzahl runden. Das gibt Ihnen die Dimension, die Sie möchten. Bevor Sie dies jedoch tun können, müssen Sie alle Interpunktions- und Leerzeichen aus der Zeichenfolge entfernen (und möglicherweise auch die Zahlen, abhängig von der Anwendung). Sie können dies tun, indem Sie über die Zeichenfolge gehen und die Buchstaben, die tatsächlich alphabetisch sind, in einen neuen Puffer kopieren. Im Folgenden gehe ich davon aus, dass Sie das getan haben.
Wie man das Gitter tatsächlich ausfüllt, gibt es eine wirklich gute Möglichkeit, dies zu tun. Die Intuition ist wie folgt. Wenn Sie in einem n x n-Gitter beginnen, sind Ihre Grenzen die Wände des Gitters. Jedes Mal, wenn du über das Raster marschierst und Buchstaben auf eine Wand triffst, hast du gerade eine Reihe oder Spalte von der Matrix entfernt. Folglich könnte Ihr Algorithmus funktionieren, indem er die erste und die letzte legale Spalte und die erste und letzte legale Zeile verfolgt. Du gehst dann über die obere Reihe von links nach rechts und schreibst Charaktere. Wenn Sie fertig sind, erhöhen Sie dann die erste legale Reihe, da Sie dort nichts mehr setzen können. Gehe dann die rechte Seite hinunter, bis du den Boden erreichst. Sobald Sie fertig sind, würden Sie dann auch die letzte Spalte von der Betrachtung ausschließen. Um beispielsweise auf unser Beispiel "In einer Spirale" zurückzukommen, beginnen wir mit einem leeren 3x3-Gitter:
%Vor%Nachdem wir die ersten drei Buchstaben oben geschrieben haben, bleibt uns folgendes:
%Vor%Nun müssen wir den Rest der Zeichenfolge in den leeren Bereich schreiben, beginnend mit dem oberen rechten Quadrat und nach unten bewegen. Da wir nie wieder in die oberste Zeile schreiben können, ist eine Möglichkeit, darüber nachzudenken, das Problem zu lösen, die restlichen Zeichen in einer Spirale auf kleinerem Raum zu schreiben.
%Vor%Ausgehend von der oberen linken Ecke und nach unten bewegen.
Um dies tatsächlich als Algorithmus zu realisieren, müssen wir an jedem Punkt ein paar Dinge im Auge behalten. Zuerst müssen wir die Grenzen der Welt speichern, während wir sie aktualisieren. Wir müssen auch unseren aktuellen Schreibstandort speichern, in welche Richtung wir uns bewegen. Im Pseudocode wird dies wie folgt dargestellt:
%Vor%Sie können die Neunzig-Grad-Drehung mit einem Trick aus der linearen Algebra implementieren: Um einen Vektor um 90 Grad nach links zu drehen, multiplizieren Sie ihn mit dem Rotationsmatrix
%Vor%Ihr neues dy und dx sind also gegeben durch
%Vor%Sie können also nach links abbiegen, indem Sie
berechnen %Vor% Wenn Sie jedoch wissen, dass das Zeichen mit dem numerischen Wert Null niemals in der Zeichenfolge angezeigt wird, können Sie die Tatsache verwenden, dass Java alle Arrays so initialisiert, dass sie überall Nullen enthalten. Sie können dann 0 als Sentinel behandeln, was bedeutet, dass "es sicher ist, weiter voranzukommen". Diese Version des (Pseudo-) Codes würde so aussehen: %Vor%Wenn Sie schließlich die Zeichenfolge in die Spirale geschrieben haben, können Sie diesen spiralförmigen Text wieder in eine Zeichenfolge konvertieren, indem Sie nacheinander die einzelnen Zeilen durchlaufen und alle gefundenen Zeichen miteinander verketten.
BEARBEITEN : Wie @Voo hervorhebt, können Sie den letzten Schritt dieses Algorithmus vereinfachen, indem Sie überhaupt kein mehrdimensionales Array erstellen und stattdessen das mehrdimensionale Array als eindimensionales Array codieren. Dies ist ein häufiger (und cleverer!) Trick. Angenommen, wir haben ein solches Gitter:
%Vor%Dann können wir dies mit einem eindimensionalen Array als
darstellen %Vor%Die Idee ist, dass wir ein gegebenes (Zeilen-, Spalten-) Paar in einem N × N-Gitter erhalten, indem wir diese Koordinate an eine entsprechende Stelle in dem linearisierten Array umwandeln, indem wir die Positionszeile * N + col betrachten. Intuitiv besagt dies, dass jeder Schritt in der y-Richtung dem Überspringen aller N Elemente einer Zeile entspricht und jeder horizontale Schritt sich in der linearisierten Darstellung nur einen Schritt horizontal bewegt.
Hoffe, das hilft!
Ich habe eine Implementierung in Python geschrieben, die meines Erachtens einen handwerklichen Ansatz zeigt. Obwohl Sie Ihre Frage mit Java getaggt haben, denke ich manchmal, dass es klug ist, über Probleme zu prototypieren und sie zu lernen, vor allem "Interviewfragen" in einer sehr dynamischen Sprache. Die Sprache selbst ist wie Pseudocode, der ausgeführt wird, und das hilft Ihnen, die Form des Problems oder die Form der Frage zu verstehen.
Die Hinweise sind da, wie die Person die Frage gestellt hat:
Von dem Punkt an, wo Sie es in kleinere Stücke zerlegen, sollten Sie in der Lage sein, die Frage zu verstehen, und dann anfangen, eine Antwort zu formulieren.
Es könnte wahrscheinlich in viel weniger Codezeilen gemacht werden, aber ich wollte es so linear wie möglich machen. Hier ist eine nicht-sehr-gute-Python-Antwort:
%Vor%Und hier ist eine Idee, wie man eine kühlere Version macht, aber es würde die Erzeugung der Reihe von Werten erfordern, die "Begrenzungen" hier genannt werden, die die "Länge eines Spazierganges sind, bevor Sie sich drehen".
%Vor%Die Größe der Seite des Quadrats ist die Quadratwurzel des Quadrats, wobei das Quadrat an erster Stelle steht.
Antwort:
Wie ich verstehe:
Sie haben
%Vor%Sie konvertieren es in ein Quadrat (wenn möglich)
%Vor%Und dann mache die Schnur im Uhrzeigersinn
%Vor%Und diese Zeichenfolge zurückgeben
Ich bin mir nicht sicher, was ich tun soll, wenn es unmöglich ist, daraus einen Platz zu machen.
Das verstehe ich von der Frage.
Sagen wir, wir haben die Zeichenfolge "Hallo Welt, das war das erste Skript, das ich programmiert habe, wie geht es dir heute gut?"
Diese Zeichenfolge hat 64 Zeichen.
Wenn Sie nun die Zeichenfolge betrachten, die Sie angegeben haben, hat sie 36 Zeichen, von denen die Quadratwurzel 6 ist, also 6 Buchstaben auf jeder Seite.
Also die obige Zeichenfolge hat 64 Zeichen, von denen die Quadratwurzel ist: 8
was bedeutet, dass das minimale Quadrat 8 Buchstaben auf jeder Seite sein muss.
Diese Antwort bezieht sich auf den Prozess hinter der Anforderung "Quadratgröße berechnen".
Leute verwenden viele verschachtelte Schleifen und if-Anweisungen in ihren obigen Lösungen. Persönlich finde ich es sauberer zu denken, wie man das in Bezug auf:
macht %Vor%Es ist eine klassische rekursive Lösung, die sogar für einen Fork-Join-Pool geändert werden könnte, wenn Sie das wirklich wollen. Diese spezielle Lösung passt die Ausgabegröße entsprechend der Eingabe an. Es ist also möglich, dass Sie 5 Zeilen x 6 Spalten erhalten, wenn Sie genügend Zeichen von der Eingabe abschneiden (obwohl Sie die Zeilenbeschneidung immer auslassen und nur ein Quadrat mit erzeugen könnten) viele Leerzeichen).
%Vor% Sieht aus wie PAYPALISTHEFASTERSAFERWAYTOSENDMONEY ist die Eingabe und
ist die Ausgabe für mich ..
Auch wenn die Frage nicht klar war, ob man anfangs einen Algorithmus zur Verfügung stellen sollte. Hier ist Pseudocode für die rekursive Lösung:
%Vor%und Implementierung in Java:
%Vor%