Algoritma dan struktur data
Saya bermaksud menggunakan repositori ini sebagai taman bermain latihan (Kata) serta pengingat beberapa algoritma yang umum, sederhana, namun kuat. Di mana saya akan menggunakan transduser clojure, yang merupakan alat listrik yang bagus untuk memproses urutan. Meskipun dokumen ini mungkin tampak lengkap, saya bermaksud menggunakannya sebagai daftar yang dapat saya kembalikan kapan saja ketika saya perlu belajar. Saya belum menerapkan semua yang tercantum di sini.
Gaya penulisan
Kode di sini tidak berbentuk dalam gaya yang akan saya gunakan untuk pengkodean profesional. Setiap tim memiliki beberapa budaya dan pendapat tentang gaya kode dan lebih baik untuk tetap berpegang pada pedoman umum ini. Selain itu kode ditulis terutama untuk dibaca oleh orang lain, atau kita semua akan kode dalam perakitan untuk kinerja maksimum jika kita hanya menargetkan pembaca mesin. Kode yang saya tulis sebagai bagian dari tim yang dimaksudkan mungkin ditulis oleh orang lain di tim ini.
Kode di sini ditulis dalam pemrograman berserakan berkat Emacs dan org-mode. Ini berarti kode yang ditulis dalam Clojure berasal dari file teks yang menjelaskan alasan di baliknya. Saya harap ini membuatnya lebih mudah dibaca.
Python
Bersiap untuk masalah baru
./dev-resources/new-problem.sh
--problem-path neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups
Lihat --help .
Ketika skrip inisialisasi selesai, perintah yang disarankan untuk tes akan muncul di akhir:
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
Berinteraksi dengan puisi dan pytest
Misalnya, untuk menonton tes saat mengembangkan:
poetry run ptw
poetry run ptw -- -- --memray
poetry run ptw -- -- --benchmark-only
poetry run ptw -- -- --benchmark-skip
Tarian kecil di sekitar -- -- mungkin bisa dihindari tetapi saya lebih suka menjadi sangat eksplisit tentang apa yang berjalan, jadi saya menjaga poetry sebagai argumen depan paling kiri.
Untuk mendapatkan Flamegraph memori:
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
Untuk mendapatkan CPU Flamegraph (atau grafik lainnya):
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
Untuk menjalankan tolok ukur dan mendapatkan ringkasan grafis:
poetry run pytest --benchmark-only --benchmark-histogram
Daftar Studi
Algoritma penyortiran
- Implement dari awal: Bubble Sort, Gabungkan Sortir, Sortir Cepat, Sortir Tumpukan.
- Diberikan berbagai bilangan bulat, temukan elemen terkecil K menggunakan algoritma pilih cepat.
- Menerapkan algoritma penghitungan untuk mengurutkan array bilangan bulat dengan rentang nilai yang diketahui.
- Selesaikan masalah "partisi tiga arah" menggunakan jenis cepat untuk mengurutkan array dengan nilai duplikat secara efisien.
Algoritma pencarian
- Implement dari awal: pencarian biner (untuk array yang diurutkan), pencarian linier.
- Diberi array yang diurutkan, temukan elemen target menggunakan pencarian biner yang dimodifikasi.
Grafik, pohon, dan algoritma traversal daripadanya
- Implement dari awal: pencarian luas-pertama (BFS), pencarian kedalaman-pertama (DFS), algoritma Dijkstra, algoritma Bellman-Ford.
- Menerapkan representasi yang berbeda: matriks adjacency, daftar adjacency.
- Temukan jalur terpendek antara dua node dalam grafik tertimbang menggunakan algoritma Dijkstra.
- Menerapkan pohon pencarian biner dan melakukan operasi dasar seperti penyisipan, penghapusan, dan pencarian.
- Diberi grafik yang diarahkan, periksa apakah ada rute antara dua node.
- Temukan jumlah komponen yang terhubung dalam grafik yang tidak diarahkan.
- Menerapkan penyortiran topologi untuk grafik asiklik terarah (DAG).
- Temukan leluhur umum terendah (LCA) dari dua node di pohon biner.
- Diberikan pohon biner, periksa apakah itu adalah pohon pencarian biner yang valid (BST).
- Diberi grafik, temukan semua komponen yang sangat terhubung (SCC) menggunakan algoritma Kosaraju atau algoritma Tarjan.
- Menerapkan algoritma Floyd-Warshall untuk menemukan jalur terpendek semua pasangan dalam grafik tertimbang.
- Diberikan pohon N-ary, lakukan traversal tingkat tingkat atau traversal kedalaman-pertama (misalnya, pre-order, pasca-pesanan).
Pemrograman Dinamis
- Memahami konsep memecah masalah menjadi subproblem yang lebih kecil yang tumpang tindih dan menggunakan memoisasi atau tabulasi.
- Selesaikan masalah "Fibonacci" klasik menggunakan pendekatan pemrograman rekursif dan dinamis.
- Diberi satu set item dengan bobot dan nilai, temukan nilai maksimum yang dapat diperoleh dengan bobot maksimum yang diberikan menggunakan masalah 0-1 ransel.
Algoritma serakah
- Memahami masalah di mana membuat pilihan optimal lokal mengarah ke solusi optimal global.
- Menerapkan solusi untuk "masalah pemilihan aktivitas" di mana Anda perlu memilih jumlah maksimum kegiatan yang tidak tumpang tindih.
- Diberi satu set koin dengan denominasi yang berbeda dan jumlah, temukan jumlah minimum koin yang diperlukan untuk membuat jumlah itu menggunakan pendekatan serakah.
Algoritma backtracking
- Selesaikan masalah "N-Queens" untuk menempatkan N Queens pada papan catur N × N tanpa saling menyerang.
- Menerapkan pemecah Sudoku untuk memecahkan teka -teki Sudoku yang diisi sebagian.
Algoritma manipulasi string
- Pencocokan string
- Pembalikan string
- Cek palindrome
- Diberi dua string, periksa apakah yang satu adalah permutasi yang lain.
- Menerapkan algoritma "Rabin-karp" untuk menemukan pola dalam teks yang diberikan.
Algoritma manipulasi bit
- Operasi Bitwise, menemukan elemen unik tunggal dalam array.
- Diberi array di mana semua angka terjadi dua kali kecuali untuk satu angka, temukan nomor unik tunggal.
- Menerapkan fungsi untuk menghitung jumlah bit yang ditetapkan ke 1 dalam bilangan bulat.
Bagilah dan menaklukkan algoritma
- Pencarian biner, menemukan jumlah subarray maksimum.
- Menerapkan algoritma Karatsuba untuk multiplikasi cepat bilangan bulat besar.
- Temukan sepasang poin terdekat di antara satu set poin dalam ruang 2D menggunakan pendekatan Divide and Conquer.
Algoritma acak
- Mengocok array secara acak di tempat.
- Menerapkan algoritma "Pilih Acak" untuk menemukan elemen terkecil K dalam array.
Teknik Jendela Geser
- Diberi berbagai bilangan bulat, temukan jumlah maksimum dari setiap subarray yang berdekatan dari ukuran k.
- Temukan substring terpanjang dengan paling banyak karakter berbeda dalam string yang diberikan.
Masalah interval
- Diberikan daftar interval, gabungkan interval yang tumpang tindih.
- Temukan jumlah minimum ruang pertemuan yang diperlukan untuk menjadwalkan daftar interval.
Mencoba
- Menerapkan struktur data trie untuk pencarian dan pengambilan string yang efisien.
- Diberi daftar kata -kata, temukan awalan umum terpanjang menggunakan trie.
- Menerapkan fitur AutoComplete menggunakan trie untuk serangkaian kata yang diberikan.
- Diberikan daftar kata -kata, temukan semua pasangan kata sedemikian rupa sehingga gabungan membentuk palindrom.
Hashing
- Menerapkan fungsi hash, teknik resolusi tabrakan, dan kasus penggunaan.
- Menerapkan tabel hash dengan resolusi tabrakan (misalnya, rantai atau pengalamatan terbuka).
- Temukan karakter non-diulang pertama dalam string menggunakan peta hash.
- Menerapkan algoritma Rabin-Karp untuk pencocokan string dengan beberapa pola.
- Temukan substring terpanjang tanpa karakter berulang menggunakan peta hash untuk frekuensi karakter.
Tumpukan
- Menerapkan Min-Haps dan Max-Heaps dan Aplikasi mereka (misalnya, antrian prioritas).
- Menerapkan Min-Heap atau Max-Heap dari awal.
- Diberi berbagai elemen, temukan elemen terbesar K menggunakan pendekatan berbasis heap.
Manipulasi matriks
- Diberi matriks M × N, putar 90 derajat di tempat.
- Diberikan matriks 0s dan 1s, temukan kuadrat terbesar 1s (sub-matriks persegi ukuran maksimum) dan kembalikan luasnya.
Pohon Merah Hitam atau Pohon AVL
- Menerapkan operasi penyisipan dan penghapusan untuk pohon merah-hitam atau pohon AVL.
- Lakukan rotasi untuk menyeimbangkan pohon pencarian biner yang tidak seimbang.
Implementasi Struktur Data
- Array dan Daftar: Menerapkan array, daftar tertaut, dan operasinya.
- Tumpukan dan antrian: Menerapkan struktur data tumpukan dan antrian dan aplikasinya.
- Hash Maps: Menerapkan peta hash dan memahami kompleksitas waktu mereka.
Peralatan
Algoritma dan struktur data diekspos oleh API Restful sederhana untuk pengaturan yang lebih realistis dan untuk tes yang lebih kuat:
(Alat yang tercantum di sini mungkin khusus untuk beberapa bahasa)
