数据结构
网络
关系数据库管理系统 (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 次浏览
