检查一个二进制字符串是否可以通过删除非相邻字符来按降序排序

在这个问题中，我们需要通过仅删除不相邻的元素来按降序对给定的二进制字符串进行排序。

为了解决这个问题，我们需要删除二进制字符串中所有位于 1 之前的 0。如果我们在字符串中的任何位置发现两个连续的零后面有两个连续的1，则意味着我们无法对字符串进行降序排序。否则，我们可以针对每种情况进行分类。

问题陈述 - 我们给定了长度等于 N 的二进制字符串 str。我们需要检查是否可以通过从字符串中删除多个不相邻的字符来按降序对给定字符串进行排序。给定的字符串。如果字符串可以降序排序，则打印“yes”；否则，打印“否”。

示例

Input –  str = "10101100"

Output – “YES”

说明

我们可以从第二个和第四个位置删除“0”，以降序对字符串进行排序。

Input –  str = "11000"

Output – “YES”

说明

字符串已经排序。

Input –  str = “010001100”

Output – “NO”

说明

这里，我们需要去掉第1、3、4、5个位置的0来对字符串进行排序，但不能去掉相邻的0。另外，我们可以通过删除所有“1”来对字符串进行排序，但这也是不可能的，因为两个“1”是相邻的。

方法 1

在这种方法中，我们将从末尾开始遍历字符串。如果我们找到两个连续的“1”，则打破循环。之后，我们检查字符串是否包含两个连续的“0”。如果是，我们返回 false。否则，我们返回 true。

算法

• 步骤 1 - 开始使用 for 循环从 'len – 2' 到 0 遍历字符串。这里，'len' 是给定二进制字符串的长度。

• 步骤 2 - 如果 str[i] 和 str[i+1] 都等于“1”，则使用“break”关键字终止循环。

• 第 3 步 - 现在，开始从第 i 个索引开始遍历字符串。

• 步骤 4 - 如果 str[j] 和 str[j+1] 都等于 '0'，则返回 0。如果循环成功终止，则返回 1。

• 第 5 步 - 根据 isSortPossible() 函数的返回值在驱动程序代码中打印“YES”或“NO”。

示例

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

输出

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

时间复杂度 - O(N)，当我们迭代字符串时。

空间复杂度 - O(1)

方法2

在这种方法中，我们将使用与第一种方法相同的逻辑，但我们优化了代码以使其更具可读性。在这里，我们将仅使用单个循环，而不是使用两个单独的循环来检测两个连续“0”后的两个连续“1”。

算法

• 第 1 步 - 定义“isTwoZeros”变量并使用“false”值进行初始化。

• 第 2 步 - 开始从第 0 个索引到“len – 1”迭代字符串。

• 步骤 3 - 如果 str[i] 和 str[I + 1] 为“0”且“isTwoZeros”等于 false，则将“isTwoZeros”的值更改为 true 。这意味着我们在给定的字符串中得到了两个连续的零。

• 步骤 4 - 在 else 部分，如果 str[i] 和 str[I + 1] 为 '1' 并且 'isTwoZeros' 等于 true，则从功能。这意味着我们在两个连续的零之后得到了两个连续的“1”。

• 第 5 步 - 当 for 循环的所有迭代终止时返回 true。

示例

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

输出

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

时间复杂度 - O(N)

空间复杂度 - O(1)

结论

我们学习了两种通过仅删除不相邻字符来按降序对二进制字符串进行排序的方法。两种方法都使用相同的逻辑，对代码的更改最少。第二种方法的代码比第一种方法的代码更具可读性。