Memahami Corak Elemen K dalam LeetCode: Asas (Bahagian 1)

Saya akhirnya faham! Cara terbaik untuk mempelajari LeetCode bukanlah dengan menyelesaikan masalah demi masalah, kadangkala mengambil masa satu jam penuh untuk menyelesaikannya secara tidak cekap. Kunci untuk menguasai LeetCode ialah mempelajari corak. Mari kita kaji yang biasa!

Penemuduga suka bertanya tentang mencari, mengekalkan atau memanipulasi elemen K dalam rentetan atau tatasusunan. Pada mulanya, saya fikir setiap masalah adalah berbeza, tetapi kemudian saya mula melihat sambungannya. Biar saya tunjukkan kepada anda apa yang saya maksudkan dengan dua masalah yang benar-benar membantu saya memahami corak ini.

Masalah 1: Cari Susunan Panjang K dengan Jumlah Terbesar

Ini secara teknikalnya soalan peringkat 'mudah' (hanya ditanya oleh satu syarikat), tetapi, ia mengajar anda banyak tentang cara berfikir tentang masalah elemen k ini!

Apa Yang Mereka Tanya

Anda mendapat tatasusunan nombor dan nilai k, dan anda perlu mencari nombor k daripada tatasusunan yang menjumlahkan sehingga jumlah terbesar yang mungkin. TETAPI (dan inilah bahagian yang membuatkan saya tersandung pada mulanya), anda perlu mengekalkan nombor dalam susunan asalnya!

Contoh:

Oh! yang ini lebih rumit:

Ok saya faham

Pada mulanya, saya fikir "rebut sahaja nombor terbesar, selesai!" Tetapi tidak - keperluan pesanan itu mengubah segala-galanya. Inilah yang akhirnya diklik:

1. Kita perlu ingat dari mana datangnya setiap nombor, bukan? Jadi Saya fikir, "Saya harus memasangkan setiap nombor dengannya jawatan?"

1. Kemudian kita boleh mengisih pasangan ini mengikut nilai (iaitu nombor pertama dalam setiap pasangan), tetapi kami menjejakinya dari mana mereka datang (itu nombor kedua)!

1. Sekarang bahagian yang menarik - kita hanya memerlukan k daripada ini, jadi ambil pasangan k pertama dan hanya kekalkan kedudukan mereka:

1. Akhir sekali, berjalan melalui tatasusunan asal dan simpan sahaja nombor yang kedudukannya ada dalam Set kami:

Inilah Kodnya

2: Kth Elemen Terbesar dalam Strim

Ok, jadi yang ini juga dilabel 'mudah' (ditanya oleh lima syarikat), tetapi yang ini lebih mengelirukan saya daripada mana-mana masalah elemen Kth yang lebih sukar.

Apa Yang Mereka Tanya

Bayangkan anda bekerja di universiti dan pelajar terus menghantar markah ujian. Tugas anda adalah untuk sentiasa mengetahui markah tertinggi ke-1 pada bila-bila masa. Markah baharu terus masuk dan anda perlu menjejaki.

Mereka memberi anda k dan beberapa markah awal, kemudian mereka terus melemparkan markah baharu kepada anda dan ingin mengetahui kth tertinggi setiap kali. Mari lihat contoh:

Ok, saya rasa saya faham

Pada mulanya, saya terus mencuba untuk mengisih keseluruhan tatasusunan setiap kali skor baharu masuk tetapi saya tahu bahawa pengisihan mungkin tidak cekap. Kemudian saya terfikir mengapa saya menjejaki semua markah sedangkan saya hanya mementingkan k atas?

Begini cara saya memecahkannya:

1. Mula-mula, susun markah awal dan hanya kekalkan k teratas:

1. Kini apabila markah baharu masuk:

Jika lebih kecil daripada kth tertinggi kami (angka pertama), abaikan
Jika ia lebih besar, ia tergolong dalam senarai kami di suatu tempat

Berikut ialah perkara yang berlaku dengan setiap tambahan:

Kod

Mengapa Dua Masalah Ini Bersambung

Kedua-dua masalah mengajar saya sesuatu yang sangat penting tentang pengendalian elemen k:

• Masalah pertama: Kadangkala anda perlu menjejaki di mana elemen berasal dari
• Masalah kedua: Kadangkala anda hanya perlu menyimpan elemen k sekitar

Masalah k-elemen ini adalah tentang menjadi bijak dengan maklumat yang anda simpan dan apa yang anda buang.
Kali seterusnya kita akan melihat dua lagi masalah k-elemen yang membina idea ini. Saya harap pada akhirnya anda melihat corak dan jenis masalah ini kelihatan kurang menakutkan!

Atas ialah kandungan terperinci Memahami Corak Elemen K dalam LeetCode: Asas (Bahagian 1). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!