資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究透過重複將兩個連續的 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 可以轉換為 str2，透過將前兩個零替換為單個 1。
可以使用 C++ 中的字元匹配和字串遍歷來解決以下問題。
演算法
步驟 1 - 使用兩個指標 i 和 j 分別同時遍歷字串 s1 和 s2。
步驟 2 - 如果兩個索引處的字元匹配，則遞增 i 和 j 指標。
步驟 3 - 如果字元不等價，則檢查第 i 個和第 (i+1) 個索引處的字元是否為 '0'，以及第 j 個索引處的字元是否為 '1'。
步驟 4 - 如果存在這種情況，則可以執行轉換。i 指標遞增兩個位置，j 指標遞增一個索引位置，因為兩個零都被轉換為一個。
步驟 5 - 如果字元不等價，並且上述情況也不存在，則無法執行轉換。
步驟 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(字串長度))。字串遍歷是字串問題解決的一個重要方面。
234 次檢視
