資料結構
網路
關係資料庫管理系統 (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
