Vérifiez si une chaîne binaire peut être triée par ordre décroissant en supprimant les caractères non adjacents

Dans ce problème, nous devons trier la chaîne binaire donnée par ordre décroissant en supprimant uniquement les éléments non adjacents.

Pour résoudre ce problème, nous devons supprimer tous les 0 qui précèdent 1 dans la chaîne binaire. Si nous trouvons deux zéros consécutifs suivis de deux 1 consécutifs n’importe où dans la chaîne, cela signifie que nous ne pouvons pas trier la chaîne par ordre décroissant. Sinon, on peut classer chaque situation.

Énoncé du problème - On nous donne une chaîne binaire str de longueur égale à N. Nous devons vérifier si une chaîne donnée peut être triée par ordre décroissant en supprimant plusieurs caractères non adjacents de la chaîne. la chaîne donnée. Si la chaîne peut être triée par ordre décroissant, imprimez « oui », sinon, imprimez « non ».

Exemple

Input –  str = "10101100"

Output – “YES”

Instructions

Nous pouvons trier la chaîne par ordre décroissant en supprimant le « 0 » de la deuxième et de la quatrième position.

Input –  str = "11000"

Output – “YES”

Instructions

Les chaînes sont triées.

Input –  str = “010001100”

Output – “NO”

Instructions

Ici, nous devons supprimer les 0 aux 1ère, 3ème, 4ème et 5ème positions pour trier la chaîne, mais nous ne pouvons pas supprimer les 0 adjacents. Alternativement, nous pourrions trier la chaîne en supprimant tous les « 1 », mais cela est également impossible car deux « 1 » sont adjacents.

Méthode 1

Dans cette méthode, nous allons parcourir la chaîne en commençant par la fin. Si on trouve deux "1" consécutifs, on brise la boucle. Après cela, nous vérifions si la chaîne contient deux "0" consécutifs. Si c'est le cas, nous retournons false. Sinon, nous retournons vrai.

Algorithme

• Étape 1 - Commencez à parcourir la chaîne de « len – 2 » à 0 en utilisant une boucle for. Ici, « len » est la longueur de la chaîne binaire donnée.

• Étape 2 - Si str[i] et str[i+1] sont égaux à "1", terminez la boucle en utilisant le mot-clé "break".

• Étape 3 - Maintenant, commencez à parcourir la chaîne à partir du i-ème index.

• Étape 4 - Si str[j] et str[j+1] sont égaux à « 0 », renvoyez 0. Renvoie 1 si la boucle se termine avec succès. p>

• Étape 5 - Imprimez "OUI" ou "NON" dans le code du pilote en fonction de la valeur de retour de la fonction isSortPossible().

Exemple

#include <bits/stdc++.h>
using namespace std;
// removing the non-adjacent characters from the given string to make it sorted in descending order
bool isSortPossible(string str, int len){
   int i, j;
   
   // Traverse the string str from the end
   for (i = len - 2; i >= 0; i--){
   
      // if str[i] and str[i + 1] is equal to 1 then break the loop.
      if (str[i] == '1' && str[i + 1] == '1'){
         break;
      }
   }
   
   // start traversing the string from i
   for (int j = i; j >= 0; j--){
      // If str[j] and str[j + 1] is equal to 0 then return false
      if (str[j] == '0' && str[j + 1] == '0'){
         return 0;
      }
   }
   return 1;
}
int main(){
   string str = "10101100";
   int len = str.length();
   cout << "The sorting of the given binary string is possible by removing non-adjacent characters - " << endl;
   if (isSortPossible(str, len))
      cout << "YES" << endl;
   else
      cout << "NO" << endl;

   return 0;
}

Sortie

The sorting of the given binary string is possible by removing non-adjacent characters −
YES

Complexité temporelle - O(N), lorsque nous parcourons la chaîne.

Complexité spatiale - O(1)

Méthode 2

Dans cette méthode, nous utiliserons la même logique que la première méthode, mais nous avons optimisé le code pour le rendre plus lisible. Ici, au lieu d’utiliser deux boucles distinctes, nous n’utiliserons qu’une seule boucle pour détecter deux « 1 » consécutifs après deux « 0 » consécutifs.

Algorithme

• Étape 1 - Définissez la variable "isTwoZeros" et initialisez-la avec la valeur "false".

• Étape 2 - Commencez à itérer la chaîne du 0ème index à « len – 1 ».

• Étape 3 - Si str[i] et str[I + 1] sont "0" et "isTwoZeros" est égal à false, alors changez la valeur de "isTwoZeros" en true . Cela signifie que nous avons deux zéros consécutifs dans la chaîne donnée.

• Étape 4 - Dans la partie else, si str[i] et str[I + 1] sont '1' et 'isTwoZeros' est égal à vrai, alors à partir de la fonction. Cela signifie que nous obtenons deux « 1 » consécutifs après deux zéros consécutifs.

• Étape 5 - Renvoie vrai lorsque toutes les itérations de la boucle for se terminent.

Exemple

#include <bits/stdc++.h>
using namespace std;
// removing the non-adjacent characters from the given string to make it sorted in descending order
bool isSortPossible(string str, int len){
   // to track if there are two adjacent zeros in the string
   bool isTwoZeros = false;
   
   // traverse the string
   for (int i = 0; i < len - 1; i++){
   
      // if two zeros are adjacent, then change the value of isTwoZeros to true
      if (str[i] == '0' && str[i + 1] == '0' && !isTwoZeros){
         isTwoZeros = true;
      }
      else{
      
         // if we find two adjacent ones after finding two adjacent zeros, then return false
         if (str[i] == '1' && str[i + 1] == '1' && isTwoZeros){
            return false;
         }
      }
   }
   
   // return true if we don't find two adjacent ones after finding two adjacent zeros
   return true;
}
int main(){
   string str = "101001100";
   int len = str.length();
   cout << "The sorting of the given binary string is possible by removing non-adjacent characters - " << endl;
   if (isSortPossible(str, len))
      cout << "YES" << endl;
   else
      cout << "NO" << endl;

   return 0;
}

Sortie

The sorting of the given binary string is possible by removing non-adjacent characters - 
NO

Complexité temporelle - O(N)

Complexité spatiale - O(1)

Conclusion

Nous avons appris deux façons de trier une chaîne binaire par ordre décroissant en supprimant uniquement les caractères non adjacents. Les deux méthodes utilisent la même logique avec des modifications minimes du code. Le code de la deuxième approche est plus lisible que celui de la première approche.

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!