inimum Bertukar kepada Kumpulan Semua Bersama II

2134. Pertukaran Minimum untuk Kumpulan Semua 1 Bersama II

Sederhana

Pertukaran ditakrifkan sebagai mengambil dua kedudukan berbeza dalam tatasusunan dan menukar nilai di dalamnya.

Tatasusunan

Satu tatasusunan bulatan ditakrifkan sebagai tatasusunan di mana kita menganggap elemen pertama dan elemen terakhir menjadi bersebelahan.

Memandangkan pekeliling binari nombor tatasusunan, kembalikan bilangan swap minimum yang diperlukan untuk mengumpulkan semua 1 hadir dalam tatasusunan bersama-sama di mana-mana lokasi.

Contoh 1:

• Input: nombor = [0,1,0,1,1,0,0]
• Output: 1
• Penjelasan: Berikut ialah beberapa cara untuk mengumpulkan semua 1 bersama:
  • [0,0,1,1,1,0,0] menggunakan 1 pertukaran.
  • [0,1,1,1,0,0,0] menggunakan 1 pertukaran.
  • [1,1,0,0,0,0,1] menggunakan 2 swap (menggunakan sifat bulat tatasusunan).
  • Tiada cara untuk mengumpulkan semua 1 bersama-sama dengan 0 pertukaran.
  • Oleh itu, bilangan swap minimum yang diperlukan ialah 1.

Contoh 2:

• Input: nombor = [0,1,1,1,0,0,1,1,0]
• Output: 2
• Penjelasan: Berikut ialah beberapa cara untuk mengumpulkan semua 1 bersama:
  • [1,1,1,0,0,0,0,1,1] menggunakan 2 swap (menggunakan sifat bulat tatasusunan).
  • [1,1,1,1,1,0,0,0,0] menggunakan 2 pertukaran.
  • Tiada cara untuk mengumpulkan semua 1 bersama-sama dengan 0 atau 1 pertukaran.
  • Oleh itu, bilangan swap minimum yang diperlukan ialah 2.

Contoh 3:

• Input: nombor = [1,1,0,0,1]
• Output: 0
• Penjelasan: Semua 1 sudah dikumpulkan bersama disebabkan oleh sifat bulat tatasusunan.
  • Oleh itu, bilangan swap minimum yang diperlukan ialah 0.

Kekangan:

• 1 <= nums.length <= 10⁵
• nums[i] ialah sama ada 0 atau 1.

Petunjuk:

1. Perhatikan bahawa nombor 1 untuk dikumpulkan bersama adalah tetap. Ia ialah nombor 1 yang dimiliki oleh keseluruhan tatasusunan.
2. Hubungi jumlah nombor ini. Kemudian, kita harus menyemak setiap subarray daripada jumlah saiz (mungkin dililit), berapa banyak swap yang diperlukan untuk menjadikan subarray semuanya 1.
3. Bilangan pertukaran yang diperlukan ialah bilangan 0 dalam subbaris.
4. Untuk menghapuskan sifat bulat tatasusunan, kita boleh menambahkan tatasusunan asal pada dirinya sendiri. Kemudian, kami menyemak setiap subarray jumlah panjang.
5. Bagaimanakah kita mengelak daripada mengira bilangan 0 dalam sub-baris setiap kali? Teknik Tingkap Gelongsor boleh membantu.

Penyelesaian:

Untuk menyelesaikan masalah ini, kita boleh ikuti langkah berikut:

1. Kira Jumlah Bilangan 1: Ini ialah nombor 1 yang perlu kita kumpulkan bersama.
2. Lanjutkan Tatasusunan: Untuk mengendalikan sifat bulat, tambahkan tatasusunan pada dirinya sendiri.
3. Gunakan Teknik Tetingkap Gelongsor: Gunakan teknik tetingkap gelongsor pada tatasusunan lanjutan untuk mencari bilangan swap minimum yang diperlukan.

Mari laksanakan penyelesaian ini dalam PHP: 2134. Pertukaran Minimum untuk Kumpulan Semua 1 Bersama II

  
  
  Penjelasan:




Kira Jumlah Bilangan 1s: Kira jumlah bilangan 1s dalam tatasusunan asal.

Lanjutkan Tatasusunan: Gabungkan tatasusunan asal kepada dirinya sendiri untuk mengendalikan sifat bulat.

Tetingkap Permulaan: Kira bilangan 0s dalam tetingkap awal bersaiz sama dengan jumlah bilangan 1s.

Tetingkap Gelongsor: Luncurkan tetingkap merentasi tatasusunan lanjutan. Untuk setiap kedudukan baharu, kemas kini kiraan 0s berdasarkan elemen masuk dan keluar dari tetingkap.

Cari Minimum: Jejaki bilangan minimum 0 yang ditemui, yang sepadan dengan bilangan swap minimum yang diperlukan.


Penyelesaian ini mengendalikan tatasusunan bulat dengan cekap dengan mengubahnya menjadi masalah linear dan menggunakan teknik tetingkap gelongsor untuk mengekalkan kiraan larian 0s dalam setiap tetingkap bersaiz sama dengan jumlah bilangan 1s.

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 inimum Bertukar kepada Kumpulan Semua Bersama II. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!