Rendre les chaînes binaires égales en remplaçant à plusieurs reprises le deuxième bit

Dans ce problème, nous devons convertir la chaîne bin1 en chaîne bin2 en remplaçant le deuxième caractère de la chaîne bin1 par la valeur minimale ou maximale parmi les premier et deuxième caractères, et supprimer le premier caractère.

Puisque nous devons supprimer le premier caractère, nous devons nous assurer que les derniers caractères len2 − 1 des deux chaînes sont identiques. De plus, nous devons nous assurer que nous pouvons obtenir le premier caractère de la deuxième chaîne en effectuant l'opération donnée sur le caractère de départ de la chaîne bin1.

Énoncé du problème - Nous recevons des chaînes binaires bin1 et bin2 de longueur len1 et len2 respectivement. Nous devons vérifier si nous pouvons convertir la chaîne bin1 en chaîne bin2 en procédant comme suit.

• Mettez à jour le deuxième caractère de la chaîne bin1 en utilisant la valeur minimale ou maximale des premier et deuxième caractères de la chaîne bin1.

• Supprimez le premier caractère de la chaîne bin1 et la taille de la chaîne sera réduite de 1 à chaque fois.

Exemple

Entrez

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

Sortie

Yes

Instructions- Nous pouvons faire ce qui suit pour convertir la chaîne bin1 en chaîne bin2.

• Nous pouvons remplacer le deuxième caractère par min(0,1) et supprimer le premier caractère. La chaîne devient donc 001011.

• Nous effectuons à nouveau la même opération et la chaîne devient 01011.

• Dans les prochaines opérations, la chaîne devient respectivement 0011 et 011.

Entrez

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

Sortie

Yes

Explication - Les chaînes données sont déjà les mêmes.

Entrez

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

Sortie

No

Explication - Nous ne pouvons pas convertir la chaîne bin1 en chaîne bin2 en effectuant l'opération donnée.

Méthode 1

Si la longueur de la chaîne bin1 est plus petite, nous ne pouvons pas la convertir en chaîne bin2.

Dans les autres cas, les derniers caractères len2 − 1 de la chaîne bin1 restent inchangés car nous n'effectuons aucune opération dessus. Par conséquent, les derniers caractères len2 − 1 des deux chaînes doivent être identiques.

De plus, si le premier caractère de la chaîne bin2 est « 0 », nous devrions min() le caractère de départ de la chaîne bin1, et elle doit contenir au moins un « 0 ».

Si le premier caractère de la chaîne bin2 est « 1 », nous devons effectuer l'opération max() sur le caractère de départ de la chaîne bin2, et elle doit contenir au moins un « 1 ».

Algorithme

Étape 1 - Si la longueur de bin1 est inférieure à la longueur de la chaîne bin2, retournez false.

Étape 2 - Parcourez la chaîne bin2 en commençant par la deuxième position.

Étape 3 - Si bin2[p] n'est pas égal à bin1[p + len1 - len2], renvoyez false car les derniers caractères len2 -1 ne sont pas les mêmes.

Étape 4 - Parcourez les premiers caractères len1 - len2 + 1 et vérifiez s'il contient des caractères bin2[0]. Si oui, retournez vrai.

Étape 5 - Renvoie false à la fin de la fonction.

Exemple

#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.";
    }
}

Sortie

YES, It is possible to convert bin1 to bin2.

Complexité temporelle - O(N) pour faire correspondre les caractères de chaîne.

Complexité spatiale - O(1) puisque nous n'utilisons aucun espace dynamique.

Nous avons appris à convertir la première chaîne binaire en deuxième chaîne binaire en suivant les opérations données. Un programmeur peut essayer de vérifier si une chaîne peut être convertie en une autre en remplaçant le dernier caractère par la valeur minimale ou maximale des caractères de dernière et de dernière seconde et en supprimant le dernier caractère.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!