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

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

为了解决这个问题，我们需要移除二进制字符串中排在1之前的所有0。如果我们在字符串的任何位置找到两个连续的0后面跟着两个连续的1，那么意味着我们无法按降序排序字符串。否则，在每种情况下我们都可以排序。

问题描述 − 给定长度为N的二进制字符串str。我们需要检查是否可以通过从给定字符串中删除多个非相邻字符来将字符串按降序排序。如果字符串可以按降序排序，则打印’yes’; 否则，打印’no’。

示例

Input –  str = "10101100"

Output – “YES”

解释

我们可以从第2个和第4个位置删除’0’，以便按照降序排序字符串。

Input –  str = "11000"

Output – “YES”

解释

字符串已经排好序了。

Input –  str = “010001100”

Output – “NO”

说明

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

方法1

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

步骤

• 步骤1 - 从’len-2’到0开始使用for循环遍历字符串。这里，’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 - 否则，如果str[i]和str[i + 1]都是‘1’，并且‘isTwoZeros’等于true，则从函数中返回false。这意味着在连续的两个零之后，我们找到了两个连续的‘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)

结论

我们学到了两种方法来通过只删除非相邻字符将二进制字符串按降序排序。这两种方法使用相同的逻辑，代码中只有细微的改动。第二种方法的代码比第一种方法更易读。