อัลกอริทึมและโครงสร้างข้อมูล
ฉันตั้งใจจะใช้ที่เก็บนี้เป็นสนามเด็กเล่น (KATA) รวมถึงการเตือนความทรงจำของอัลกอริทึมทั่วไปที่เรียบง่าย แต่ทรงพลัง ที่สง่างามฉันจะใช้ตัวแปลงสัญญาณ Clojure ซึ่งเป็นเครื่องมือไฟฟ้าที่ยอดเยี่ยมในการประมวลผลลำดับ ในขณะที่เอกสารนี้อาจดูละเอียดถี่ถ้วน แต่ฉันตั้งใจจะใช้เป็นรายการที่ฉันสามารถกลับมาได้ตลอดเวลาเมื่อฉันต้องการเรียน ฉันยังไม่ได้ใช้ทุกอย่างที่ระบุไว้ที่นี่
รูปแบบการเขียน
รหัสที่นี่ไม่ได้มีรูปร่างในสไตล์ที่ฉันจะใช้สำหรับการเข้ารหัสระดับมืออาชีพ ทุกทีมมีวัฒนธรรมและความคิดเห็นเกี่ยวกับสไตล์รหัสและดีกว่าที่จะยึดติดกับแนวทางทั่วไปเหล่านี้ ยิ่งไปกว่านั้นโค้ดถูกเขียนขึ้นเป็นหลักเพื่ออ่านโดยคนอื่นหรือเราทุกคนจะเขียนโค้ดในแอสเซมบลีเพื่อประสิทธิภาพสูงสุดหากเรากำหนดเป้าหมายเฉพาะผู้อ่านเครื่องเท่านั้น รหัสที่ฉันเขียนเป็นส่วนหนึ่งของทีมมีจุดประสงค์เพื่อเขียนโดยคนอื่นในทีมนี้
รหัสที่นี่เขียนขึ้นในการเขียนโปรแกรม litterate ขอบคุณ Emacs และ Org-Mode หมายความว่ารหัสที่เขียนใน Clojure นั้นได้มาจากไฟล์ข้อความที่อธิบายเหตุผลที่อยู่เบื้องหลัง ฉันหวังว่ามันจะทำให้อ่านง่ายขึ้น
งูหลาม
เตรียมพร้อมสำหรับปัญหาใหม่
./dev-resources/new-problem.sh
--problem-path neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups
ดู --help
เมื่อสคริปต์เริ่มต้นเสร็จสิ้นคำสั่งที่แนะนำสำหรับการทดสอบจะปรากฏขึ้นในตอนท้าย:
poetry run ptw -- --
src/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups.py
tests/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups_test.py
โต้ตอบกับบทกวีและ pytest
ตัวอย่างเช่นในการดูการทดสอบในขณะที่กำลังพัฒนา:
poetry run ptw
poetry run ptw -- -- --memray
poetry run ptw -- -- --benchmark-only
poetry run ptw -- -- --benchmark-skip
การเต้นรำเล็ก ๆ น้อย ๆ -- -- อาจหลีกเลี่ยงได้ แต่ฉันชอบที่จะชัดเจนมากเกี่ยวกับการวิ่งดังนั้นฉันจึงเก็บ poetry ไว้เป็นข้อโต้แย้งด้านหน้าซ้ายสุด
เพื่อรับหน่วยความจำ flamegraph:
poetry run memray run -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4 "
poetry run python -m memray flamegraph memray-neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate.554244.bin
เพื่อรับ CPU FlameGraph (หรือกราฟอื่น ๆ ):
poetry run python -m cProfile -o program.prof -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4, 4 "
poetry run snakeviz program.prof
ในการเรียกใช้มาตรฐานและรับบทสรุปกราฟิก:
poetry run pytest --benchmark-only --benchmark-histogram
รายการศึกษา
การเรียงลำดับอัลกอริทึม
- นำไปใช้ตั้งแต่เริ่มต้น: การเรียงลำดับฟอง, การเรียงลำดับ, เรียงลำดับอย่างรวดเร็ว, เรียงลำดับฮีป
- ได้รับอาร์เรย์ของจำนวนเต็มค้นหาองค์ประกอบที่เล็กที่สุด kth โดยใช้อัลกอริทึมเลือกอย่างรวดเร็ว
- ใช้อัลกอริทึมการเรียงลำดับการนับเพื่อเรียงลำดับอาร์เรย์ของจำนวนเต็มที่มีช่วงของค่าที่ทราบ
- แก้ปัญหา "พาร์ติชันสามทาง" โดยใช้การเรียงลำดับอย่างรวดเร็วเพื่อจัดเรียงอาร์เรย์ที่มีค่าที่ซ้ำกันอย่างมีประสิทธิภาพ
การค้นหาอัลกอริทึม
- นำไปใช้ตั้งแต่เริ่มต้น: การค้นหาแบบไบนารี (สำหรับอาร์เรย์ที่เรียงลำดับ), การค้นหาเชิงเส้น
- ให้อาร์เรย์ที่เรียงลำดับหมุนให้ค้นหาองค์ประกอบเป้าหมายโดยใช้การค้นหาไบนารีที่แก้ไขแล้ว
กราฟต้นไม้และอัลกอริทึมของการสำรวจ
- นำไปใช้ตั้งแต่เริ่มต้น: การค้นหาแบบกว้างก่อน (BFS), การค้นหาเชิงลึกครั้งแรก (DFS), อัลกอริทึมของ Dijkstra, อัลกอริทึม Bellman-Ford
- ใช้การเป็นตัวแทนที่แตกต่างกัน: matrix adjacency, adjacency list
- ค้นหาเส้นทางที่สั้นที่สุดระหว่างสองโหนดในกราฟถ่วงน้ำหนักโดยใช้อัลกอริทึมของ Dijkstra
- ใช้แผนผังการค้นหาแบบไบนารีและดำเนินการพื้นฐานเช่นการแทรกการลบและการค้นหา
- ให้กราฟกำกับตรวจสอบว่ามีเส้นทางระหว่างสองโหนดหรือไม่
- ค้นหาจำนวนส่วนประกอบที่เชื่อมต่อในกราฟที่ไม่ได้บอกทิศทาง
- ใช้การเรียงลำดับทอพอโลยีสำหรับกราฟอะซิเคลิคกำกับ (DAG)
- ค้นหาบรรพบุรุษที่ต่ำที่สุด (LCA) ของสองโหนดในต้นไม้ไบนารี
- ให้ต้นไม้ไบนารีตรวจสอบว่าเป็นแผนผังไบนารีที่ถูกต้อง (BST) หรือไม่
- ให้กราฟค้นหาส่วนประกอบที่เชื่อมต่ออย่างยิ่ง (SCCs) ทั้งหมดโดยใช้อัลกอริทึมของ Kosaraju หรืออัลกอริทึมของ Tarjan
- ใช้อัลกอริทึม Floyd-Warshall เพื่อค้นหาเส้นทางที่สั้นที่สุดทั้งหมดในกราฟถ่วงน้ำหนัก
- ให้ต้นไม้ N-ary ให้ดำเนินการข้ามระดับการเดินทางหรือการสำรวจความลึกก่อน (เช่นการสั่งซื้อล่วงหน้า, โพสต์สั่ง)
การเขียนโปรแกรมแบบไดนามิก
- การทำความเข้าใจแนวคิดของการทำลายปัญหาให้เป็นปัญหาย่อยที่ซ้อนทับกันขนาดเล็กและใช้การบันทึกความทรงจำหรือการจัดตาราง
- แก้ปัญหา "Fibonacci" แบบคลาสสิกโดยใช้วิธีการเขียนโปรแกรมแบบเรียกซ้ำและแบบไดนามิก
- ด้วยชุดของรายการที่มีน้ำหนักและค่าให้ค้นหาค่าสูงสุดที่สามารถรับได้ด้วยน้ำหนักสูงสุดที่กำหนดโดยใช้ปัญหา 0-1 knapsack
อัลกอริทึมโลภ
- การทำความเข้าใจปัญหาที่การเลือกตัวเลือกที่ดีที่สุดในท้องถิ่นนำไปสู่การแก้ปัญหาที่ดีที่สุดทั่วโลก
- ใช้โซลูชันสำหรับ "ปัญหาการเลือกกิจกรรม" ซึ่งคุณต้องเลือกจำนวนกิจกรรมสูงสุดที่ไม่ทับซ้อนกัน
- เมื่อพิจารณาชุดของเหรียญที่มีนิกายที่แตกต่างกันและจำนวนเงินให้ค้นหาจำนวนเหรียญขั้นต่ำที่จำเป็นในการสร้างจำนวนเงินนั้นโดยใช้วิธีโลภ
อัลกอริทึมการย้อนรอย
- แก้ปัญหา "n-queens" เพื่อวาง n ควีนส์บนกระดานหมากรุก n × n โดยไม่โจมตีซึ่งกันและกัน
- ใช้ Sudoku Solver เพื่อแก้ปริศนา Sudoku ที่เต็มไปด้วยบางส่วน
อัลกอริทึมการจัดการสตริง
- การจับคู่สตริง
- การพลิกกลับของสตริง
- ตรวจสอบ Palindrome
- ให้สองสตริงตรวจสอบว่ามีการเปลี่ยนแปลงของอีกสายหนึ่งหรือไม่
- ใช้อัลกอริทึม "Rabin-Karp" เพื่อค้นหารูปแบบในข้อความที่กำหนด
อัลกอริทึมการจัดการบิต
- การดำเนินการ bitwise ค้นหาองค์ประกอบที่ไม่ซ้ำกันเดียวในอาร์เรย์
- ได้รับอาร์เรย์ที่ตัวเลขทั้งหมดเกิดขึ้นสองครั้งยกเว้นหมายเลขหนึ่งให้ค้นหาหมายเลขที่ไม่ซ้ำเดียว
- ใช้ฟังก์ชันเพื่อนับจำนวนบิตที่ตั้งค่าเป็น 1 ในจำนวนเต็ม
อัลกอริทึมแบ่งและพิชิต
- การค้นหาแบบไบนารีค้นหาผลรวม subarray สูงสุด
- ใช้อัลกอริทึม Karatsuba สำหรับการคูณจำนวนเต็มขนาดใหญ่อย่างรวดเร็ว
- ค้นหาจุดที่ใกล้เคียงที่สุดในชุดของจุดในพื้นที่ 2D โดยใช้วิธีการหารและพิชิต
อัลกอริทึมแบบสุ่ม
- สับเปลี่ยนอาร์เรย์แบบสุ่มในสถานที่
- ใช้อัลกอริทึม "สุ่มเลือก" เพื่อค้นหาองค์ประกอบที่เล็กที่สุด kth ในอาร์เรย์
เทคนิคการเลื่อนหน้าต่าง
- ได้รับอาร์เรย์ของจำนวนเต็มค้นหาผลรวมสูงสุดของ subarray ที่ต่อเนื่องกันขนาด K
- ค้นหาสตริงย่อยที่ยาวที่สุดที่มีอักขระที่แตกต่าง k ส่วนใหญ่ในสตริงที่กำหนด
ปัญหาช่วงเวลา
- ให้รายการช่วงเวลารวมช่วงเวลาที่ทับซ้อนกัน
- ค้นหาจำนวนห้องประชุมขั้นต่ำที่จำเป็นในการกำหนดเวลาของช่วงเวลา
พยายาม
- ใช้โครงสร้างข้อมูล Trie สำหรับการค้นหาสตริงที่มีประสิทธิภาพและการดึงข้อมูล
- ให้รายการคำศัพท์ค้นหาคำนำหน้าทั่วไปที่ยาวที่สุดโดยใช้ Trie
- ใช้คุณสมบัติการเติมข้อความอัตโนมัติโดยใช้ Trie สำหรับชุดคำที่กำหนด
- ให้รายการคำศัพท์ค้นหาคู่คำทั้งหมดเพื่อให้การต่อกันเป็นรูปแบบ palindrome
การแฮม
- การใช้ฟังก์ชั่นแฮชเทคนิคการแก้ไขการชนและกรณีการใช้งาน
- ใช้ตารางแฮชที่มีความละเอียดการชนกัน (เช่นการผูกมัดหรือการเปิดที่อยู่)
- ค้นหาอักขระที่ไม่ซ้ำครั้งแรกในสตริงโดยใช้แผนที่แฮช
- ใช้อัลกอริทึม Rabin-Karp สำหรับการจับคู่สตริงที่มีหลายรูปแบบ
- ค้นหาสตริงย่อยที่ยาวที่สุดโดยไม่ต้องทำซ้ำอักขระโดยใช้แผนที่แฮชสำหรับความถี่อักขระ
กอง
- การใช้งาน Min-heaps และ Max-heaps และแอปพลิเคชันของพวกเขา (เช่นคิวลำดับความสำคัญ)
- ใช้ Min-heap หรือ Max-heap ตั้งแต่เริ่มต้น
- ให้องค์ประกอบอาร์เรย์ค้นหาองค์ประกอบที่ใหญ่ที่สุด Kth โดยใช้วิธีการที่ใช้ฮีป
การจัดการเมทริกซ์
- ให้เมทริกซ์ M × N หมุนไปที่ 90 องศาในสถานที่
- ให้เมทริกซ์ของ 0s และ 1s ค้นหาสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุดของ 1s (เมทริกซ์ย่อยขนาดสูงสุด) และส่งคืนพื้นที่
ต้นไม้สีแดงดำหรือต้นไม้ AVL
- ใช้การแทรกและการลบสำหรับต้นไม้สีแดงดำหรือต้นไม้ AVL
- ทำการหมุนเพื่อสร้างสมดุลระหว่างแผนผังไบนารีที่ไม่สมดุล
การใช้งานโครงสร้างข้อมูล
- อาร์เรย์และรายการ: การใช้อาร์เรย์, รายการที่เชื่อมโยงและการดำเนินงานของพวกเขา
- สแต็คและคิว: การใช้โครงสร้างข้อมูลสแต็กและคิวและแอปพลิเคชันของพวกเขา
- แผนที่แฮช: การใช้แผนที่แฮชและทำความเข้าใจกับความซับซ้อนของเวลา
เครื่องมือ
อัลกอริทึมและโครงสร้างข้อมูลจะถูกเปิดเผยโดย API ที่เรียบง่ายสำหรับการตั้งค่าที่สมจริงยิ่งขึ้นและสำหรับการทดสอบที่แข็งแกร่งยิ่งขึ้น:
(เครื่องมือที่ระบุไว้ที่นี่อาจเฉพาะเจาะจงสำหรับบางภาษา)
