Von einem Übersetzer: Heute veröffentlichen wir
einen Artikel von
Fabian Terh für Sie. Der Artikel ist vor allem für Programmieranfänger nützlich.
Ich bin ein autodidaktischer Programmierer. Dieser Beitrag spiegelt meine persönlichen Erfahrungen und Fähigkeiten in Bereichen wie Algorithmen und Datenstrukturen wider. Außerdem spreche ich über Möglichkeiten, Probleme zu lösen (die zweite ist mir übrigens etwas schlechter als die erste).
Skillbox empfiehlt: einen zweijährigen praktischen Kurs "Ich bin ein PRO Web Developer".
Wir erinnern Sie daran: Für alle Leser von „Habr“ - ein Rabatt von 10.000 Rubel bei der Anmeldung für einen Skillbox-Kurs mit dem Promo-Code „Habr“.
Problem: Sie kennen die Theorie, haben aber Schwierigkeiten mit der Praxis
Vor nicht allzu langer Zeit hatte ich ein Problem, das als "Ich weiß nicht, was ich nicht weiß" beschrieben werden kann - wir können eine Neugierde sagen. Tatsache ist, dass ich die Theorie ganz gut verstehe. Ich weiß, wie Listen funktionieren, was separate Operationen sind, was abstrakte Datentypen sind usw.
Das Problem ist jedoch, dass ich nicht weiß, welche Informationen für mich in der Praxis nützlich sein können, und ich habe keine Ahnung, was bei einigen Aufgaben möglicherweise fehlt. Daher ist es für mich schwierig, einige Probleme zu lösen.
Arten von Aufgaben, die sich erfüllen könnenEin Beispiel für eine Frage zu Datenstrukturen: Beschreiben Sie, wie Sie einen Knoten in eine verknüpfte Liste einfügen und die zeitliche Komplexität angeben.
Hier ist eine Frage zu Algorithmen: Suchen Sie ein Element in einem gedrehten sortierten Array und bestimmen Sie die zeitliche Komplexität.
Schließlich ist die letzte Frage, die eine höhere "Ebene" als die vorherigen hat, eine Aufforderung, einen Weg zur Lösung des Problems zu beschreiben und die Anforderungen für seine Implementierung aufzulisten.
Im Laufe der Arbeit müssen Sie möglicherweise genau das tun, d. H. Beschreibung der Lösung. Bei der Wettbewerbsprogrammierung ist es häufig erforderlich, Arbeitscode bereitzustellen, ohne explizit Datenstrukturen oder Algorithmen anzugeben. Mit anderen Worten, von Ihnen wird erwartet, dass Sie Datenstrukturen und Algorithmen verwenden können, die jeweils optimal sind, um das Problem so effizient wie möglich zu lösen.
Wie kann ich meine Fähigkeiten verbessern?
Persönlich habe ich dafür drei Ressourcen verwendet: HackerRank, LeetCode und Kattis. Sie sind einander ähnlich, insbesondere die ersten beiden, aber nicht identisch.
Ich würde die Fähigkeiten, die zur Lösung von Problemen benötigt werden, in drei Gruppen einteilen:
- Kenntnis der Datenstrukturen;
- Kenntnis von Algorithmen;
- Fähigkeit, Datenstrukturen und Algorithmen anzuwenden.
Die ersten beiden Kategorien sind grundlegend, sie liegen ganz unten. Die dritte Kategorie ist eine höhere Klasse.
Kenntnis von DatenstrukturenHackerRank war mein Lieblingsplatz hier. Es gibt einen Abschnitt über Datenstrukturen, in dem Informationen nach Typ gefiltert werden können, einschließlich Bäumen, verknüpften Listen, Arrays usw.
Die bei HackerRank angesprochenen Probleme beziehen sich hauptsächlich auf die Arbeit mit Datenstrukturen:
- Arrays: Drehung des Arrays und Ausführung anderer Aktionen damit.
- Verknüpfte Listen: Umkehren, Zykluserkennung.
- Bäume: Knotentausch, BST-Validierung.
Sie haben wahrscheinlich schon verstanden, was los war. Von der Ressource eingereichte Fragen können nicht direkt zur Lösung von Problemen verwendet werden. Aber sie werden benötigt, um die Grundlagen zu verstehen, was in meinem Fall äußerst wichtig war.
HackerRank verfügt nicht über ein allgemein verfügbares „Lösungsmodell“, obwohl der Diskussionsteil viele Tipps, Tricks und sogar Fragmente von Arbeitscode enthält. Das alles hat mir sehr geholfen.
Kenntnis der AlgorithmenHackerRank hat einen Abschnitt mit Algorithmen, obwohl LeetCode näher bei mir ist. Es scheint mir, dass die Liste der angesprochenen Themen in der zweiten Ressource viel umfangreicher ist und es Erklärungen und Tipps gibt.
Beginnen Sie am besten mit den 100 häufigsten Fragen (dieser Abschnitt bezieht sich auf LeetCode). Einige waren sehr nützlich für mich:
- Zusammenführen von Konten;
- größte kontinuierlich ansteigende Folge;
- Suche in gedrehtem sortiertem Array.
Im Gegensatz zu Problemen im Zusammenhang mit Datenstrukturen liegt der Schwerpunkt hier auf der Vorgehensweise. Beispielsweise ist das Problem des Zusammenführens von Konten hauptsächlich auf die Verwendung von Standard-UFDS-Algorithmen zurückzuführen. Das Suchproblem in einem gedrehten sortierten Array ist eine Drehung in einer binären Suche. Manchmal ist es möglich, qualitativ neue Methoden zur Lösung von Problemen zu finden - zum Beispiel die "Schiebefenster" -Methode für das Problem der längsten kontinuierlich ansteigenden Teilsequenz. "
Fähigkeit, Datenstrukturen und Algorithmen anzuwendenNun, ich habe diese Fähigkeit bereits mit Hilfe der Kattis-Ressource gepumpt. Es gibt ein riesiges Archiv gelöster Probleme, in dem Daten aus verschiedenen Quellen gesammelt wurden, darunter Wettbewerbe von Programmierern aus der ganzen Welt.
Leider hat Kattis kein Forum und Fälle sind private, nicht häufige Fälle. Daher gibt es einige Probleme, die ich mit seiner Hilfe nicht lösen konnte.
Eine Ressource kann jedoch vielen Programmierern helfen. Ich selbst habe nicht zu viel Zeit damit verbracht, es zu studieren.
Andere Ressourcen
Geeksforgeeks ist eine weitere wertvolle Ressource zum Erlernen von Algorithmen und Datenstrukturen. Ich mag die Tatsache, dass es Snippets in verschiedenen Sprachen bietet, einschließlich C ++, Java und Python. Sie können sie problemlos verwenden.
Und natürlich gibt es gute alte Google von YouTube.
Fazit
Die Hauptsache ist, Code zu schreiben, Debugging zu betreiben und den Code anderer Entwickler zu studieren, damit Sie Ihre aktuellen Aufgaben schnell erledigen können. Das Lösen von Problemen ist schwierig, aber mit jedem Versuch und mit jedem gelösten Problem werden Sie immer besser.