الخوارزميات وهياكل البيانات
أنوي استخدام هذا المستودع كملعب تدريبي (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
للحصول على وحدة المعالجة المركزية 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.
- تنفيذ تمثيلات مختلفة: مصفوفة مجاورة ، قائمة المجاورة.
- ابحث عن أقصر مسار بين العقدتين في رسم بياني مرجح باستخدام خوارزمية Dijkstra.
- قم بتنفيذ شجرة بحث ثنائية وتنفيذ العمليات الأساسية مثل الإدراج والحذف والبحث.
- بالنظر إلى رسم بياني موجه ، تحقق مما إذا كان هناك طريق بين العقدتين.
- ابحث عن عدد المكونات المتصلة في رسم بياني غير موجه.
- تنفيذ الفرز الطوبولوجي للرسم البياني الموجه (DAG).
- ابحث عن أدنى سلف مشترك (LCA) لعقدتين في شجرة ثنائية.
- بالنظر إلى شجرة ثنائية ، تحقق مما إذا كانت شجرة بحث ثنائية صالحة (BST).
- بالنظر إلى الرسم البياني ، ابحث عن جميع المكونات المتصلة بقوة (SCCs) باستخدام خوارزمية Kosaraju أو خوارزمية Tarjan.
- قم بتنفيذ خوارزمية Floyd-Warshall للعثور على أقصر المسارات في رسم بياني مرجح.
- بالنظر إلى شجرة N-ary ، قم بإجراء اجتياز من الدرجة الأولى أو اجتياز العمق الأول (على سبيل المثال ، الطلب المسبق ، بعد الطلب).
البرمجة الديناميكية
- فهم مفهوم تقسيم المشكلة إلى مشكلات فرعية متداخلة أصغر واستخدام المذكرات أو الجدولة.
- حل مشكلة "Fibonacci" الكلاسيكية باستخدام مقاربات البرمجة المتكررة والديناميكية.
- بالنظر إلى مجموعة من العناصر ذات الأوزان والقيم ، ابحث عن الحد الأقصى للقيمة التي يمكن الحصول عليها بأقصى قدر من الوزن باستخدام مشكلة knapsack 0-1.
خوارزميات الجشع
- يؤدي فهم المشكلات حيث يؤدي اتخاذ الخيارات المثلى محليًا إلى حل مثالي عالميًا.
- قم بتنفيذ حل لـ "مشكلة اختيار النشاط" حيث تحتاج إلى تحديد الحد الأقصى لعدد الأنشطة التي لا تتداخل.
- بالنظر إلى مجموعة من العملات المعدنية ذات الطوائف المختلفة وكمية ، ابحث عن الحد الأدنى لعدد العملات المعدنية اللازمة لجعل هذا المبلغ باستخدام النهج الجشع.
خوارزميات التراجع
- حل مشكلة "n-queens" لوضع N Queens على لوحة N × N دون مهاجمة بعضها البعض.
- تنفيذ Sudoku Solver لحل لغز Sudoku شغله جزئيًا.
خوارزميات معالجة السلسلة
- سلسلة مطابقة
- انعكاس السلسلة
- الشيكات باليندروم
- بالنظر إلى سلسلتين ، تحقق مما إذا كان أحدهما عبارة عن تقليب الآخر.
- قم بتنفيذ خوارزمية "Rabin-Karp" لإيجاد نمط في نص معين.
خوارزميات التلاعب بت
- عمليات bitwise ، إيجاد عنصر فريد واحد في صفيف.
- بالنظر إلى صفيف حيث تحدث جميع الأرقام مرتين باستثناء رقم واحد ، ابحث عن الرقم الفريد المفرد.
- قم بتنفيذ وظيفة لحساب عدد البتات التي يتم تعيينها على 1 في عدد صحيح.
تقسيم الخوارزميات وقهرها
- البحث الثنائي ، إيجاد الحد الأقصى لمجموع الجوس الفرعي.
- قم بتنفيذ خوارزمية Karatsuba للضرب السريع للأعداد الصحيحة الكبيرة.
- ابحث عن أقرب زوج من النقاط بين مجموعة من النقاط في مساحة ثنائية الأبعاد باستخدام نهج الفجوة والقهر.
خوارزميات عشوائية
- خلط صفيف عشوائيا في مكان.
- قم بتنفيذ خوارزمية "اختيار عشوائي" للعثور على عنصر KTH الأصغر في صفيف.
تقنية النافذة المنزلق
- بالنظر إلى مجموعة من الأعداد الصحيحة ، ابحث عن الحد الأقصى لمجموع أي جهاز فرعي متجاور بحجم k.
- ابحث عن أطول فرعية مع أحرف K مميزة في معظم K في سلسلة معينة.
مشاكل الفاصل
- بالنظر إلى قائمة الفواصل الزمنية ، دمج فترات متداخلة.
- ابحث عن الحد الأدنى لعدد غرف الاجتماعات المطلوبة لجدولة قائمة الفواصل الزمنية.
يحاول
- قم بتنفيذ بنية بيانات TRIE للبحث عن سلسلة فعالة واسترجاعها.
- بالنظر إلى قائمة الكلمات ، ابحث عن أطول بادئة شائعة باستخدام Trie.
- قم بتنفيذ ميزة الإكمال التلقائي باستخدام trie لمجموعة معينة من الكلمات.
- بالنظر إلى قائمة بالكلمات ، ابحث عن كل أزواج الكلمات بحيث تشكل التسلسل palindrome.
التجزئة
- تنفيذ وظائف التجزئة ، وتقنيات حل الاصطدام ، وحالات الاستخدام.
- قم بتنفيذ جدول التجزئة مع دقة التصادم (على سبيل المثال ، التسلسل أو المفتوح العنوان).
- ابحث عن أول حرف غير متكرر في سلسلة باستخدام خريطة التجزئة.
- قم بتنفيذ خوارزمية Rabin-Karp لمطابقة السلسلة مع أنماط متعددة.
- ابحث عن أطول فرعية دون تكرار الأحرف باستخدام خريطة التجزئة لتردد الأحرف.
أكوام
- تنفيذ Heaps و Max-Heaps وتطبيقاتها (على سبيل المثال ، قوائم قوائم الأولوية).
- قم بتنفيذ Min-Heap أو Max-Heap من الصفر.
- بالنظر إلى مجموعة من العناصر ، ابحث عن العنصر الأكبر KTH باستخدام نهج قائم على الكومة.
التلاعب المصفوفة
- بالنظر إلى مصفوفة M × N ، قم بتدويرها بمقدار 90 درجة في مكانها.
- بالنظر إلى مصفوفة من 0S و 1S ، ابحث عن أكبر مربع من 1S (مصفوفة فرعية مربعة بحجم الحد الأقصى) وإرجاع منطقتها.
أشجار أسود أحمر أو أشجار AVL
- قم بتنفيذ عمليات الإدراج والحذف لشجرة سوداء حمراء أو شجرة AVL.
- أداء الدورات لتحقيق التوازن بين شجرة البحث الثنائية غير متوازنة.
تطبيقات بنية البيانات
- المصفوفات والقوائم: تنفيذ المصفوفات والقوائم المرتبطة وعملياتها.
- الكدسات وقوائم الانتظار: تنفيذ هياكل بيانات المكدس وقائمة الانتظار وتطبيقاتها.
- خرائط التجزئة: تنفيذ خرائط التجزئة وفهم تعقيد الوقت.
أدوات
تتعرض الخوارزميات وهياكل البيانات من خلال واجهة برمجة تطبيقات بسيطة لإعداد أكثر واقعية واختبار أكثر قوة:
(قد تكون الأدوات المدرجة هنا خاصة ببعض اللغات)
