檢查一個二進位字串是否可以透過刪除非相鄰字元來按降序排序

在這個問題中，我們需要透過僅刪除不相鄰的元素來按降序對給定的二進位字串進行排序。

為了解決這個問題，我們需要刪除二進位字串中所有位於 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。 p>

• 第 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)

結論

我們學習了兩種透過僅刪除不相鄰字元來按降序對二進位字串進行排序的方法。兩種方法都使用相同的邏輯，對程式碼的變更最少。第二種方法的程式碼比第一種方法的程式碼更具可讀性。

以上是檢查一個二進位字串是否可以透過刪除非相鄰字元來按降序排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！