Umkehren einer Zeichenfolge ohne Verwendung von standard-Funktionen
Vor kurzem habe ich gebeten, dies in einem interview. Als ein Hochschulabsolvent, und nur die Programmierung über 2 Jahre (alle Schule), war ich an einem Verlust. Ich hatte eine vage Idee, aber ich bin mir sicher, dass ich versagt habe. Dies ist, was ich geschrieben habe:
string Reverse(string word, string reversed)
{
if(word.length() == 0)
{
return reversed;
}
else
{
string temp;
reversed = word.substr(0,1) + reversed;
temp = word.substr(1);
Reverse(temp, reversed);
}
return reversed;
}
Nun, dass ich zu Hause bin, Teste ich es, und die Rückkehr ist nur der erste Buchstabe in der Eingabe. Ich bin mir vage vertraut mit dem Konzept der Rekursion, aber ich bin offensichtlich in Ermangelung an. Jede Hilfe/Zeiger/Vorschläge werden sehr geschätzt. Danke.
BEARBEITEN:
Folgende Dennis Meng post, ich habe die folgende änderung:
string Reverse(string word, string reversed)
{
if(word.length() == 0)
{
return reversed;
}
else
{
string temp;
reversed = word.substr(0,1) + reversed;
temp = word.substr(1);
return Reverse(temp, reversed);
}
}
Nun bekomme ich den richtigen Wert zurück. Danke so sehr viel.
Warum ist ein
Reverse
Funktion, die zwei Argumente?Die Antwort würde ich schon suchen, wenn ich diese Frage in einem interview, würde man die beteiligten konstruieren einen neuen string mit einem reverse-iterator-paar. Ich werde nicht zu geben Ihnen eine volle Antwort - kann man sehen, dass sich selbst ein.
Interview-Fragen nicht zu "schwer zu beantworten". Interview soll nicht eine Konkurrenz, weil in der Regel müssen Sie ein guter Kandidat für einen job, nicht um ein champion zu werden.
sehr viel, so - es ist oft der Fall, dass er die gewissenhafte und mehr junior-completer-finisher, anstatt ein weiteres star-Entwickler mit einem riesigen ego in Ihrem team, und manchmal ist das budget beschränkt, was Sie mieten. Es ist nichts falsch mit der Erwartung zu mentor für neue team-Mitglieder - aber es hängt sehr viel auf die Umgebung und jemanden, es zu tun. Was Sie nie wollen, ist eine Haftung, die Sie dann später nur schwer brennen nicht besonders gut.
InformationsquelleAutor Renrael | 2012-08-09
Du musst angemeldet sein, um einen Kommentar abzugeben.
Was schief geht, ist hier:
Wissen Sie, dass der Anruf zurückkehren sollte, die richtige Antwort, also warum nicht einfach zurück? In anderen Worten, was, wenn Sie haben
statt? Die Besonderheiten, warum Ihr code war nur die Rückgabe der ersten Buchstaben umfasst pass-by-reference/pass-by-value; wegen der pass-by-value-Sachen, die man eigentlich nie verwendet, was getan wurde in der rekursiven Aufrufe. (Sie machte den call und warf Weg, was gab es zurück.)
Es ist eine ziemlich häufige interview-Frage, die Dinge beginnen, stellen Sie sicher, dass Sie die Grundlagen, etc. Ihr Lehrer Recht, die sagen, dass Sie sollten nicht das Rad neu erfinden, aber es ist gut zu wissen, wie das Rad erfunden wurde, und die Interviewer wissen wollen, Ihre Gedanken mehr als die Antwort sowieso.
(Auch die anderen Jungs Recht, die sagen, es gibt viel bessere Möglichkeiten, dies zu tun, aber ich würde sagen, die on-the-fly in einem interview Frage dieser Ansatz ist völlig in Ordnung.)
Gesehen zu haben, meine ursprüngliche Antwort, auch wenn es nicht die richtigen return-Wert, was würden Sie denken, es als interviewer? Nur versuchen, um zu Messen, einen möglichen Rückruf. Ich fühlte mich den rest des Interviews und der test verlief gut. Wir sind gerade auf diesem.
Gut, ich bin wahrscheinlich nicht die beste person zu Fragen, was für ein interviewer würde sagen, aber wenn ich wurden interviewt Sie und sah diesen code, ich würde sehen, dass man zumindest ein grobes Verständnis von Rekursion, weisen darauf hin, dass es ein Fehler war, und Sie ermutigen, es zu beheben. Sobald es behoben ist, dann würde ich sehen, wenn Sie tun können diese rekursiv, ohne den Akkumulator, und schließlich sehen, wenn Sie tun kann die iterative Lösung.
InformationsquelleAutor Dennis Meng
Erste von allen, sollten Sie die übergabe
word
durch const-Referenz und diereversed
- by-reference. Beim Aufruf der rekursiven Funktion, du machst eine Kopie von jeder dieser strings, also die äußerste Funktion nicht sehen können, alles, was Sie tun. Eine andere Möglichkeit wäre gewesen, weisen Sie das Ergebnis der recursed Funktionreversed
, aber dann haben Sie noch eine dumme Anzahl der string-Kopien überall. Also: die übergabe der Variablen per Referenz.Zweiten: Es gibt einfachere Wege, um das umkehren einer Zeichenfolge:
InformationsquelleAutor Mooing Duck
Ich bin mir nicht sicher, warum bist du mit Rekursion hier. es ist wirklich unnötig:
sizeof(word)
" -- nonononononoNO!Pflege zu erarbeiten?
nicht zurück die Länge der Zeichenfolge, aber die Größe der
std::string
Klasse, das ist nicht, was Sie wollen. Sie benötigenword.size()
brainfart. behoben
Stimmt, aber an dieser Stelle möchte ich nur Kreide es bis zu den Beantworter der Frage zu tun kopieren/einfügen und nicht beschneiden alles aus.
InformationsquelleAutor ewok
Ein string ist nichts anderes als ein array von Zeichen. Generell in diesem Fall, verwenden Sie ein array von Zeichen zu erklären, der Algorithmus. Hier ist ein besserer Weg, es zu tun.
Wenn die gleiche Frage in Java, müssen Sie sicherstellen, dass Sie die Konvertierung von string zu char [] - array umkehren und dann in form eines String. Dies hilft bei der Beibehaltung der Anzahl der Objekte, werden immer erstellt, minimal. Mindestens sollten Sie über einen StringBuilder.
operator []
könnten Sie effektiv nutzen, um dieses sehr gleichen Algorithmus, nur dass Sie sich nicht mehr übergeben müssenlen
Ursache der string bereits kennt, weiß es. 😛InformationsquelleAutor Senthil Babu
Hier ist eine andere Lösung (ähnlich schon gepostet).
Aber jetzt sehe ich, dass diese Lösung nicht für Sie in Ordnung, da es verwendet std Zeug.
InformationsquelleAutor Alexander Rios
Nur zu empfehlen, eine bessere Art des Umgangs mit Rekursion:
String-Umkehr mit Rekursion in C++:
InformationsquelleAutor totjammykd