数据结构
网络
关系数据库管理系统 (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”。
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
结论
在本文中，我们研究了一种有效的算法，用于重用通配符“?”将给定字符串转换为回文。通过根据特定条件仔细更改“?”字符，我们可以确保最终字符串恰好包含 'a' 个“0”和 'b' 个“1”。我们逐步介绍了该算法，提供了 C++、C、Java 和 Python 的实现，并分析了该解决方案的时间和空间复杂度。
152 次浏览
