Augment your knowledge of Python with this entertaining learning guide, which features 100 exercises and programming puzzles and solutions. Python Challenges will help prepare you for your next exam or a job interview, and covers numerous practical topics such as strings, data structures, recursion, arrays, and more.
Each topic is addressed in its own separate chapter, starting with an introduction to the basics and followed by 10 to 15 exercises of various degrees of difficulty, helping you to improve your programming skills effectively. Detailed sample solutions, including the algorithms used for all tasks, are included to maximize your understanding of each area. Author Michael Inden also describes alternative solutions and analyzes possible pitfalls and typical errors.
Three appendices round out the book: the first covers the Python command line interpreter, which is often helpful for trying out the code snippets and examples in the book, followed by an overview of Pytest for unit testing and checking the solutions. The last explains the O notation for estimating performance.
After reading this book, you'll be prepared to take the next step in your career or tackle your next personal project. All source code is freely available for download via the Apress website.
What You Will Learn
- Improve your Python knowledge by solving enjoyable but challenging programming puzzles
- Solve mathematical problems, recursions, strings, arrays and more
- Manage data processing and data structures like lists, sets, maps
- Handle advanced recursion as well as binary trees, sorting and searching
- Gamify key fundamentals for fun and easier reinforcement
Who this book is for:
Programmers, software developers who are either professionals or makers, as well as students and teachers. At least some prior experience with the Python programming is recommended.
1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Aufbau der Kapitel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Grundgerust des PyCharm-Projekts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Grundgerust fur die Unit Tests mit PyTest . . . . . . . . . . . . . . . . . . . . . . . . 41.4 Anmerkung zum Programmierstil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Anmerkung zu den Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.6 Ausprobieren der Beispiele und Loesungen . . . . . . . . . . . . . . . . . . . . . . . 9I Grundlagen 112 Mathematische Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.1.1 Roemische Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.1.2 Zahlenspielereien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.2 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.2.1 Aufgabe 1: Grundrechenarten ( ) . . . . . . . . . . . . . . . . . 212.2.2 Aufgabe 2: Zahl als Text ( ) . . . . . . . . . . . . . . . . . . . . . . 222.2.3 Aufgabe 3: Vollkommene Zahlen ( ) . . . . . . . . . . . . . . . 222.2.4 Aufgabe 4: Primzahlen ( ) . . . . . . . . . . . . . . . . . . . . . . . 232.2.5 Aufgabe 5: Primzahlpaare ( ). . . . . . . . . . . . . . . . . . . . . 232.2.6 Aufgabe 6: Prufsumme ( ) . . . . . . . . . . . . . . . . . . . . . . . 232.2.7 Aufgabe 7: Roemische Zahlen ( ) . . . . . . . . . . . . . . . . . . 242.2.8 Aufgabe 8: Kombinatorik ( ) . . . . . . . . . . . . . . . . . . . . . . 242.2.9 Aufgabe 9: Armstrong-Zahlen ( ) . . . . . . . . . . . . . . . . . 252.2.10 Aufgabe 10: Max Change Calculator ( ) . . . . . . . . . . . 252.2.11 Aufgabe 11: Befreundete Zahlen ( ) . . . . . . . . . . . . . . . 262.2.12 Aufgabe 12: Primfaktorzerlegung ( ) . . . . . . . . . . . . . . 262.3 Loesungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.3.1 Loesung 1: Grundrechenarten ( ) . . . . . . . . . . . . . . . . . . 272.3.2 Loesung 2: Zahl als Text ( ) . . . . . . . . . . . . . . . . . . . . . . . 292.3.3 Loesung 3: Vollkommene Zahlen ( ) . . . . . . . . . . . . . . . . 312.3.4 Loesung 4: Primzahlen ( ) . . . . . . . . . . . . . . . . . . . . . . . . 33viii Inhaltsverzeichnis2.3.5 Loesung 5: Primzahlpaare ( ) . . . . . . . . . . . . . . . . . . . . . 352.3.6 Loesung 6: Prufsumme ( ) . . . . . . . . . . . . . . . . . . . . . . . . 392.3.7 Loesung 7: Roemische Zahlen ( ) . . . . . . . . . . . . . . . . . . . 402.3.8 Loesung 8: Kombinatorik ( ) . . . . . . . . . . . . . . . . . . . . . . . 432.3.9 Loesung 9: Armstrong-Zahlen ( ) . . . . . . . . . . . . . . . . . . 462.3.10 Loesung 10: Max Change Calculator ( ) . . . . . . . . . . . . 492.3.11 Loesung 11: Befreundete Zahlen ( ) . . . . . . . . . . . . . . . . 502.3.12 Loesung 12: Primfaktorzerlegung ( ) . . . . . . . . . . . . . . . 523 Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.1.1 Mathematische Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.1.2 Algorithmische Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593.1.3 Typische Probleme: Endlose Aufrufe und RecursionError 643.2 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663.2.1 Aufgabe 1: Fibonacci ( ) . . . . . . . . . . . . . . . . . . . . . . . . . 663.2.2 Aufgabe 2: Ziffern verarbeiten ( ) . . . . . . . . . . . . . . . . . 663.2.3 Aufgabe 3: ggT / GCD ( ) . . . . . . . . . . . . . . . . . . . . . . . . 673.2.4 Aufgabe 4: Reverse String ( ) . . . . . . . . . . . . . . . . . . . . 683.2.5 Aufgabe 5: Array Sum ( ) . . . . . . . . . . . . . . . . . . . . . . . . 683.2.6 Aufgabe 6: Array Min ( ) . . . . . . . . . . . . . . . . . . . . . . . . . 683.2.7 Aufgabe 7: Konvertierungen ( ) . . . . . . . . . . . . . . . . . . . 693.2.8 Aufgabe 8: Exponentialfunktion ( ) . . . . . . . . . . . . . . . . 703.2.9 Aufgabe 9: Pascal'sches Dreieck ( ) . . . . . . . . . . . . . . . 713.2.10 Aufgabe 10: Zahlenpalindrome ( ) . . . . . . . . . . . . . . . . 713.2.11 Aufgabe 11: Permutationen ( ) . . . . . . . . . . . . . . . . . . . 723.2.12 Aufgabe 12: Count Substrings ( ) . . . . . . . . . . . . . . . . . 723.2.13 Aufgabe 13: Lineal ( ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 733.3 Loesungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 743.3.1 Loesung 1: Fibonacci ( ) . . . . . . . . . . . . . . . . . . . . . . . . . . 743.3.2 Loesung 2: Ziffern verarbeiten ( ) . . . . . . . . . . . . . . . . . . 763.3.3 Loesung 3: ggT / GCD ( ) . . . . . . . . . . . . . . . . . . . . . . . . . 783.3.4 Loesung 4: Reverse String ( ) . . . . . . . . . . . . . . . . . . . . . 803.3.5 Loesung 5: Array Sum ( ) . . . . . . . . . . . . . . . . . . . . . . . . . 813.3.6 Loesung 6: Array Min ( ) . . . . . . . . . . . . . . . . . . . . . . . . . . 833.3.7 Loesung 7: Konvertierungen ( ) . . . . . . . . . . . . . . . . . . . . 843.3.8 Loesung 8: Exponentialfunktion ( ) . . . . . . . . . . . . . . . . . 873.3.9 Loesung 9: Pascal'sches Dreieck ( ) . . . . . . . . . . . . . . . 903.3.10 Loesung 10: Zahlenpalindrome ( ) . . . . . . . . . . . . . . . . . 933.3.11 Loesung 11: Permutationen ( ) . . . . . . . . . . . . . . . . . . . . 963.3.12 Loesung 12: Count Substrings ( ) . . . . . . . . . . . . . . . . . . 993.3.13 Loesung 13: Lineal ( ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102Inhaltsverzeichnis ix4 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1054.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1054.2 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1114.2.1 Aufgabe 1: Zahlenumwandlungen ( ) . . . . . . . . . . . . . . 1114.2.2 Aufgabe 2: Joiner ( ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1114.2.3 Aufgabe 3: Reverse String ( ) . . . . . . . . . . . . . . . . . . . . 1124.2.4 Aufgabe 4: Palindrom ( ). . . . . . . . . . . . . . . . . . . . . . . . . 1124.2.5 Aufgabe 5: No Duplicate Chars ( ) . . . . . . . . . . . . . . . . 1134.2.6 Aufgabe 6: Doppelte Buchstaben entfernen ( ) . . . . . 1134.2.7 Aufgabe 7: Capitalize ( ) . . . . . . . . . . . . . . . . . . . . . . . . . 1144.2.8 Aufgabe 8: Rotation ( ) . . . . . . . . . . . . . . . . . . . . . . . . . . 1154.2.9 Aufgabe 9: Wohlgeformte Klammern ( ) . . . . . . . . . . . 1154.2.10 Aufgabe 10: Anagramm ( ) . . . . . . . . . . . . . . . . . . . . . . . 1164.2.11 Aufgabe 11: Morse Code ( ) . . . . . . . . . . . . . . . . . . . . . 1164.2.12 Aufgabe 12: Pattern Checker ( ) . . . . . . . . . . . . . . . . . . 1174.2.13 Aufgabe 13: Tennis-Punktestand ( ) . . . . . . . . . . . . . . . 1174.2.14 Aufgabe 14: Versionsnummern ( ) . . . . . . . . . . . . . . . . 1184.2.15 Aufgabe 15: Konvertierung str_to_number ( ) . . . . 1184.2.16 Aufgabe 16: Print Tower ( ) . . . . . . . . . . . . . . . . . . . . . . 1194.2.17 Aufgabe 17: Gefullter Rahmen ( ) . . . . . . . . . . . . . . . . . 1194.2.18 Aufgabe 18: Vokale raten ( ) . . . . . . . . . . . . . . . . . . . . . 1194.3 Loesungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1204.3.1 Loesung 1: Zahlenumwandlungen ( ) . . . . . . . . . . . . . . . 1204.3.2 Loesung 2: Joiner ( ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1234.3.3 Loesung 3: Reverse String ( ) . . . . . . . . . . . . . . . . . . . . . 1244.3.4 Loesung 4: Palindrom ( ) . . . . . . . . . . . . . . . . . . . . . . . . . 1264.3.5 Loesung 5: No Duplicate Chars ( ) . . . . . . . . . . . . . . . . . 1294.3.6 Loesung 6: Doppelte Buchstaben entfernen ( ) . . . . . . 1314.3.7 Loesung 7: Capitalize ( ). . . . . . . . . . . . . . . . . . . . . . . . . . 1324.3.8 Loesung 8: Rotation ( ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 1364.3.9 Loesung 9: Wohlgeformte Klammern ( ) . . . . . . . . . . . . 1374.3.10 Loesung 10: Anagramm ( ) . . . . . . . . . . . . . . . . . . . . . . . 1394.3.11 Loesung 11: Morse Code ( ) . . . . . . . . . . . . . . . . . . . . . . 1404.3.12 Loesung 12: Pattern Checker ( ) . . . . . . . . . . . . . . . . . . . 1424.3.13 Loesung 13: Tennis-Punktestand ( ) . . . . . . . . . . . . . . . . 1444.3.14 Loesung 14: Versionsnummern ( ) . . . . . . . . . . . . . . . . . 1474.3.15 Loesung 15: Konvertierung str_to_number ( ) . . . . . 1484.3.16 Loesung 16: Print Tower ( ) . . . . . . . . . . . . . . . . . . . . . . . 1514.3.17 Loesung 17: Gefullter Rahmen ( ) . . . . . . . . . . . . . . . . . 1534.3.18 Loesung 18: Vokale raten ( ) . . . . . . . . . . . . . . . . . . . . . . 154x Inhaltsverzeichnis5 Basisdatenstrukturen: Listen, Sets und Dictionaries . . . . . . . . . . . 1575.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1575.1.1 Sequenzielle Datentypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1575.1.2 Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1595.1.3 Mengen (Sets) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1635.1.4 Schlussel-Wert-Abbildungen (Dictionaries) . . . . . . . . . . . . . . . . 1645.1.5 Der Stack als LIFO-Datenstruktur . . . . . . . . . . . . . . . . . . . . . . . . 1665.1.6 Die Queue als FIFO-Datenstruktur . . . . . . . . . . . . . . . . . . . . . . . 1675.2 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1715.2.1 Aufgabe 1: Gemeinsame Elemente ( ). . . . . . . . . . . . . 1715.2.2 Aufgabe 2: Eigener Stack ( ) . . . . . . . . . . . . . . . . . . . . . 1715.2.3 Aufgabe 3: List Reverse ( ) . . . . . . . . . . . . . . . . . . . . . . 1715.2.4 Aufgabe 4: Duplikate entfernen ( ) . . . . . . . . . . . . . . . . 1725.2.5 Aufgabe 5: Maximaler Gewinn ( ) . . . . . . . . . . . . . . . . . 1725.2.6 Aufgabe 6: Langstes Teilstuck ( ) . . . . . . . . . . . . . . . . . 1735.2.7 Aufgabe 7: Wohlgeformte Klammern ( ) . . . . . . . . . . . 1735.2.8 Aufgabe 8: Pascal'sches Dreieck ( ) . . . . . . . . . . . . . . . 1745.2.9 Aufgabe 9: Check Magic Triangle ( ) . . . . . . . . . . . . . . 1745.2.10 Aufgabe 10: Haufigste Elemente ( ) . . . . . . . . . . . . . . . 1755.2.11 Aufgabe 11: Addition von Ziffern ( ) . . . . . . . . . . . . . . . 1755.2.12 Aufgabe 12: List Merge ( ) . . . . . . . . . . . . . . . . . . . . . . . 1765.2.13 Aufgabe 13: Excel Magic Select ( ) . . . . . . . . . . . . . . . 1765.2.14 Aufgabe 14: Stack Based Queue ( ) . . . . . . . . . . . . . . . 1775.3 Loesungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1785.3.1 Loesung 1: Gemeinsame Elemente ( ) . . . . . . . . . . . . . 1785.3.2 Loesung 2: Eigener Stack ( ) . . . . . . . . . . . . . . . . . . . . . . 1805.3.3 Loesung 3: List Reverse ( ) . . . . . . . . . . . . . . . . . . . . . . . 1815.3.4 Loesung 4: Duplikate entfernen ( ) . . . . . . . . . . . . . . . . . 1845.3.5 Loesung 5: Maximaler Gewinn ( ) . . . . . . . . . . . . . . . . . . 1865.3.6 Loesung 6: Langstes Teilstuck ( ) . . . . . . . . . . . . . . . . . . 1885.3.7 Loesung 7: Wohlgeformte Klammern ( ) . . . . . . . . . . . . 1905.3.8 Loesung 8: Pascal'sches Dreieck ( ). . . . . . . . . . . . . . . . 1945.3.9 Loesung 9: Check Magic Triangle ( ) . . . . . . . . . . . . . . . 1965.3.10 Loesung 10: Haufigste Elemente ( ) . . . . . . . . . . . . . . . . 1995.3.11 Loesung 11: Addition von Ziffern ( ) . . . . . . . . . . . . . . . . 2005.3.12 Loesung 12: List Merge ( ) . . . . . . . . . . . . . . . . . . . . . . . . 2045.3.13 Loesung 13: Excel Magic Select ( ) . . . . . . . . . . . . . . . . 2085.3.14 Loesung 14: Stack Based Queue ( ) . . . . . . . . . . . . . . . 210Inhaltsverzeichnis xi6 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2136.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2136.1.1 Eindimensionale Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2146.1.2 Mehrdimensionale Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2226.1.3 Typische Fehler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2276.1.4 Besonderheiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2286.1.5 Rekapitulation: NumPy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2296.2 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2356.2.1 Aufgabe 1: Gerade vor ungeraden Zahlen ( ) . . . . . . . 2356.2.2 Aufgabe 2: Flip ( ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2356.2.3 Aufgabe 3: Palindrom ( ). . . . . . . . . . . . . . . . . . . . . . . . . 2356.2.4 Aufgabe 4: Inplace Rotate ( ) . . . . . . . . . . . . . . . . . . . . . 2366.2.5 Aufgabe 5: Jewels Board Init ( ) . . . . . . . . . . . . . . . . . . 2366.2.6 Aufgabe 6: Jewels Board Erase Diamonds ( ) . . . . . . 2386.2.7 Aufgabe 7: Spiral-Traversal ( ) . . . . . . . . . . . . . . . . . . . . 2396.2.8 Aufgabe 8: Add One to Array As Number ( ). . . . . . . . 2396.2.9 Aufgabe 9: Sudoku-Checker ( ) . . . . . . . . . . . . . . . . . . . 2406.2.10 Aufgabe 10: Flood-Fill ( ) . . . . . . . . . . . . . . . . . . . . . . . . 2416.2.11 Aufgabe 11: Array Min und Max ( ) . . . . . . . . . . . . . . . . 2426.2.12 Aufgabe 12: Array Split ( ) . . . . . . . . . . . . . . . . . . . . . . . 2436.2.13 Aufgabe 13: Minesweeper Board ( ) . . . . . . . . . . . . . . . 2446.3 Loesungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2466.3.1 Loesung 1: Gerade vor ungeraden Zahlen ( ) . . . . . . . . 2466.3.2 Loesung 2: Flip ( ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2506.3.3 Loesung 3: Palindrom ( ) . . . . . . . . . . . . . . . . . . . . . . . . . 2536.3.4 Loesung 4: Inplace Rotate ( ) . . . . . . . . . . . . . . . . . . . . . 2556.3.5 Loesung 5: Jewels Board Init ( ) . . . . . . . . . . . . . . . . . . . 2596.3.6 Loesung 6: Jewels Board Erase Diamonds ( ) . . . . . . . 2656.3.7 Loesung 7: Spiral-Traversal ( ) . . . . . . . . . . . . . . . . . . . . . 2736.3.8 Loesung 8: Add One to Array As Number ( ) . . . . . . . . 2776.3.9 Loesung 9: Sudoku-Checker ( ) . . . . . . . . . . . . . . . . . . . 2786.3.10 Loesung 10: Flood-Fill ( ) . . . . . . . . . . . . . . . . . . . . . . . . . 2836.3.11 Loesung 11: Array Min und Max ( ) . . . . . . . . . . . . . . . . 2876.3.12 Loesung 12: Array Split ( ) . . . . . . . . . . . . . . . . . . . . . . . . 2906.3.13 Loesung 13: Minesweeper Board ( ) . . . . . . . . . . . . . . . 294xii InhaltsverzeichnisII Fortgeschrittenere und kniffligere Themen 3017 Rekursion Advanced . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3037.1 Memoization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3037.1.1 Memoization fur Fibonacci-Zahlen . . . . . . . . . . . . . . . . . . . . . . . . 3037.1.2 Memoization fur Pascal'sches Dreieck . . . . . . . . . . . . . . . . . . . . 3057.1.3 Memoization mit Python-Bordmitteln . . . . . . . . . . . . . . . . . . . . . . 3077.2 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3117.2.1 n-Damen-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3117.3 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3157.3.1 Aufgabe 1: Turme von Hanoi ( ) . . . . . . . . . . . . . . . . . . 3157.3.2 Aufgabe 2: Edit Distance ( ) . . . . . . . . . . . . . . . . . . . . . . 3167.3.3 Aufgabe 3: Longest Common Subsequence ( ) . . . . . 3167.3.4 Aufgabe 4: Weg aus Labyrinth ( ) . . . . . . . . . . . . . . . . . 3177.3.5 Aufgabe 5: Sudoku-Solver ( ) . . . . . . . . . . . . . . . . . . . . 3187.3.6 Aufgabe 6: Math Operator Checker ( ) . . . . . . . . . . . . . 3197.3.7 Aufgabe 7: Wassereimer-Problem ( ) . . . . . . . . . . . . . . 3207.3.8 Aufgabe 8: Alle Palindrom-Teilstrings ( ) . . . . . . . . . . . 3217.3.9 Aufgabe 9: n-Damen-Problem ( ) . . . . . . . . . . . . . . . . . 3217.4 Loesungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3227.4.1 Loesung 1: Turme von Hanoi ( ) . . . . . . . . . . . . . . . . . . . 3227.4.2 Loesung 2: Edit Distance ( ). . . . . . . . . . . . . . . . . . . . . . . 3277.4.3 Loesung 3: Longest Common Subsequence ( ) . . . . . . 3307.4.4 Loesung 4: Weg aus Labyrinth ( ) . . . . . . . . . . . . . . . . . . 3347.4.5 Loesung 5: Sudoku-Solver ( ) . . . . . . . . . . . . . . . . . . . . . 3377.4.6 Loesung 6: Math Operator Checker ( ). . . . . . . . . . . . . . 3447.4.7 Loesung 7: Wassereimer-Problem ( ). . . . . . . . . . . . . . . 3477.4.8 Loesung 8: Alle Palindrom-Teilstrings ( ) . . . . . . . . . . . . 3507.4.9 Loesung 9: n-Damen-Problem ( ) . . . . . . . . . . . . . . . . . . 3548 Binarbaume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3618.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3618.1.1 Aufbau, Begrifflichkeiten und Anwendungsbeispiele . . . . . . . . 3618.1.2 Binarbaume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3628.1.3 Binarbaume mit Ordnung: binare Suchbaume . . . . . . . . . . . . . 3638.1.4 Traversierungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3658.1.5 Balancierte Baume und weitere Eigenschaften . . . . . . . . . . . . . 3678.1.6 Baume fur die Beispiele und UEbungsaufgaben . . . . . . . . . . . . . 3698.2 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3718.2.1 Aufgabe 1: Tree Traversal ( ) . . . . . . . . . . . . . . . . . . . . . 3718.2.2 Aufgabe 2: In-, Pre- und Postorder iterativ ( ) . . . . . . . 3718.2.3 Aufgabe 3: Tree-Hoehe berechnen ( ) . . . . . . . . . . . . . . 3718.2.4 Aufgabe 4: Kleinster gemeinsamer Vorfahre ( ) . . . . . 372Inhaltsverzeichnis xiii8.2.5 Aufgabe 5: Breadth-First ( ) . . . . . . . . . . . . . . . . . . . . . . 3728.2.6 Aufgabe 6: Level Sum ( ) . . . . . . . . . . . . . . . . . . . . . . . . 3738.2.7 Aufgabe 7: Tree Rotate ( ) . . . . . . . . . . . . . . . . . . . . . . . 3738.2.8 Aufgabe 8: Rekonstruktion ( ) . . . . . . . . . . . . . . . . . . . . 3748.2.9 Aufgabe 9: Math Evaluation ( ) . . . . . . . . . . . . . . . . . . . 3748.2.10 Aufgabe 10: Symmetrie ( ) . . . . . . . . . . . . . . . . . . . . . . . 3758.2.11 Aufgabe 11: Check Binary Search Tree ( ) . . . . . . . . . 3768.2.12 Aufgabe 12: Vollstandigkeit ( ) . . . . . . . . . . . . . . . . . . . . 3768.2.13 Aufgabe 13: Tree Printer ( ) . . . . . . . . . . . . . . . . . . . . . . 3788.3 Loesungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3818.3.1 Loesung 1: Tree Traversal ( ) . . . . . . . . . . . . . . . . . . . . . . 3818.3.2 Loesung 2: In-, Pre- und Postorder iterativ ( ) . . . . . . . . 3838.3.3 Loesung 3: Tree-Hoehe berechnen ( ) . . . . . . . . . . . . . . . 3908.3.4 Loesung 4: Kleinster gemeinsamer Vorfahre ( ) . . . . . . 3918.3.5 Loesung 5: Breadth-First ( ) . . . . . . . . . . . . . . . . . . . . . . . 3948.3.6 Loesung 6: Level Sum ( ) . . . . . . . . . . . . . . . . . . . . . . . . . 3968.3.7 Loesung 7: Tree Rotate ( ) . . . . . . . . . . . . . . . . . . . . . . . . 3998.3.8 Loesung 8: Rekonstruktion ( ) . . . . . . . . . . . . . . . . . . . . . 4028.3.9 Loesung 9: Math Evaluation ( ) . . . . . . . . . . . . . . . . . . . . 4078.3.10 Loesung 10: Symmetrie ( ) . . . . . . . . . . . . . . . . . . . . . . . . 4088.3.11 Loesung 11: Check Binary Search Tree ( ) . . . . . . . . . . 4138.3.12 Loesung 12: Vollstandigkeit ( ). . . . . . . . . . . . . . . . . . . . . 4158.3.13 Loesung 13: Tree Printer ( ) . . . . . . . . . . . . . . . . . . . . . . . 4239 Suchen und Sortieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4339.1 Einfuhrung Suchen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4339.1.1 Binarsuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4359.2 Einfuhrung Sortieren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4369.2.1 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4369.2.2 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4389.2.3 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4409.2.4 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4419.2.5 Bucket Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4439.2.6 Schlussgedanken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4449.3 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4459.3.1 Aufgabe 1: Contains All ( ) . . . . . . . . . . . . . . . . . . . . . . . 4459.3.2 Aufgabe 2: Partitionierung ( ). . . . . . . . . . . . . . . . . . . . . 4459.3.3 Aufgabe 3: Binarsuche ( ) . . . . . . . . . . . . . . . . . . . . . . . 4469.3.4 Aufgabe 4: Insertion Sort ( ) . . . . . . . . . . . . . . . . . . . . . 4469.3.5 Aufgabe 5: Selection Sort ( ) . . . . . . . . . . . . . . . . . . . . . 4479.3.6 Aufgabe 6: Quick Sort ( ) . . . . . . . . . . . . . . . . . . . . . . . . 4479.3.7 Aufgabe 7: Bucket Sort ( ) . . . . . . . . . . . . . . . . . . . . . . . 4489.3.8 Aufgabe 8: Suche in rotierten Daten ( ) . . . . . . . . . . . . 448xiv Inhaltsverzeichnis9.4 Loesungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4509.4.1 Loesung 1: Contains All ( ) . . . . . . . . . . . . . . . . . . . . . . . . 4509.4.2 Loesung 2: Partitionierung ( ) . . . . . . . . . . . . . . . . . . . . . 4519.4.3 Loesung 3: Binarsuche ( ) . . . . . . . . . . . . . . . . . . . . . . . . 4539.4.4 Loesung 4: Insertion Sort ( ) . . . . . . . . . . . . . . . . . . . . . . 4569.4.5 Loesung 5: Selection Sort ( ) . . . . . . . . . . . . . . . . . . . . . . 4579.4.6 Loesung 6: Quick Sort ( ) . . . . . . . . . . . . . . . . . . . . . . . . . 4589.4.7 Loesung 7: Bucket Sort ( ) . . . . . . . . . . . . . . . . . . . . . . . . 4609.4.8 Loesung 8: Suche in rotierten Daten ( ) . . . . . . . . . . . . . 46110 Schlusswort und erganzende Literatur . . . . . . . . . . . . . . . . . . . . . . . . 46710.1 Schlusswort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46710.1.1 Gelerntes pro Kapitel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46710.1.2 Bedenkenswertes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46910.2 Knobelaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47110.2.1 Goldsacke - Falschung entdecken . . . . . . . . . . . . . . . . . . . . . . . 47110.2.2 Pferderennen - schnellste drei Pferde ermitteln . . . . . . . . . . . . 47210.3 Erganzende Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475III Anhang 479A Kurzeinfuhrung Pytest. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481A.1 Schreiben und Ausfuhren von Tests. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481A.1.1 Installation von Pytest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481A.1.2 Beispiel: Ein erster Unit Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482A.1.3 Ausfuhren von Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482A.1.4 Behandlung erwarteter Exceptions . . . . . . . . . . . . . . . . . . . . . . . 484A.1.5 Parametrisierte Tests mit Pytest . . . . . . . . . . . . . . . . . . . . . . . . . . 485A.2 Weiterfuhrende Literatur zu Pytest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486B Kurzeinfuhrung Dekoratoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487C Schnelleinstieg O-Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493C.1 Abschatzungen mit der O-Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493C.1.1 Komplexitatsklassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494C.1.2 Komplexitat und Programmlaufzeit . . . . . . . . . . . . . . . . . . . . . . . 496Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499Michael Inden is an Oracle-certified Java developer with over 20 years of professional experience designing complex software systems for international companies. There, he has worked in various roles such as SW developer, SW architect, consultant, team leader, CTO, head of academy, and trainer. Currently, he is working as a freelancer.
His special interests are creating high-quality applications with ergonomic GUIs, developing and solving programming puzzles, and coaching. He likes to pass on his knowledge and has led various courses and talks, both internally and externally, as well as at conferences such as JAX/W-JAX, JAX London, and Oracle Code One.
Besides, he is also an author of technical books. His german books, among others "Der Weg zum Java-Profi", Java Challenge", "Python Challenge" are all published by dpunkt.verlag.
