inimum Bertukar kepada Kumpulan Semua Bersama II

2134. Pertukaran Minimum untuk Kumpulan Semua 1 Bersama II

Sederhana

Aswapditakrifkan sebagai mengambil duaberbezakedudukan dalam tatasusunan dan menukar nilai di dalamnya.

Tatasusunanbulatanditakrifkan sebagai tatasusunan di mana kita menganggap elemenpertamadan elementerakhirsebagaibersebelahan.

Diberikan nombor tatasusunanpekeliling binari, kembalikanbilangan swap minimum yang diperlukan untuk mengumpulkan semua 1 hadir dalam tatasusunan bersama-sama dimana-mana lokasi.

Contoh 1:

• Input:angka = [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:angka = [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:angka = [1,1,0,0,1]
• Output:0
• Penjelasan:Semua 1 sudah dikumpulkan bersama kerana sifat bulat tatasusunan.
  • Oleh itu, bilangan swap minimum yang diperlukan ialah 0.

Kekangan:

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

Petunjuk:

1. Perhatikan bahawa nombor 1 untuk dikumpulkan bersama adalah tetap. Ia adalah nombor 1 yang dimiliki oleh keseluruhan tatasusunan.
2. Hubungi nombor ini secara keseluruhan. Kemudian, kita harus menyemak setiap subarray daripada jumlah saiz (mungkin dililit), berapa banyak swap yang diperlukan untuk menjadikan subarray semuanya 1.
3. Bilangan swap 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 nombor 0 dalam subaray setiap kali? Teknik Sliding Window boleh membantu.

Penyelesaian:

Untuk menyelesaikan masalah ini, kita boleh ikuti langkah berikut:

1. Kira Jumlah Bilangan 1s: Ini ialah bilangan 1 yang perlu kita kumpulkan.
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 kita 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 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.
Hubungi Pautan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberirepositoribintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna buat 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!