透過重複將兩個連續的0替換為單一1，使給定的二進位字串相等

在任何程式語言中，二進位字串是由字元0和1組成的集合。在每個階段，二進位字串遵循的方法是字串只能包含這兩個字元。

連續字串中的字元是指索引之間的差為1的字元。讓我們考慮兩個索引，i和j，如果|j-i| = 1，則它們稱為連續的。

在C 中，如果兩個字串等價，則表示：

• 兩個字串中對應的字元相同。

• 字串的長度相等，且對應索引處的字元重合。

說明問題陳述的一些例子如下 -

範例範例

str1 - “10001”

str2 - “101”

解決方案-

str1 無法轉換為 str2，因為在將 str1 轉換為建立等效字串 str2 的過程中，我們將得到 str1 為“1011”，而 str2 是“101”。

範例2 - 讓我們考慮以下輸入−

#str1 - “001”

str2 - “11”

解決方案-

str1可以透過將前兩個零改為一個1來轉換為str2。

使用C 中的字元匹配和字串遍歷可以解決以下問題。

演算法

• 步驟 1 - 兩個指標 i 和 j 分別用於同時迭代字串 s1 和 s2。

• 第 2 步 - 如果兩個索引處的字元匹配，我們將增加 i 和 j 指標。

• 步驟3 − 如果字元不相等，我們檢查第i個和第(i 1)個索引處的字元是否為'0'，以及第j個索引處的字符是否為'1'。

• 第四步 - 如果有這樣的情況，可以進行轉換。 i指標增加兩個位置，j增加一個索引位置，因為兩個零都被轉換為一。

• 第五步 - 如果字元不相等，且上述情況也不存在，則無法進行轉換。

• 步驟 6 − 如果指標 i 和 j 都成功到達結尾位置，則可以將 s1 轉換為 s2。

範例

以下程式碼片段將兩個二進位字串作為輸入，並根據指定條件檢查這兩個字串是否可以透過簡單的字元替換來等效

//including the required libraries
#include <bits/stdc++.h>
using namespace std;

//convert consecutive 0's to 1
bool convertBinary(string s1, string s2){

   //fetching the lengths of both the strings
   int len1 = s1.length();
   int len2 = s2.length();
   string temp ="";

   //maintaining counters of both the strings
   int i = 0, j = 0;

   //iterating over both the strings simultaneously
   while (i < len1 && j < len2) {

      //if both the characters are equivalent in nature
      //skip to next character
      if (s1[i] == s2[j]) {
         temp+=s1[i];

         //incrementing both pointers
         i++;
         j++;
      }

      // if both characters differ
      else {

         // checking if '00' of s1 can be converted to '1' of s2
         if(s2[j]=='1' && s1[i]=='0'){

            //checking if i+1th index exists and is equivalent to 0
            if(i+1 < len1 && s1[i+1]=='0'){

               //conversion is possible
               //skip two 0's of s1 since converted to 1 in s2
               temp+='1';
               i += 2;
               j++;
            } else {
               return false;
            }
         }

         // If not possible to combine
         else {
            return false;
         }
      }
   }
   cout<<"Entered string2 "<<s2<<"\n";
   cout<<"Converted string1 "<<temp<<"\n";

   //check if both the strings are returned to end position
   if (i == len1 && j == len2)
      return true;
      return false;
}

// calling the conversion rate
int main(){
   string str1 = "100100";
   string str2 = "1111";

   //capturing result
   cout<<"Entered string1 "<<str1<<"\n";
   bool res = convertBinary(str1, str2);
   if (res)
      cout << "First string can be converted to second";
   else
      cout << "First string can't be converted to second";
   return 0;
}

輸出

Entered string1 100100
Entered string2 1111
Converted string1 1111
First string can be converted to second

結論

由於此方法可以有效地逐個字元比較輸入字串，時間複雜度為 O(min(字串長度))。字串遍歷是解決字串問題的一個重要方面。

以上是透過重複將兩個連續的0替換為單一1，使給定的二進位字串相等的詳細內容。更多資訊請關注PHP中文網其他相關文章！