Solusi LeetCode dengan Gaya yang Baik

Dokumen ini memberikan gambaran komprehensif tentang LeetCode-Solutions-in-Good-Style, sumber daya yang menawarkan tutorial ramah pemula dan solusi video untuk masalah algoritma dan struktur data. Dokumen ini menampilkan pendekatan terstruktur dengan kode yang jelas, penjelasan mendetail, dan fokus pada pembangunan pemahaman yang kuat tentang konsep dasar daripada pengkodean kompetitif.

LeetCode-Solusi-dalam-Gaya-Baik

Penjelasan: Seperti kebanyakan teman sekelas saya, saya belajar dan merangkum pada saat yang bersamaan. Saya akan mencoba berbagi lebih banyak dan memberikan Anda beberapa pengetahuan yang bermanfaat. Terima kasih atas dukungan Anda yang tiada henti.

Halo semuanya, ini adalah tutorial tingkat pemula tentang "Algoritma dan Struktur Data". Cocok untuk siswa yang tidak memiliki dasar dalam algoritme dan siswa yang telah berganti karier. Tidak cocok untuk persiapan kompetisi algoritme. Hal yang ingin saya sampaikan adalah: tulis kode dengan logika yang jelas, jadi kode yang saya tulis harus melalui pemikiran yang matang. Formatnya sangat standar, tanpa gaya pribadi, dan saya tidak akan menulis baris kosong atau komentar untuk menguranginya jumlah baris kode. Ini dia:

Anda dapat memanggil saya weiwei. Saya akan mencoba yang terbaik untuk menjawab pertanyaan yang saya tahu sesuai kemampuan dan waktu saya. Jika Anda memiliki pertanyaan yang tidak dapat dijawab tepat waktu, mungkin karena saya tidak melihat notifikasi di situs. Anda dapat mengirimi saya email di [email protected].

Solusi video yang saya rekam

Saya mulai merekam solusi video pada bulan September 2019. Pada awalnya, saya akan mencatat materi yang ingin saya bicarakan beberapa kali. Sekarang tulislah draf kata demi kata saat menjelaskan poin pengetahuan. Banyak sekali video yang telah terkumpul, yang sebenarnya merupakan kursus sistematis kecil. Sekarang semuanya tercantum di sini. Saya harap dapat bermanfaat bagi semua orang.

0. Bagaimana cara pengguna algoritma pemula menggunakan LeetCode? 【Berbagi informasi berguna】

1. Kompleksitas waktu dan kompleksitas ruang

Video ini menyebutkan bahwa kompleksitas waktu merupakan konsep asimtotik dan perlu dipahami dari sudut pandang dinamis. Dan penjelasan tegas (bentuk batas) kompleksitas waktu dijelaskan sehingga setiap orang dapat memahami aturan perhitungan kompleksitas waktu. Hal ini juga menunjukkan: Kompleksitas waktu bukanlah waktu berjalannya program; "ruang untuk waktu" harus digunakan, dan lebih banyak perhatian harus diberikan untuk mengoptimalkan "kompleksitas waktu".

2. Pencarian biner

Video ini memperkenalkan cara menulis algoritma pencarian biner. Meskipun ada banyak detail tentang pencarian biner, selama kita menguasai ide pemecahan masalah yang benar, lebih banyak berlatih, berpikir dengan rajin, dan membuat lebih banyak ringkasan, masalah pencarian biner tidak akan ada. lagi menjadi kesulitan.

Video berikut menjelaskan beberapa contoh pertanyaan pencarian biner. Kami fokus pada menganalisis arti pertanyaan dan bagaimana menggunakan kondisi yang diberikan dalam pertanyaan untuk mempersempit rentang pencarian secara bertahap.

Melalui analisis pertanyaan 4 "Likou" (menemukan median dari dua array orde positif), kami memperkenalkan teknik ini kepada Anda: Jika properti elemen target yang Anda cari lebih kompleks, Anda dapat membalikkan properti ini. , lalu tulis pernyataan logis yang dapat dengan mudah mengurangi rentang masalah.

3. Masalah yang berkaitan dengan penyortiran

"Merge sort" dan "quick sort" adalah algoritma pengurutan yang sangat penting. Pemahaman yang mendalam tentang keduanya sangat membantu dalam memahami mekanisme pengoperasian fungsi "rekursif". ". "Pasangan urutan terbalik" dan "Masalah bendera Belanda (klasifikasi warna)" juga merupakan masalah algoritma yang sangat klasik.

Menghitung "pasangan urutan terbalik" sepenuhnya didasarkan pada gagasan "pengurutan gabungan".

Dalam penjelasan masalah "klasifikasi warna", kami memperkenalkan "loop invarian" kepada semua orang Dalam proses penulisan kode, kita harus selalu mematuhi semantik variabel yang digunakan, "sebelum eksekusi program" dan "selama eksekusi" Itu. tetap tidak berubah setelah "eksekusi berakhir". Mengikuti definisi kami sendiri tentang "loop invarian" adalah cara penting bagi kami untuk menulis kode yang benar.

"Bilangan positif pertama yang hilang" adalah masalah algoritma klasik. Ide yang digunakan adalah "hashing di tempat", yang dapat dipahami sebagai aplikasi khusus dari algoritma "pengurutan keranjang": satu wortel, satu lubang, dan satu ember. Simpan sebuah elemen. Saya ingin menekankan bahwa fakta bahwa Anda dapat melakukan ini berkaitan erat dengan nilai elemen array input.

4. Jendela geser

Masalah "jendela geser" adalah masalah umum yang diselesaikan dengan menerapkan "invarian loop", yang menguji kemampuan pengkodean dan debugging kami.

5. Tumpukan masalah terkait

Masalah yang diselesaikan dengan menggunakan "tumpukan" mengharuskan kita menggunakan contoh spesifik untuk menemukan bahwa penyelesaiannya sesuai dengan aturan "masuk terakhir, keluar pertama":

Menguasai dua soal berikut tidak terlepas dari mempelajari contoh-contoh spesifik kemudian merangkum kaidah umum.

Salah satu aplikasi "stack" yang paling banyak digunakan adalah sebagai pendukung struktur data untuk "rekursi", "traversal depth-first" dan "algoritma pembagian dan penaklukan".

6. Pencarian gabungan

Struktur data "Union Search Set" saat ini jarang digunakan dalam wawancara. Jika Anda sedang mempersiapkan wawancara algoritma, Anda dapat melewatinya.

7. pohon

Banyak permasalahan pohon yang dapat diselesaikan dengan menggunakan "traversal depth-first" atau "traversal broadth-first".

8. Algoritma penelusuran mundur

"Algoritme kemunduran" sebenarnya adalah penjelajahan mendalam pertama dari "struktur pohon" yang terdapat dalam pertanyaan. Saat mengerjakan soal jenis ini, penting untuk menggambar diagram struktur pohon di kertas coretan.

9. Pemrograman dinamis

10. Penyortiran topologi dan penjelajahan pertama luasnya

11. Tabel hash

12. Operasi bit terkait

Situs web pribadi saya dan catatan studi algoritma

Grup WeChat dan grup QQ

Jika Anda membutuhkan teman untuk mengerjakan soal bersama, Anda dapat bergabung dengan grup WeChat dan grup QQ.

Buku Leet Saya

Ini adalah promosi untuk diri saya sendiri. Saya baru-baru ini meluncurkan LeetBook saya sendiri di "LeetBook": Mempelajari Algoritma dari Nol (sebelumnya dikenal sebagai "Mempelajari Algoritma dan Struktur Data dengan "LeetCoin")", yang ditujukan terutama untuk teman-teman yang telah berganti karier dan telah berganti karier. landasan nol. Menjelaskan pengetahuan dasar algoritma dan struktur data.

menjelaskan:

Dua bab pertama LeetBook (Kompleksitas Waktu, Pencarian Biner) gratis untuk dibaca. Bab-bab berikut memerlukan pembayaran untuk membacanya. Harga non-anggota adalah 99 yuan dan harga anggota adalah 69 yuan sama seperti LeetBook. Hanya bagian tambahannya, tidak kurang;

Judul kursus LeetBook, contoh, latihan, dan repositori kode pendukung (repositori yang sedang Anda lihat) sepenuhnya bersifat publik. Jika Anda sudah menguasai konten (termasuk latihan) yang dirancang di LeetBook, tidak disarankan untuk membelinya;

Tenaga yang diinvestasikan sama dengan menulis solusi biasanya, hanya saja LeetBook akan lebih detail dalam membuat grafik. Konten berbayar adalah: waktu dan tenaga yang dikeluarkan untuk membuat tutorial, serta partisipasi staf dan ahli "Likou" dalam produksi dan review, pengalaman membaca akan lebih baik. Tidak menutup kemungkinan bahwa saya biasanya menulis lebih banyak poin pengetahuan pemecahan masalah daripada LeetBook;

Pengguna tingkat menengah dan lanjutan harap membeli dengan hati-hati;

Anda dapat berkonsultasi dengan saya tentang konten kursus di situs "Likou" atau akun sosial saya yang lain, atau Anda dapat mengirimkan masalah ke gudang ini. Terlepas dari apakah saya membeli kursus atau tidak, saya akan mencoba yang terbaik untuk menjawab pertanyaan-pertanyaan yang saya tahu (jika waktu mengizinkan dan sesuai kemampuan saya). Terima kasih atas dukungan Anda yang berkelanjutan kepada saya. Setiap orang dipersilakan untuk berkomunikasi dengan saya jika Anda memiliki saran dan pendapat;

Ilmu yang saya jelaskan ada di buku-buku yang saya rekomendasikan kepada semua orang, blog, solusi masalah, dan catatan yang saya tulis. Solusi masalah, blog, dan catatan yang saya terbitkan akan selalu saya bagikan, dan selama saya punya waktu dan tenaga, . Saya akan terus melakukannya.

Saya sangat berterima kasih kepada "Likou" karena telah memberi saya kesempatan untuk mengambil kursus dan membantu saya memenuhi keinginan kecil saya.

Direktori klasifikasi dan solusi masalah "Lekou" (disusun menurut bab LeetBook, Bab 16 dan seterusnya adalah bab yang saat ini tidak termasuk dalam LeetBook)

Catatan: Kategori pertanyaan sesuai dengan bab LeetBook saya.

Bab 1 Kompleksitas Waktu

Bagian ini memperkenalkan konsep kompleksitas waktu. Anda dapat menonton [Penjelasan Video], yang sepenuhnya gratis. Tidak ada latihan untuk bab ini.

Bab 2 Pencarian Biner

Jenis Pertanyaan 1: Temukan subskrip dalam dua poin

menjelaskan:

praktik:

Jenis Pertanyaan 2: Tentukan bilangan bulat dengan rentang dua poin (jawaban dua poin)

Pemikiran algoritmik: kurangi dan taklukkan. Jika pertanyaannya mengharuskan kita mencari bilangan bulat, dan bilangan bulat tersebut memiliki rentang tertentu, kita dapat secara bertahap mempersempit rentang tersebut melalui pencarian biner, dan akhirnya mendekatinya ke suatu angka.

Jenis pertanyaan 3: Fungsi diskriminan kompleks (masalah maksimalisasi)

Catatan: Jenis pertanyaan ini pada dasarnya adalah "Jenis Pertanyaan 2" (jawaban dua poin), namun mungkin terasa sedikit membingungkan saat pertama kali mempelajarinya. Pertanyaan jenis ini ditanyakan dengan cara yang sama. Kata kuncinya adalah "kontinu" dan "bilangan bulat positif". Harap perhatikan untuk menangkap informasi penting tersebut dalam pertanyaan.

Bab 3 Algoritma Dasar Penyortiran

Bagian ini berisi empat algoritma pengurutan dasar: pengurutan pilihan, pengurutan penyisipan, pengurutan bukit, dan pengurutan gelembung.

Pertanyaan "Likou" 912: Solusi untuk array yang diurutkan: Ini merangkum beberapa poin penting dan materi pembelajaran untuk masalah pengurutan. Anda dapat mulai mempelajari algoritma dari masalah pengurutan.

Permasalahan array dapat dijadikan sebagai “bidang pemula” dalam algoritma, karena permasalahan tersebut hanya dapat diselesaikan dengan menguasai pengetahuan dasar bahasa pemrograman. Sangat mudah untuk memikirkan solusi untuk masalah berikut, bahkan jika Anda belum mempelajari struktur data dan pengetahuan algoritma yang relevan.

Poin pengetahuan: invarian loop

Bab 4 Algoritma Penyortiran Tingkat Lanjut (Penting)

Bagian ini perlu fokus pada penguasaan tiga algoritma pengurutan tingkat lanjut: pengurutan gabungan, pengurutan cepat, dan pengurutan heap.

menjelaskan:

Bab 5 Penyortiran Non-Komparatif (Opsional)

Bagian ini berisi tiga jenis pengurutan non-perbandingan: pengurutan penghitungan, pengurutan radix, dan pengurutan keranjang. Memecahkan masalah ini memerlukan pemahaman konsep hashing di tempat.

Bab 6 Jendela Geser dan Penunjuk Ganda

1. Jendela geser

Metode penulisan referensi jendela geser (bukan template, mohon jangan disalin apa adanya, ini hanya untuk referensi, yang lebih penting adalah memahami ide desain algoritma):

Pengingat ramah: Soal 3 dan 76 merupakan soal dasar yang harus bisa Anda kerjakan. Setelah Anda memahami pertanyaan-pertanyaan di atas secara menyeluruh, Anda dapat menjawab pertanyaan-pertanyaan berikut dengan lebih mudah.

Pertanyaan kunci:

menjelaskan:

praktik:

menjelaskan:

Pertanyaan 209: Informasi penting yang diberikan dalam pertanyaan: Semua elemen dalam array adalah bilangan bulat positif. Ada total 3 metode sebagai berikut.

Metode 1: Solusi dengan kekerasan

Metode 2: Jendela geser (analisis alasan mengapa jendela geser dapat digunakan)

Metode 3: Buat awalan dan larik, lalu gunakan pencarian biner

Pertanyaan 438: Sama seperti pertanyaan 76;

Pertanyaan 567: Sama seperti pertanyaan 76, hanya saja kumpulan kalimat berkualifikasinya berbeda.

2. Petunjuk ganda

Masalah "penunjuk ganda" sebenarnya merupakan optimasi dari algoritma naif. Banyak solusi yang tidak memenuhi maksud masalah diurutkan sekaligus. Masih lebih penting untuk menganalisis mengapa penunjuk ganda dapat digunakan.

Algoritme pencarian biner yang digunakan untuk menemukan subskrip juga dapat dianggap sebagai solusi penunjuk ganda.

Bab 7 Daftar Tertaut

Teknik yang sangat praktis untuk memecahkan masalah daftar tertaut adalah “menggambar”. Hal yang sama juga berlaku untuk analisis dan penjelasan masalah algoritmik lainnya (menjelaskan kepada pewawancara).

Anda dapat menulis fungsi pengujian untuk daftar tertaut untuk memfasilitasi proses debug. Metode implementasi yang disarankan adalah: ① Membuat daftar tertaut tunggal melalui array; ② Cetak node saat ini dan node berikutnya berdasarkan node saat ini. Kedua metode ini dapat dengan mudah membantu kami men-debug program yang terkait dengan daftar tertaut.

Jenis pertanyaan 1: Masalah penunjuk penunjuk daftar tertaut dasar

Catatan: Beberapa masalah memerlukan penggunaan "simpul kepala virtual" untuk menghindari logika diskusi klasifikasi yang rumit untuk simpul pertama dari daftar tertaut. Kita telah melihat gagasan ini dalam susunan yang disebut "penjaga".

Gunakan fungsi rekursif untuk menghindari operasi rumit dalam mengubah variabel penunjuk, sehingga penyelesaian masalah menjadi sederhana.

menjelaskan:

Tipe Pertanyaan 2: Keterampilan Penunjuk Cepat dan Lambat

Tepatnya, mungkin lebih baik menyebutnya "penunjuk tersinkronisasi".

Dengan menggunakan dua variabel penunjuk, keduanya terletak di simpul pertama daftar tertaut di awal. Yang satu selalu hanya mengambil satu langkah dalam satu waktu, dan yang lainnya selalu hanya mengambil dua langkah dalam satu waktu, satu di depan dan satu lagi di dalam. kembali, pada saat yang sama. Dengan cara ini, ketika penunjuk cepat selesai berjalan, penunjuk lambat akan mencapai posisi tengah daftar tertaut.

Fitur umum untuk menyelesaikan masalah ini adalah dengan menggunakan dua variabel penunjuk untuk bergerak secara sinkron. Penunjuk cepat dan lambat bergerak ke arah yang sama, dan "perbedaan" antara langkah-langkahnya konstan. Berdasarkan kepastian ini, beberapa masalah dalam daftar tertaut dapat diselesaikan. Menggunakan ide ini juga dapat memecahkan masalah daftar tertaut berikut:

menjelaskan:

Jenis pertanyaan ketiga: Desain struktur data

Bab 8 Tumpukan dan Antrian

1. Tumpukan

Tipe Pertanyaan 1: Masalah dasar diselesaikan dengan menggunakan stack

Pertanyaan-pertanyaan berikut ini sangat mendasar dan harus dikuasai:

praktik:

Tipe Pertanyaan 2: Tumpukan Monoton

Tumpukan monotonik adalah tumpukan biasa, yang kebetulan mematuhi prinsip "masuk terakhir, keluar pertama" saat digunakan, dan elemen dalam tumpukan bersifat monoton. Soal "tumpukan monoton" dan "antrian monoton" biasanya sangat istimewa. Kuasai saja contoh dan beberapa latihannya.

Pengalaman: subskrip umumnya disimpan dalam tumpukan monoton.

menjelaskan:

praktik:

2. Antrian

Tipe Pertanyaan 1: Masalah dasar diselesaikan dengan menggunakan antrian

Semua masalah diselesaikan menggunakan antrian penggunaan traversal luasnya.

Tipe Pertanyaan 2: Antrian Monoton

Antrian yang monoton hanyalah antrian biasa. Permasalahan ini saat ini banyak ditemukan pada antrian monotonik pada “Likou”. Kuncinya adalah menganalisis dengan jelas mengapa algoritma yang dirancang justru membuat antrian menjadi monoton. Selain itu ada contoh penggunaan antrian monotonik untuk optimasi pada “Knapsack Problem”. Teman-teman yang berminat dapat mempelajarinya yaitu ilmu kompetisi.

Pengalaman: Langganan umumnya disimpan dalam antrian monoton.

Bab 9 Antrian Prioritas

Catatan: Penting untuk memahami implementasi "heap" sebagai "antrian prioritas". Ini akan membantu untuk memahami detail pengkodean hapus() dan ganti(), sehingga Anda akan lebih efektif saat menggunakan heap.

Penerapan: Secara dinamis memilih elemen dengan prioritas tertinggi dalam antrian saat ini, dengan fokus pada pemahaman arti "dinamis".

Bab 10: Pencarian Gabungan

Dan cek [penjelasan video] poin-poin pengetahuan dalam video solusi soal 990. Pertanyaan dasar dan umum meliputi:

Pertanyaan opsional:

Bab 11 Pohon (Pohon Biner dan Pohon Pencarian Biner)

Bab 12 Algoritma Mundur

Jenis pertanyaan 1: Masalah dasar penelusuran mundur

Melalui soal-soal ini, Anda dapat memahami ide dari algoritma backtracking. Poin-poin pengetahuan dari algoritma backtracking dijelaskan dalam solusi video dan solusi teks dari pertanyaan 46 "Likou".

Backtracking adalah dengan menggunakan depth-first traversal untuk mencari semua solusi pada pohon (grafik). Traversal depth-first memiliki struktur rekursif yang jelas.

Kiat untuk menyelesaikan masalah berikut: ① Gambar, gambar, gambar; ② Pahami traversal dan rekursi yang mendalam; ③ Debug lebih banyak, debug lebih banyak.

Tipe Pertanyaan 2: Masalah Mundur pada String

Poin penting yang perlu dipahami: Karena string menghasilkan karakter baru setiap saat, status tidak perlu disetel ulang.

Jenis pertanyaan ketiga: Isi Banjir

Tipe Pertanyaan 4: Beberapa Pertanyaan Permainan

menjelaskan:

Bab 13 Pemrograman Dinamis (Bagian 1)

Dua ide penting dari pemrograman dinamis:

Dua arah pemikiran dalam pemrograman dinamis:

Tiga kondisi yang harus dipenuhi untuk menyelesaikan masalah menggunakan pemrograman dinamis:

Dua konsep penting pemrograman dinamis:

Referensi klasifikasi pertanyaan:

Catatan: Pertanyaan umum yang diberikan di bawah ini akan ditambahkan (2 Desember 2020).

1. Memulai

Pahami dua metode pemrograman dinamis yaitu rekursi memori "top-down" dan rekursi "bottom-up".

2. Submasalah yang berulang

Bagian ini memerlukan penggunaan "prinsip perkalian penghitungan langkah" dan "prinsip penjumlahan penghitungan kategorikal".

Pertanyaan 70: Ini adalah pertanyaan yang sama dengan bilangan Fibonacci. Soal penghitungan akan menggunakan prinsip penghitungan klasifikasi dan prinsip penghitungan langkah.

3. Substruktur optimal

menjelaskan:

Pertanyaan 377: Perhatikan bahwa pemeriksaan bukan merupakan masalah ransel.

4. Tidak ada efek samping

praktik:

Berikut ini adalah beberapa masalah klasik "pemrograman dinamis". Karena isu-isu ini sangat penting, maka isu-isu ini dimasukkan dalam kategori tersendiri.

5. Jumlah sub-segmen maksimum

praktik:

6. Kenaikan terpanjang berikutnya

Catatan: Pertanyaan 300 adalah soal pemrograman dinamis yang sangat klasik. Solusi $O(N log N)$ mendefinisikan keadaan sesuai dengan karakteristik masalah itu sendiri dan membuktikan bahwa array keadaan adalah array yang dipesan, yang mengurangi kompleksitas waktu.

praktik:

7. Substring umum terpanjang

8. Interval DP dan DP yang dipartisi

Interval DP:

DP yang dipartisi:

9. DP Pohon

Bab 14 Pemrograman Dinamis (Bagian 2)

1. Masalah Ransel

Sembilan kuliah tentang ransel: https://github.com/tianyicui/pack

("DP Tipe Game", "DP Kompresi Status", "DP Digital", dll. akan ditambahkan.)

Pertanyaan lainnya

Bab 15 Algoritma Serakah

Bab 17 Tabel Hash

Bab 18 Jumlah Awalan dan Tabel Hash

Bab 19 Traversal Luas-Pertama

Beberapa masalah dengan penjelajahan pohon yang pertama kali dan beberapa masalah di LeetBook.

Bab 20 Algoritma Teori Graf (Pohon Rentang Minimum)

Bab 21 Algoritma Teori Graf (Jalur Terpendek Sumber Tunggal)

Bab 22 Algoritma Bagi dan Taklukkan

Gagasan membagi dan menaklukkan (membagi dan menaklukkan) membagi masalah yang lebih besar menjadi beberapa sub-masalah yang lebih kecil dengan jenis yang sama, dan kemudian menyelesaikan sub-masalah tersebut secara rekursif. Setelah setiap sub-masalah selesai, solusinya masalah awal diperoleh.

Algoritme bagi-dan-taklukkan dapat dijalankan secara paralel, namun dalam bidang algoritma dasar, algoritma bagi-dan-taklukkan dijalankan dengan cara depth-first traversal.

Algoritme umum yang menerapkan gagasan bagi-dan-taklukkan: pengurutan gabungan, pengurutan cepat.

Masalah khas pemikiran membagi dan menaklukkan: "Pertanyaan 51 tentang Pedang Menunjuk pada Penawaran": "Pertanyaan 51 tentang Pedang Menunjuk pada Penawaran" 51. Pasangan urutan terbalik dalam array (penjelasan video).

Pertanyaan umum lainnya (akan ditambahkan)

Ini akan terus diperbarui, dan teman-teman dipersilakan untuk memberikan masukan yang berharga!