Cari Bit Kth dalam Rentetan Binari Nth

1545. Cari Bit Kth dalam Rentetan Perduaan Nth

Kesukaran: Sederhana

Topik: Rentetan, Rekursi, Simulasi

Diberi dua integer positif n dan k, rentetan binari S_n dibentuk seperti berikut:

• S₁ = "0"
• S_i = S_{i - 1} "1" terbalik(songsang(S_{i - 1})) untuk i > 1

Di mana menandakan operasi penggabungan, reverse(x) mengembalikan rentetan terbalik x, dan invert(x) menyongsangkan semua bit dalam x (0 berubah menjadi 1 dan 1 berubah menjadi 0).

Sebagai contoh, empat rentetan pertama dalam urutan di atas ialah:

• S₁ = "0"
• S₂ = "011"
• S₃ = "0111001"
• S₄ = "011100110110001"

Kembalikan bit k^ke dalam S_n. Dijamin k sah untuk n.

Contoh 1:

• Input: n = 3, k = 1
• Output: "0"
• Penjelasan: S₃ ialah "0111001". Bit 1^st ialah "0".

Contoh 2:

• Input: n = 4, k = 11
• Output: "1"
• Penjelasan: S₄ ialah "011100110110001". Bit ke-11 ialah "1".

Contoh 3:

• Input: n = 3, k = 2
• Output: "0"

Kekangan:

• 1 <= n <= 20
• 1 <= k <= 2ⁿ - 1

Petunjuk:

1. Memandangkan n adalah kecil, kita hanya boleh mensimulasikan proses membina S1 kepada Sn.

Penyelesaian:

Kita perlu memahami proses rekursif yang digunakan untuk menjana setiap rentetan binari S_n dan gunakan ini untuk menentukan bit k-ke- tanpa membina keseluruhan rentetan.

Pendekatan:

1. Pembinaan Rentetan Rekursif:

   • S₁ = "0".
   • Untuk saya > 1:
     • S_i dibina sebagai: S_i = S_i-1 "1" terbalik(songsang(S_i-1))
   • Ini bermakna S_i terdiri daripada tiga bahagian:
     • S_i-1 (bahagian asal)
     • "1" (bit tengah)
     • terbalik(terbalikkan(S_i-1)) (bahagian yang berubah)

2. Pemerhatian Utama:

   • S_i mempunyai panjang 2^i-1.
   • Bit tengah (kedudukan 2^i-1 daripada S_i sentiasa "1".
   • Jika k terletak pada separuh masa pertama, ia jatuh dalam S_i-1.
   • Jika k betul-betul kedudukan tengah, jawapannya ialah "1".
   • Jika k berada pada separuh masa kedua, ia sepadan dengan bahagian songsang terbalik.

3. Menterbalikkan dan Membalikkan:

   • Untuk menentukan bit pada separuh masa kedua, petakan k ke kedudukan yang sepadan pada separuh masa pertama menggunakan: k' = 2ⁱ - k
   • Bit pada kedudukan ini dalam separuh asal adalah terbalik, jadi kita perlu membalikkan hasilnya.

4. Penyelesaian Rekursif:

   • Tentukan secara rekursif kbit ke- dengan mengurangkan n dan pemetaan k sehingga n = 1.

Mari laksanakan penyelesaian ini dalam PHP: 1545. Cari Bit Kth dalam Rentetan Binari N


<?php
/**
 * @param Integer $n
 * @param Integer $k
 * @return String
 */
function findKthBit($n, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

Penjelasan:

• Kes Asas: Jika n = 1, S_i ialah "0" , jadi satu-satunya nilai yang mungkin untuk mana-mana k ialah "0".
• Langkah Rekursif:
  • Kira indeks tengah pertengahan iaitu 2^n-1.
  • Jika k sepadan dengan indeks tengah, kembalikan "1".
  • Jika k kurang daripada pertengahan, k-ke bit terletak pada separuh masa pertama, jadi kami mencari secara rekursif kbit ke- dalam S_n-1.
  • Jika k lebih besar daripada pertengahan, kita dapati bit yang sepadan dalam separuh masa kedua songsang dan balikkannya.

Analisis Kerumitan:

• Kerumitan Masa: O(n) kerana setiap panggilan rekursif mengurangkan n sebanyak 1.
• Kerumitan Angkasa: O(n) untuk timbunan panggilan rekursif.

Contoh Panduan:

1. Input: n = 3 , k = 1

   • S₃ = "0111001"
   • k = 1 jatuh pada separuh masa pertama, jadi kita cari k = 1 dalam S₂.
   • Dalam S₂ = "011" , k = 1 sepadan dengan "0".

2. Input: n = 4 , k = 11

   • S₄ = "011100110110001"
   • Indeks tengah untuk S₄ ialah 8.
   • k = 11 jatuh pada separuh masa kedua.
   • Peta k = 11 ke bit yang sepadan pada separuh masa pertama: k' = 2 ^{4 - 11 = 5}.
   • Cari k = 5 dalam S₃ , iaitu "0", kemudian balikkannya kepada "1".

Dengan memanfaatkan rekursi dan sifat pembinaan rentetan, penyelesaian ini mengelakkan menjana keseluruhan rentetan, menjadikannya cekap walaupun untuk lebih besar n.

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 Cari Bit Kth dalam Rentetan Binari Nth. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!