Ambil K setiap Watak Dari Kiri dan Kanan

2516. Ambil K Setiap Watak Dari Kiri dan Kanan

Kesukaran: Sederhana

Topik: Jadual Hash, Rentetan, Tetingkap Gelongsor

Anda diberi rentetan s yang terdiri daripada aksara 'a', 'b' dan 'c' serta integer bukan negatif k. Setiap minit, anda boleh mengambil sama ada paling kiri aksara s, atau paling kanan aksara s.

Kembalikan minimum bilangan minit yang diperlukan untuk anda mengambil sekurang-kurangnya k setiap aksara, atau kembalikan -1 jika tidak mungkin untuk mengambil k setiap aksara watak.

Contoh 1:

• Input: s = "aabaaaacaabc", k = 2
• Output: 8
• Penjelasan: Ambil tiga aksara dari kiri s. Anda kini mempunyai dua aksara 'a', dan satu aksara 'b'.
  • Ambil lima aksara dari sebelah kanan s. Anda kini mempunyai empat aksara 'a', dua aksara 'b' dan dua aksara 'c'.
  • Sebanyak 3 5 = 8 minit diperlukan.
  • Boleh dibuktikan bahawa 8 adalah bilangan minimum minit yang diperlukan.

Contoh 2:

• Input: s = "a", k = 1
• Output: -1
• Penjelasan: Tidak boleh mengambil satu 'b' atau 'c' jadi kembalikan -1.

Kekangan:

• 1 <= s.panjang <= 10⁵
• s hanya terdiri daripada huruf 'a', 'b' dan 'c'.
• 0 <= k <= s.panjang

Petunjuk:

1. Mulakan dengan mengira kekerapan setiap aksara dan semak jika boleh.
2. Jika anda mengambil x aksara dari sebelah kiri, apakah bilangan minimum aksara yang perlu anda ambil dari sebelah kanan? Cari ini untuk semua nilai x dalam julat 0 ≤ x ≤ s.panjang.
3. Gunakan pendekatan dua mata untuk mengelakkan pengiraan maklumat yang sama beberapa kali.

Penyelesaian:

Kita boleh menggunakan teknik tetingkap gelongsor dengan dua penunjuk untuk mencari bilangan minit minimum yang diperlukan untuk mengambil sekurang-kurangnya k setiap aksara ('a', 'b', 'c') dari kedua-dua kiri dan kanan rentetan.

Pecahan Masalah:

• Kami diberi rentetan s yang mengandungi hanya 'a', 'b' dan 'c'.
• Kita perlu mengambil sekurang-kurangnya k kejadian setiap aksara, sama ada daripada aksara paling kiri atau paling kanan rentetan.
• Kita perlu menentukan bilangan minit minimum yang diperlukan untuk mencapai ini atau mengembalikan -1 jika mustahil.

Pendekatan:

1. Semakan Awal:

   • Jika k == 0, kami boleh terus mengembalikan 0 kerana tiada aksara diperlukan.
   • Jika k melebihi bilangan kejadian mana-mana aksara dalam rentetan, kembalikan -1 dengan segera.

2. Kiraan Kekerapan:

   • Kita perlu mengira berapa kali 'a', 'b' dan 'c' muncul dalam rentetan s untuk memastikan bahawa adalah mungkin untuk mengumpulkan k setiap aksara.

3. Teknik Tingkap Gelongsor:

   • Gunakan pendekatan tingkap gelongsor dengan dua penunjuk (kiri dan kanan).
   • Kekalkan dua penunjuk dan luncurkannya dari kedua-dua hujung rentetan untuk mengumpulkan aksara yang diperlukan.
   • Untuk setiap bilangan aksara yang diambil dari sebelah kiri, kirakan bilangan minimum aksara yang perlu diambil dari kanan untuk memenuhi keperluan.

4. Pengoptimuman:

   • Daripada mengira semula kiraan aksara berulang kali untuk setiap tetingkap, kami boleh menjejaki kiraan aksara semasa kami mengembangkan atau mengecutkan tetingkap.

Mari laksanakan penyelesaian ini dalam PHP: 2516. Ambil K setiap Watak Dari Kiri dan Kanan

  
  
  Penjelasan:




Persediaan Awal:


Kami mengira kejadian 'a', 'b' dan 'c' dalam keseluruhan rentetan untuk memastikan kemungkinan untuk mengumpulkan sekurang-kurangnya k setiap aksara.
Jika mana-mana kiraan aksara kurang daripada k, kembalikan -1.



Tetingkap Gelongsor:


Kami menggunakan dua penunjuk (kiri dan kanan) untuk mencipta tetingkap gelongsor dari kedua-dua hujungnya.
Kami mengembangkan tetingkap dengan menggerakkan penuding kanan dan menambah kiraan aksara yang ditemui.
Setelah kami mempunyai sekurang-kurangnya k setiap aksara dalam tetingkap semasa, kami cuba mengecilkan tetingkap dari kiri untuk meminimumkan bilangan minit (aksara yang diambil).



Meminimumkan Masa:


Kami menjejaki bilangan minit minimum yang diperlukan dengan membandingkan saiz tetingkap setiap kali kami mengumpulkan k aksara daripada semua jenis.





  
  
  Kerumitan Masa:



Mengira aksara pada mulanya mengambil masa O(n).
Operasi tetingkap gelongsor mengambil masa O(n), kerana kedua-dua penunjuk kiri dan kanan bergerak melintasi rentetan sekali.
Kerumitan masa keseluruhan ialah O(n).



  
  
  Kes Tepi:



Jika k == 0, kembalikan 0.
Jika mustahil untuk mengambil k setiap aksara, kembalikan -1.


Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          
Atas ialah kandungan terperinci Ambil K setiap Watak Dari Kiri dan Kanan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!