数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究检查是否可以通过移除非相邻字符将二进制字符串排序为降序
在这个问题中，我们需要通过移除仅非相邻元素来将给定的二进制字符串排序为降序。
为了解决这个问题，我们需要移除二进制字符串中所有位于1之前的0。如果我们在字符串的任何位置发现两个连续的1位于两个连续的0之后，这意味着我们无法将字符串排序为降序。否则，在每种情况下我们都可以对其进行排序。
问题陈述 − 我们得到了一个长度等于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”来排序字符串，但我们不能移除相邻的“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，则从函数返回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)
结论
我们学习了两种方法，通过仅移除非相邻字符来将二进制字符串排序为降序。这两种方法都使用相同的逻辑，代码中只有细微的更改。第二种方法的代码比第一种方法的代码更易读。
浏览量：102
