Bilangan Operasi Minimum untuk Mengalihkan Semua Bola ke Setiap Kotak

1769. Bilangan Operasi Minimum untuk Mengalihkan Semua Bola ke Setiap Kotak

Kesukaran: Sederhana

Topik: Tatasusunan, Rentetan, Jumlah Awalan

Anda mempunyai n kotak. Anda diberi kotak rentetan binari dengan panjang n, dengan kotak[i] ialah '0' jika kotak i^th kosong dan '1' jika mengandungi satu bola.

Dalam satu operasi, anda boleh memindahkan satu bola dari kotak ke kotak bersebelahan. Kotak i bersebelahan dengan kotak j jika abs(i - j) == 1. Ambil perhatian bahawa selepas berbuat demikian, mungkin terdapat lebih daripada satu bola dalam beberapa kotak.

Kembalikan jawapan tatasusunan saiz n, dengan jawapan[i] ialah minimum bilangan operasi yang diperlukan untuk memindahkan semua bola ke kotak i^ke.

Setiap jawapan[i] dikira dengan mengambil kira keadaan awal kotak.

Contoh 1:

• Input: kotak = "110"
• Output: [1,1,3]
• Penjelasan: Jawapan bagi setiap kotak adalah seperti berikut:
  1. Kotak pertama: anda perlu mengalihkan satu bola dari kotak kedua ke kotak pertama dalam satu operasi.
  2. Kotak kedua: anda perlu memindahkan satu bola dari kotak pertama ke kotak kedua dalam satu operasi.
  3. Kotak ketiga: anda perlu memindahkan satu bola dari kotak pertama ke kotak ketiga dalam dua operasi dan memindahkan satu bola dari kotak kedua ke kotak ketiga dalam satu operasi.

Contoh 2:

• Input: kotak = "001011"
• Output: [11,8,5,4,3,4]

Kekangan:

• n == kotak.panjang
• 1
• kotak[i] sama ada '0' atau '1'.

Petunjuk:

1. Jika anda ingin memindahkan bola dari kotak i ke kotak j, anda memerlukan pergerakan abs(i-j).
2. Untuk mengalihkan semua bola ke beberapa kotak, anda boleh mengalihkannya satu demi satu.
3. Untuk setiap kotak i, lelaran pada setiap bola dalam kotak j dan tambah abs(i-j) pada jawapan[i].

Penyelesaian:

Kami boleh menggunakan pendekatan jumlah awalan yang membolehkan kami mengira bilangan minimum operasi yang diperlukan untuk memindahkan semua bola ke setiap kotak tanpa mensimulasikan setiap operasi secara eksplisit.

Pemerhatian Utama:

1. Bilangan pergerakan yang diperlukan untuk memindahkan bola dari kotak i ke kotak j hanyalah abs(i - j).
2. Kita boleh mengira jumlah pergerakan untuk memindahkan semua bola ke kotak tertentu dengan memanfaatkan kedudukan bola dan jumlah operasi yang sedang berjalan.
3. Dengan mengira pergerakan dari kiri ke kanan dan kanan ke kiri, kita boleh menentukan keputusan dalam dua hantaran.

Pendekatan:

1. Hantaran Kiri-ke-Kanan: Dalam hantaran ini, kira bilangan pergerakan untuk membawa semua bola ke kotak semasa bermula dari kiri.
2. Hantar Kanan ke Kiri: Dalam hantaran ini, kira bilangan pergerakan untuk membawa semua bola ke kotak semasa bermula dari kanan.
3. Gabungkan keputusan kedua-dua pas untuk mendapatkan keputusan akhir bagi setiap kotak.

Langkah Penyelesaian:

1. Mulakan dengan mengulangi rentetan kotak dan mengira bilangan bola di sebelah kiri dan di sebelah kanan setiap kotak.
2. Semasa lelaran, hitung bilangan pergerakan yang diperlukan untuk membawa semua bola ke kotak semasa menggunakan kedua-dua maklumat kiri dan kanan.

Mari laksanakan penyelesaian ini dalam PHP: 1769. Bilangan Minimum Operasi untuk Mengalihkan Semua Bola ke Setiap Kotak

<?php /**
 * @param String $boxes
 * @return Integer[]
 */
function minOperations($boxes) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$boxes = "110";
print_r(minOperations($boxes)); // Output: [1,1,3]

$boxes = "001011";
print_r(minOperations($boxes)); // Output: [11,8,5,4,3,4]
?>

Penjelasan:

1. Hantar kiri ke kanan: Kami mengira jumlah bilangan operasi yang diperlukan untuk membawa semua bola dari sebelah kiri ke kotak semasa. Untuk setiap bola yang ditemui ('1'), kami mengemas kini jumlah bilangan pergerakan.
2. Hantar kanan ke kiri: Sama seperti hantaran kiri ke kanan, tetapi kami mengira bilangan operasi untuk mengalihkan bola dari sebelah kanan ke kotak semasa.
3. Jumlah operasi untuk setiap kotak ialah jumlah pergerakan dari hantaran kiri dan kanan.

Contoh Panduan:

Contoh 1:

$boxes = "110";
print_r(minOperations($boxes));

Output:

Array
(
    [0] => 1
    [1] => 1
    [2] => 3
)

Contoh 2:

$boxes = "001011";
print_r(minOperations($boxes));

Output:

Array
(
    [0] => 11
    [1] => 8
    [2] => 5
    [3] => 4
    [4] => 3
    [5] => 4
)

Kerumitan Masa:

• Penyelesaian berjalan dalam masa O(n) kerana kami mengulangi rentetan kotak dua kali (sekali untuk hantaran kiri ke kanan dan sekali untuk hantaran kanan ke kiri).
• Kerumitan ruang ialah O(n) kerana kami menyimpan tatasusunan jawapan untuk menyimpan hasilnya.

Penyelesaian ini mengira bilangan operasi minimum untuk setiap kotak dengan cekap menggunakan teknik jumlah awalan.

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 Bilangan Operasi Minimum untuk Mengalihkan Semua Bola ke Setiap Kotak. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!