Temu Duga Pengekodan: Swap bersebelahan minimum untuk menghasilkan palindrom

Gesaan dan penetapan

Setiap swap bersebelahan bernilai satu. Aksara boleh berulang, dan input boleh menjadi mustahil apabila lebih daripada satu aksara mempunyai kekerapan ganjil. Matlamatnya adalah bilangan swap minimum, bukan sekadar sebarang palindrom.

Perkara yang diuji oleh penemu duga

• Menerbitkan syarat kebolehlaksanaan kekerapan ganjil.
• Memadankan aksara kiri dengan pasangan sah terdekat dari kanan.
• Membuktikan mengapa pilihan greedy adalah optimum dan mengambil kira anjakan.

Soalan penjelasan sebelum menjawab

• Adakah swap hanya bersebelahan, dan adakah setiap swap bernilai satu?
• Adakah abjadnya sewenang-wenangnya, dan adakah titik kod Unicode dianggap sebagai aksara?
• Patutkah fungsi mengubah tatasusunan atau mengembalikan bilangannya sahaja?
• Apakah saiz input yang menentukan sama ada pendekatan O(n²) boleh diterima?

Rangka kerja jawapan 30 saat

Kira kekerapan ganjil terlebih dahulu; lebih daripada satu kiraan ganjil menjadikan palindrom mustahil. Gunakan penuding pada kedua-dua hujung. Jika kedua-dua hujung sepadan, bergerak ke dalam. Jika tidak, cari aksara yang sepadan untuk hujung kiri dengan mengimbas dari sempadan kanan ke dalam, apungkan (bubble) ke arah kanan dengan swap bersebelahan, dan kira setiap pergerakan. Jika tiada padanan wujud, aksara yang tidak sepadan mestilah pusat tunggal; gerakkannya ke arah pusat dan teruskan.

Perincian langkah demi langkah

1. Buktikan kebolehlaksanaan

Palindrom mempunyai paling banyak satu kekerapan ganjil, kerana pasangan menduduki kedudukan simetri dan hanya pusat panjang ganjil boleh kekal tanpa pasangan. Pemeriksaan ini mengelakkan daripada menjalankan gelung greedy pada input yang mustahil.

2. Padankan sempadan

Bagi penuding i dan j, jika s[i] bersamaan dengan s[j], kedua-dua kedudukan ditetapkan. Jika tidak, cari k dari j turun ke i + 1 untuk s[k] == s[i]. Menggerakkan aksara itu ke kanan menelan kos j - k swap dan mengekalkan awalan yang telah ditetapkan.

3. Kendalikan aksara pusat

Jika tiada padanan ditemui, s[i] ialah aksara kekerapan ganjil yang sepatutnya berada di pusat. Gerakkannya satu langkah ke kanan pada satu masa sehingga ia mencapai bahagian tengah, sambil mengira swap. Jangan buangnya atau menganggap pusat mesti ditemui pada laluan pertama.

4. Laksanakan simulasi

count odd frequencies
if odd_count > 1: return impossible
left = 0, right = n - 1, swaps = 0
while left < right:
    if s[left] == s[right]: left++, right--; continue
    k = right
    while k > left and s[k] != s[left]: k--
    if k == left:
        swap s[k] with s[k + 1]
        swaps++
    else:
        while k < right:
            swap s[k] with s[k + 1]
            k++, swaps++
        left++, right--
return swaps

5. Analisis kerumitan dan idea pembuktian

Setiap laluan carian dan pengapungan boleh mengimbas O(n), diulang O(n) kali, jadi masa ialah O(n²) dan tatasusunan boleh ubah menggunakan ruang tambahan O(1). Pasangan greedy adalah yang paling dekat dengan sempadan; menggerakkan aksara sama yang lebih jauh memerlukan sekurang-kurangnya jumlah swap yang sama sebelum sempadan boleh ditetapkan. Kes pusat dipaksa oleh pariti.

Contoh jawapan berkualiti tinggi

“Saya mula-mula mengira kekerapan ganjil; lebih daripada satu bermakna mustahil. Kemudian saya membandingkan kedua-dua hujung. Sekiranya tidak sepadan, saya mencari aksara sama yang paling dekat dengan sempadan kanan dan mengapungkannya ke tempatnya, menambah jaraknya; jika tiada yang sama wujud, aksara itu ialah pusat ganjil yang unik, jadi saya menggerakkannya ke arah tengah. Hujung yang sepadan mengecilkan tetingkap. Simulasi ini mengambil masa O(n²) dan O(1) ruang tambahan, dan pilihan greedy adalah optimum kerana mana-mana pasangan yang lebih jauh memerlukan sekurang-kurangnya bilangan swap bersebelahan yang sama.”

Kesilapan biasa

• Semak sama ada kiraan adalah genap sahaja → rentetan panjang ganjil mungkin mempunyai satu kiraan ganjil → benarkan paling banyak satu kekerapan ganjil.
• Swap dengan aksara sepadan yang sewenang-wenangnya → pergerakan tambahan boleh menjadi tidak minimum → pilih pasangan yang paling dekat dengan sempadan.
• Gugurkan aksara yang tidak sepadan → pergerakan pusat terkurang kira → apungkannya ke arah tengah.
• Gunakan swap dua penuding tanpa anjakan → kos swap bersebelahan hilang → simulasikan setiap pergerakan bersebelahan atau gunakan struktur data yang setara.

Soalan susulan dan respons

Bolehkah algoritma mengembalikan palindrom itu juga?

Ya. Kekalkan tatasusunan boleh ubah dan kembalikan kedua-dua kandungan akhir dan kiraan swap. Simulasi yang sama merekodkan setiap swap bersebelahan jika pemanggil memerlukan urutan tersebut.

Bagaimanakah anda memperbaikinya untuk input yang besar?

Jejaki kedudukan asal dengan Fenwick tree atau struktur statistik pesanan supaya menggerakkan aksara boleh mengemas kini kedudukan dalam masa logaritma. Gandingan greedy kekal, manakala pengiraan kos mengelakkan anjakan setiap elemen.

Bagaimana jika swap adalah sewenang-wenangnya dan bukannya bersebelahan?

Itu model kos yang berbeza. Bukti jarak pasangan terdekat tidak lagi terpakai; tentukan operasi yang dibenarkan sebelum menggunakan semula algoritma ini.