資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學透過替換萬用字元 '?'，生成一個恰好包含 'a' 個 0 和 'b' 個 1 的迴文二進位制字串。
在處理字串操作問題時，我們經常會遇到需要將給定字串轉換為特定模式或格式的情況。其中一個問題是生成一個包含一定數量的“0”和“1”的迴文二進位制字串，同時替換用“？”表示的萬用字元。
在本文中，我們將探討使用 C++ 解決此問題的有效演算法方法。我們將討論問題陳述及其方法，並分析演算法的時間和空間複雜度。
問題陳述
給定一個由“0”、“1”和萬用字元“?”組成的字串，我們需要透過替換“?”字元將其轉換為迴文二進位制字串。最終的迴文字串應恰好包含 'a' 個“0”和 'b' 個“1”，其中 'a' 和 'b' 是給定的整數。如果無法形成這樣的迴文，則應返回 -1。
方法
初始化兩個指標，“left”和“right”，分別指向字串的開頭和結尾。
使用 for 迴圈統計“0”和“1”的出現次數。此步驟有助於我們確定字串中已存在的“0”和“1”的數量。然後，相應地減少 'a' 和 'b' 的值。
當 “left” 小於 “right” 時，迭代字串。
如果 “S[left]” 和 “S[right]” 都是“?”字元：
如果“0”的數量（用 'a' 表示）大於“1”的數量（用 'b' 表示），則將 “S[left]” 和 “S[right]” 設定為“0”並將 'a' 減 2；
否則，將 “S[left]” 和 “S[right]” 設定為“1”並將 'b' 減 2。
如果 “S[left]” 是“?”，“S[right]” 不是“?”：
如果 S[right] 等於“0”，則將 “S[left]” 設定為“0”並將 'a' 減 1；
否則，將 “S[left]” 設定為“1”並將 'b' 減 1。
如果 “S[right]” 是“?”，“S[left]” 不是“?”：
如果 S[left] 等於“1”，則將 “S[right]” 設定為“1”並將 'b' 減 1；
否則，將 “S[right]” 設定為“0”並將 'a' 減 1。
如果 “S[left]” 不是“?”，“S[right]” 也不是“?”，但它們不相等，則無法形成迴文，因此返回 -1。
將 “left” 指標向右移動，將 “right” 指標向左移動。
對於奇數長度的字串，如果中間元素為“?”：
如果“0”的數量（'a'）大於“1”的數量（'b'），則將中間元素設定為“0”並將 'a' 減 1；
否則，將中間字元設定為“1”並將 'b' 減 1。
檢查 'a' 和 'b' 是否都為零。如果都為零，則返回最終的迴文二進位制字串；否則，返回 -1。
示例
現在，讓我們在不同的程式語言中實現上述方法：C、C++、Java 和 Python。
#include <stdio.h>
#include <string.h>
// Function to convert the string
// to a binary palindromic string with 'a' 0's and 'b' 1's
char* palindromicString(char S[], int a, int b){
int left = 0;
int right = strlen(S) - 1;
// count '0's and '1's in S
for (int i = 0; i < strlen(S); i++) {
if (S[i] == '0') {
a--;
} else if (S[i] == '1') {
b--;
}
}
// Replace '?' characters based on conditions
while (left < right) {
if (S[left] == '?' && S[right] == '?') {
if (a > b) {
S[left] = S[right] = '0';
a -= 2;
} else {
S[left] = S[right] = '1';
b -= 2;
}
} else if (S[left] == '?' && S[right] != '?') {
if (S[right] == '0') {
S[left] = S[right];
a--;
} else {
S[left] = S[right];
b--;
}
} else if (S[right] == '?' && S[left] != '?') {
if (S[left] == '0') {
S[right] = S[left];
a--;
} else {
S[right] = S[left];
b--;
}
} else if (S[left] != S[right]) {
return "-1";
}
left++;
right--;
}
// If the string length is odd, handle the case of the middle character.
if (strlen(S) % 2 != 0 && S[strlen(S) / 2] == '?') {
if (a > b) {
S[strlen(S) / 2] = '0';
a--;
} else {
S[strlen(S) / 2] = '1';
b--;
}
}
// Return the palindromic binary string if 'a' and 'b' are both zero, else return -1.
if (a == 0 && b == 0) {
return S;
} else {
return "-1";
}
}
int main(){
char str[] = "01?1???";
int a = 4, b = 3;
printf("%s\n", palindromicString(str, a, b));
return 0;
}
輸出
0101010
#include<iostream>
#include<string>
using namespace std;
// Function to convert the string
// to a binary palindromic string with 'a' 0's and 'b' 1's
string palindromicString(string S, int a, int b) {
int left = 0;
int right = S.size() - 1;
// count '0's and '1's in S
for(auto s: S){
if(s=='0'){
a--;
} else if(s=='1'){
b--;
}
}
// Replace '?' characters based on conditions
while (left < right) {
if (S[left] == '?' && S[right] == '?') {
if (a > b) {
S[left] = S[right] = '0';
a -= 2;
} else{
S[left] = S[right] = '1';
b -= 2;
}
} else if (S[left] == '?' && S[right] != '?') {
if(S[right]=='0'){
S[left]=S[right];
a--;
} else{
S[left]=S[right];
b--;
}
} else if (S[right] == '?' && S[left] != '?') {
if(S[left]=='0'){
S[right]=S[left];
a--;
} else{
S[right]=S[left];
b--;
}
} else if (S[left] != S[right]) {
return "-1";
}
left++;
right--;
}
// If the string length is odd, handle the case of the middle character.
if (S.size() % 2 != 0 && S[S.size() / 2] == '?') {
if (a > b) {
S[S.size() / 2] = '0';
a--;
} else {
S[S.size() / 2] = '1';
b--;
}
}
// Return the palindromic binary string if 'a' and 'b' are both zero, else return -1.
if (a == 0 && b == 0) {
return S;
} else {
return "-1";
}
}
int main() {
string str = "01?1???";
int a = 4, b = 3;
cout << palindromicString(str, a, b) << endl;
return 0;
}
輸出
0101010
public class PalindromicString {
static String palindromicString(String str, int a, int b) {
char[] S = str.toCharArray();
int left = 0;
int right = S.length - 1;
// count '0's and '1's in S
for (char s : S) {
if (s == '0') {
a--;
} else if (s == '1') {
b--;
}
}
// Replace '?' characters based on conditions
while (left < right) {
if (S[left] == '?' && S[right] == '?') {
if (a > b) {
S[left] = S[right] = '0';
a -= 2;
} else {
S[left] = S[right] = '1';
b -= 2;
}
} else if (S[left] == '?' && S[right] != '?') {
if (S[right] == '0') {
S[left] = S[right];
a--;
} else {
S[left] = S[right];
b--;
}
} else if (S[right] == '?' && S[left] != '?') {
if (S[left] == '0') {
S[right] = S[left];
a--;
} else {
S[right] = S[left];
b--;
}
} else if (S[left] != S[right]) {
return "-1";
}
left++;
right--;
}
// If the string length is odd, handle the case of the middle character.
if (S.length % 2 != 0 && S[S.length / 2] == '?') {
if (a > b) {
S[S.length / 2] = '0';
a--;
} else {
S[S.length / 2] = '1';
b--;
}
}
// Return the palindromic binary string if 'a' and 'b' are both zero, else return -1.
if (a == 0 && b == 0) {
return new String(S);
} else {
return "-1";
}
}
public static void main(String[] args) {
String str = "01?1???";
int a = 4, b = 3;
System.out.println(palindromicString(str, a, b));
}
}
輸出
0101010
def palindromic_string(s, a, b):
S = list(s)
left = 0
right = len(S) - 1
# count '0's and '1's in S
for char in S:
if char == '0':
a -= 1
elif char == '1':
b -= 1
# Replace '?' characters based on conditions
while left < right:
if S[left] == '?' and S[right] == '?':
if a > b:
S[left] = S[right] = '0'
a -= 2
else:
S[left] = S[right] = '1'
b -= 2
elif S[left] == '?' and S[right] != '?':
if S[right] == '0':
S[left] = S[right]
a -= 1
else:
S[left] = S[right]
b -= 1
elif S[right] == '?' and S[left] != '?':
if S[left] == '0':
S[right] = S[left]
a -= 1
else:
S[right] = S[left]
b -= 1
elif S[left] != S[right]:
return "-1"
left += 1
right -= 1
# If the string length is odd, handle the case of the middle character.
if len(S) % 2 != 0 and S[len(S) // 2] == '?':
if a > b:
S[len(S) // 2] = '0'
a -= 1
else:
S[len(S) // 2] = '1'
b -= 1
# Return the palindromic binary string if 'a' and 'b' are both zero, else return -1.
if a == 0 and b == 0:
return ''.join(S)
else:
return "-1"
if __name__ == "__main__":
s = "01?1???"
a, b = 4, 3
print(palindromic_string(s, a, b))
輸出
0101010
複雜度分析
時間複雜度 - 演算法對字串進行正向遍歷以統計“0”和“1”的出現次數，這需要 O(N) 時間，其中 N 是字串的長度。然後，它從兩端迭代字串，這需要 O(N/2) 時間。總的來說，該解決方案的時間複雜度為 O(N)。
空間複雜度 - 由於需要儲存輸入字串和其他一些需要常量空間的變數，該解決方案的空間複雜度為 O(N)。
測試用例
Test case → "01?1???", a=4, b=3
輸入字串 S 設定為“01?1???”，a 設定為 4，b 設定為 3。
使用給定引數呼叫 palindromicString 函式。
該函式首先將左指標和右指標分別初始化為字串 S 的開頭和結尾。
迭代遍歷 S 中的每個字元以計算“0”和“1”的出現次數，並相應地遞減 a 和 b，結果 a=3，b=1，因為字串中已經有一個“0”和兩個“1”。
該函式進入一個 while 迴圈，該迴圈持續到左指標超過右指標。
在 while 迴圈內，該函式檢查各種條件以根據“0”和“1”的計數替換“?”字元。
在第一次迭代中，S[left] 為“0”，S[right] 為“?”。由於 S[left] 為“0”，它將 S[right] 替換為“0”並將 a 遞減 1，因此現在 a=2。
更新後的字串變為“01?1??0”。
左指標遞增，右指標遞減。
在第二次迭代中，S[left] 為“1”，S[right] 為“?”。由於 S[left] 為“1”，它將 S[right] 替換為“1”並將 b 遞減 1，因此現在 b=0。
更新後的字串變為“01?1?10”。
指標更新。
在第三次迭代中，S[left] 為“?”，S[right] 為“?”。由於 a 大於 b，這兩個“?”字元都替換為“0”，並且 a 遞減 2，因此現在 a=0。
指標更新，這次重疊。因此，while迴圈停止，字串變為“0101010”。
該函式檢查中間字元的情況。由於長度為奇數但中間字元為“1”，因此它不檢查中間元素條件。
最後，該函式檢查 a 和 b 是否都為零。由於 a 為 0 且 b 為 0，因此返回修改後的字串“0101010”。
結果列印到控制檯，結果為“0101010”。
結論
在本文中，我們研究了一種有效的演算法，用於重用萬用字元“?”將給定字串轉換為迴文。透過根據特定條件仔細更改“?”字元，我們可以確保最終字串恰好包含 'a' 個“0”和 'b' 個“1”。我們逐步介紹了該演算法，提供了 C++、C、Java 和 Python 的實現，並分析了該解決方案的時間和空間複雜度。
152 次瀏覽
