Jadikan rentetan binari sama dengan berulang kali menggantikan bit kedua

Dalam masalah ini, kita perlu menukar rentetan bin1 kepada rentetan bin2 dengan menggantikan aksara kedua rentetan bin1 dengan nilai minimum atau maksimum antara aksara pertama dan kedua, dan memadamkan aksara pertama.

Memandangkan kita perlu mengalih keluar aksara pertama, kita perlu memastikan bahawa len2 terakhir − 1 aksara dalam dua rentetan adalah sama. Selain itu, kita perlu memastikan bahawa kita boleh mendapatkan aksara pertama rentetan kedua dengan melaksanakan operasi yang diberikan pada aksara permulaan rentetan bin1.

Pernyataan Masalah - Kami diberi bin1 dan bin2 rentetan binari panjang len1 dan len2 masing-masing. Kita perlu menyemak sama ada kita boleh menukar rentetan bin1 kepada rentetan bin2 dengan melakukan perkara berikut.

• Kemas kini aksara kedua rentetan bin1 menggunakan nilai minimum atau maksimum bagi aksara pertama dan kedua rentetan bin1.

• Alih keluar aksara pertama rentetan bin1, dan saiz rentetan akan dikurangkan sebanyak 1 setiap kali.

Contoh

Masuk

bin1 = "0101011"; bin2 = "011";

Output

Yes

Arahan- Kita boleh melakukan perkara berikut untuk menukar rentetan bin1 kepada rentetan bin2.

• Kita boleh menggantikan aksara kedua dengan min(0,1) dan memadamkan aksara pertama. Oleh itu, rentetan menjadi 001011.

• Kami melakukan operasi yang sama sekali lagi dan rentetan menjadi 01011.

• Dalam beberapa operasi seterusnya, rentetan masing-masing menjadi 0011 dan 011.

Masuk

bin1 = "1110"; bin2 = "1110";

Output

Yes

Penjelasan - Rentetan yang diberikan sudah sama.

Masuk

bin1 = "101101"; bin2 = "1110";

Output

No

Penjelasan - Kami tidak boleh menukar rentetan bin1 kepada rentetan bin2 dengan melakukan operasi yang diberikan.

Kaedah 1

Jika panjang rentetan bin1 lebih kecil, kita tidak boleh menukarnya kepada rentetan bin2.

Dalam kes lain, len2 terakhir − 1 aksara rentetan bin1 kekal tidak berubah kerana kami tidak melakukan sebarang operasi padanya. Oleh itu, len2 − 1 aksara terakhir dalam kedua-dua rentetan hendaklah sama.

Selain itu, jika aksara pertama rentetan bin2 ialah '0', kita harus min() aksara permulaan rentetan bin1, dan ia harus mengandungi sekurang-kurangnya satu '0'.

Jika aksara pertama dalam rentetan bin2 ialah '1', kita harus melaksanakan operasi max() pada aksara permulaan rentetan bin2, dan ia harus mengandungi sekurang-kurangnya satu '1'.

Algoritma

Langkah 1 - Jika panjang bin1 kurang daripada panjang rentetan bin2, kembalikan palsu.

Langkah 2 - Lintas tali bin2 bermula dari kedudukan kedua.

Langkah 3 - Jika bin2[p] tidak sama dengan bin1[p + len1 - len2], kembalikan palsu kerana len2 -1 aksara terakhir tidak sama.

Langkah 4 - Lintas len1 pertama - len2 + 1 aksara dan semak jika ia mengandungi bin2[0] aksara. Jika ya, kembalikan benar.

Langkah 5 - Kembalikan palsu pada penghujung fungsi.

Contoh

#include <bits/stdc++.h>
using namespace std;

bool convertAtoB(string bin1, string bin2) {
    int len1 = bin1.size(), len2 = bin2.size();
    // When length 1 is less than length 2
    if (len1 < len2) {
        return false;
    }
    // Check whether substring bin1[p + len1 - len2]... bin1[len1] and bin2[1]... bin2[len2]
    for (int p = 1; p < len2; p++) {
        if (bin1[p + len1 - len2] != bin2[p]) {
            return false;
        }
    }
    // Check whether substring bin1[0... len1 - len2 - 1] contains bin2[0]
    for (int p = 0; p < len1 - len2 + 1; p++) {
        if (bin1[p] == bin2[0]) {
            return true;
        }
    }
    return false;
}
int main() {
    string bin1 = "0101011";
    string bin2 = "011";
    bool res = convertAtoB(bin1, bin2);
    if (res == true) {
        cout << "YES, It is possible to convert bin1 to bin2.";
    } else {
        cout << "NO, It is not possible to convert bin1 to bin2.";
    }
}

Output

YES, It is possible to convert bin1 to bin2.

Kerumitan masa - O(N) untuk memadankan aksara rentetan.

Kerumitan ruang - O(1) kerana kami tidak menggunakan sebarang ruang dinamik.

Kami belajar untuk menukar rentetan binari pertama kepada rentetan binari kedua dengan mengikut operasi yang diberikan. Seorang pengaturcara mungkin cuba menyemak sama ada satu rentetan boleh ditukar kepada rentetan lain dengan menggantikan aksara terakhir dengan nilai minimum atau maksimum aksara kedua terakhir dan terakhir dan mengalih keluar aksara terakhir.

Atas ialah kandungan terperinci Jadikan rentetan binari sama dengan berulang kali menggantikan bit kedua. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!