给定一个字符串，去掉该字符串中的所有“b”和“ac”，必须替换它们，并且只允许在该字符串上迭代一次。（来源） 谷歌面试问题 )
null
例如：
acbac ==> "" aaac ==> aa ababac ==> aa bbbbd ==> d
我们强烈建议您在继续解决方案之前单击此处并进行练习。
这两个条件是： 1. 所有“b”和“ac”的过滤应为单通 2. 不允许有额外的空间。
方法是使用两个索引变量i和j。我们使用“i”在字符串中向前移动，并使用索引j添加字符，除了“b”和“ac”。这里的诀窍是如何在“c”之前跟踪“a”。一种有趣的方法是使用两状态机。当前一个字符为“a”时，状态保持为2，否则状态为1。 1) 如果状态为1，则如果以下条件之一为真，则不要将当前字符复制到输出 … （a） 当前字符为“b”（我们需要删除“b”） … b） 当前字符为“a”（下一个字符可能为“c”） 2) 如果状态为2且当前字符不是“c”，我们首先需要确保复制前一个字符“a”。然后我们检查当前字符，如果当前字符不是“b”和“a”，那么我们将其复制到输出。
C++
// A C++ program to remove "b" and 'ac' from input string #include <iostream> using namespace std; #define ONE 1 #define TWO 2 // The main function that removes occurrences of "a" and "bc" // in input string void stringFilter( char *str) { // state is initially ONE (The previous character is not a) int state = ONE; // i and j are index variables, i is used to read next // character of input string, j is used for indexes of output // string (modified input string) int j = 0; // Process all characters of input string one by one for ( int i = 0; str[i] != ' ' ; i++) { /* If state is ONE, then do NOT copy the current character to output if one of the following conditions is true ...a) Current character is 'b' (We need to remove 'b') ...b) Current character is 'a' (Next character may be 'c') */ if (state == ONE && str[i] != 'a' && str[i] != 'b' ) { str[j] = str[i]; j++; } // If state is TWO and current character is not 'c' (other- // wise we ignore both previous and current characters) if (state == TWO && str[i] != 'c' ) { // First copy the previous 'a' str[j] = 'a' ; j++; // Then copy the current character if it is not 'a' // and 'b' if (str[i] != 'a' && str[i] != 'b' ) { str[j] = str[i]; j++; } } // Change state according to current character state = (str[i] == 'a' )? TWO: ONE; } // If last character was 'a', copy it to output if (state == TWO) { str[j] = 'a' ; j++; } // Set the string terminator str[j] = ' ' ; } /* Driver program to check above functions */ int main() { char str1[] = "ad" ; stringFilter(str1); cout << str1 << endl; char str2[] = "acbac" ; stringFilter(str2); cout << str2 << endl; char str3[] = "aaac" ; stringFilter(str3); cout << str3 << endl; char str4[] = "react" ; stringFilter(str4); cout << str4 << endl; char str5[] = "aa" ; stringFilter(str5); cout << str5 << endl; char str6[] = "ababaac" ; stringFilter(str6); cout << str6 << endl; return 0; } |
JAVA
// A Java program to remove "b" and // 'ac' from input String import java.util.*; class GFG { static final int ONE = 1 ; static final int TWO = 2 ; // The main function that removes occurrences // of "a" and "bc" in input String static char [] StringFilter( char []str) { // state is initially ONE // (The previous character is not a) int state = ONE; // i and j are index variables, // i is used to read next // character of input String, // j is used for indexes of output // String (modified input String) int j = 0 ; // Process all characters of // input String one by one for ( int i = 0 ; i < str.length; i++) { /* If state is ONE, then do NOT copy the current character to output if one of the following conditions is true ...a) Current character is 'b' (We need to remove 'b') ...b) Current character is 'a' (Next character may be 'c') */ if (state == ONE && str[i] != 'a' && str[i] != 'b' ) { str[j] = str[i]; j++; } // If state is TWO and current character // is not 'c' (otherwise we ignore both // previous and current characters) if (state == TWO && str[i] != 'c' ) { // First copy the previous 'a' str[j] = 'a' ; j++; // Then copy the current character // if it is not 'a' and 'b' if (str[i] != 'a' && str[i] != 'b' ) { str[j] = str[i]; j++; } } // Change state according to current character state = (str[i] == 'a' ) ? TWO : ONE; } // If last character was 'a', // copy it to output if (state == TWO) { str[j] = 'a' ; j++; } return Arrays.copyOfRange(str, 0 , j); } // Driver Code public static void main(String[] args) { char str1[] = "ad" .toCharArray(); str1 = StringFilter(str1); System.out.print(String.valueOf(str1) + "" ); char str2[] = "acbac" .toCharArray(); str2 = StringFilter(str2); System.out.print(String.valueOf(str2) + "" ); char str3[] = "aaac" .toCharArray(); str3 = StringFilter(str3); System.out.print(String.valueOf(str3) + "" ); char str4[] = "react" .toCharArray(); str4 = StringFilter(str4); System.out.print(String.valueOf(str4) + "" ); char str5[] = "aa" .toCharArray(); str5 = StringFilter(str5); System.out.print(String.valueOf(str5) + "" ); char str6[] = "ababaac" .toCharArray(); str6 = StringFilter(str6); System.out.print(String.valueOf(str6) + "" ); } } // This code is contributed by 29AjayKumar |
python
# A Python program to remove "b" and 'ac' from input string ONE = 1 TWO = 2 # Utility function to convert string to list def toList(string): l = [] for x in string: l.append(x) return l # Utility function to convert list to string def toString(l): return ''.join(l) # The main function that removes occurrences of "a" and "bc" # in input string def stringFilter(string): # state is initially ONE (The previous character is not a) state = ONE # i and j are index variables, i is used to read next # character of input string, j is used for indexes of # output string (modified input string) j = 0 # Process all characters of input string one by one for i in xrange ( len (string)): # If state is ONE, then do NOT copy the current character # to output if one of the following conditions is true # ...a) Current character is 'b' (We need to remove 'b') # ...b) Current character is 'a' (Next character may be 'c') if state = = ONE and string[i] ! = 'a' and string[i] ! = 'b' : string[j] = string[i] j + = 1 # If state is TWO and current character is not 'c' (other- # wise we ignore both previous and current characters) if state = = TWO and string[i] ! = 'c' : # First copy the previous 'a' string[j] = 'a' j + = 1 # Then copy the current character if it is not 'a' and 'b' if string[i] ! = 'a' and string[i] ! = 'b' : string[j] = string[i] j + = 1 # Change state according to current character state = TWO if string[i] = = 'a' else ONE # If last character was 'a', copy it to output if state = = TWO: string[j] = 'a' j + = 1 return toString(string[:j]) # Driver program string1 = stringFilter(toList( "ad" )) print string1 string2 = stringFilter(toList( "acbac" )) print string2 string3 = stringFilter(toList( "aaac" )) print string3 string4 = stringFilter(toList( "react" )) print string4 string5 = stringFilter(toList( "aa" )) print string5 string6 = stringFilter(toList( "ababaac" )) print string6 # This code is contributed by BHAVYA JAIN |
C#
// A C# program to remove "b" and // 'ac' from input String using System; class GFG { static readonly int ONE = 1; static readonly int TWO = 2; // The main function that removes occurrences // of "a" and "bc" in input String static char [] StringFilter( char []str) { // state is initially ONE // (The previous character is not a) int state = ONE; // i and j are index variables, // i is used to read next // character of input String, // j is used for indexes of output // String (modified input String) int j = 0; // Process all characters of // input String one by one for ( int i = 0; i < str.Length; i++) { /* If state is ONE, then do NOT copy the current character to output if one of the following conditions is true ...a) Current character is 'b' (We need to remove 'b') ...b) Current character is 'a' (Next character may be 'c') */ if (state == ONE && str[i] != 'a' && str[i] != 'b' ) { str[j] = str[i]; j++; } // If state is TWO and current character // is not 'c' (otherwise we ignore both // previous and current characters) if (state == TWO && str[i] != 'c' ) { // First copy the previous 'a' str[j] = 'a' ; j++; // Then copy the current character // if it is not 'a' and 'b' if (str[i] != 'a' && str[i] != 'b' ) { str[j] = str[i]; j++; } } // Change state according to // current character state = (str[i] == 'a' ) ? TWO : ONE; } // If last character was 'a', // copy it to output if (state == TWO) { str[j] = 'a' ; j++; } return String.Join( "" , str). Substring(0, j).ToCharArray(); } // Driver Code public static void Main(String[] args) { char []str1 = "ad" .ToCharArray(); str1 = StringFilter(str1); Console.Write(String.Join( "" , str1) + "" ); char []str2 = "acbac" .ToCharArray(); str2 = StringFilter(str2); Console.Write(String.Join( "" , str2) + "" ); char []str3 = "aaac" .ToCharArray(); str3 = StringFilter(str3); Console.Write(String.Join( "" , str3) + "" ); char []str4 = "react" .ToCharArray(); str4 = StringFilter(str4); Console.Write(String.Join( "" , str4) + "" ); char []str5 = "aa" .ToCharArray(); str5 = StringFilter(str5); Console.Write(String.Join( "" , str5) + "" ); char []str6 = "ababaac" .ToCharArray(); str6 = StringFilter(str6); Console.Write(String.Join( "" , str6) + "" ); } } // This code is contributed by Rajput-Ji |
输出：
ad aa ret aa aaa
上述问题的一个扩展，我们根本不希望输出中出现“ac”： 上面的代码看起来不错，似乎可以处理所有情况，但如果输入字符串是“aacacc”，那么上面的代码将生成输出为“ac”，这看起来是正确的，因为它删除了连续出现的“a”和“c”。如果要求输出字符串中根本没有“ac”，该怎么办。我们是否可以修改上述程序，使其输出为输入“aacacc”的空字符串，并在输入为“abcaacd”时输出为“d”？事实证明，它也可以在给定的限制下完成。这个想法很简单。我们需要在上面程序的循环中添加以下行。
if (j>1 && str[j-2] == 'a' && str[j-1] == 'c' ) j = j-2; |
看见 这 用于修改程序的不同测试用例。
原始问题的更简单解决方案：
C++
// // A C++ program to remove "b" and 'ac' from input string #include<bits/stdc++.h> using namespace std; void stringFilter( char *str) { int n = strlen (str); int i = -1; // previous character int j = 0; // current character while (j < n) { /* check if current and next character forms ac */ if (j < n-1 && str[j] == 'a' && str[j+1] == 'c' ) j += 2; /* if current character is b */ else if (str[j] == 'b' ) j++; /* if current char is 'c && last char in output is 'a' so delete both */ else if (i >= 0 && str[j] == 'c' && str[i] == 'a' ) i--,j++; /* else copy curr char to output string */ else str[++i] = str[j++]; } str[++i] = ' ' ; } // Driver program to test above function int main() { char str1[] = "ad" ; cout << "Input => " << str1 << "Output => " ; stringFilter(str1); cout << str1 << endl << endl; char str2[] = "acbac" ; cout << "Input => " << str2 << "Output => " ; stringFilter(str2); cout << str2 << endl << endl; char str3[] = "aaac" ; cout << "Input => " << str3 << "Output => " ; stringFilter(str3); cout << str3 << endl << endl; char str4[] = "react" ; cout << "Input => " << str4 << "Output => " ; stringFilter(str4); cout << str4 << endl << endl; char str5[] = "aa" ; cout << "Input => " << str5 << "Output => " ; stringFilter(str5); cout << str5 << endl << endl; char str6[] = "ababaac" ; cout << "Input => " << str6 << "Output => " ; stringFilter(str6); cout << str6 << endl << endl; char str[] = "abc" ; cout << "Input => " << str << "Output => " ; stringFilter(str); cout << str << endl << endl; return 0; } |
JAVA
// A Java program to remove "b" and 'ac' from input string class GfG { // The main function that removes occurrences of "a" and "bc" // in input string static void stringFilter( char str[]) { int n = str.length; int i = - 1 ; // previous character int j = 0 ; // current character while (j < n) { /* check if current and next character forms ac */ if (j < n- 1 && str[j] == 'a' && str[j+ 1 ] == 'c' ) j += 2 ; /* if current character is b */ else if (str[j] == 'b' ) j++; /* if current char is 'c && last char in output is 'a' so delete both */ else if (i >= 0 && str[j] == 'c' && str[i] == 'a' ) { i--; j++; } /* else copy curr char to output string */ else str[++i] = str[j++]; } System.out.println( new String(str).substring( 0 ,i+ 1 )); } /* Driver program to check above functions */ public static void main(String[] args) { String str1 = "ad" ; stringFilter(str1.toCharArray()); String str2 = "acbac" ; stringFilter(str2.toCharArray()); String str3 = "aaac" ; stringFilter(str3.toCharArray()); String str4 = "react" ; stringFilter(str4.toCharArray()); String str5 = "aa" ; stringFilter(str5.toCharArray()); String str6 = "ababaac" ; stringFilter(str6.toCharArray()); } } |
python
# A Python program to remove "b" and 'ac' from input string # Utility function to convert string to list def toList(string): l = [] for x in string: l.append(x) return l # Utility function to convert list to string def toString(l): return ''.join(l) def stringFilter(string): # length of string n = len (string) i = - 1 j = 0 while j < n: # Check if current and next character forms ac if j < n - 1 and string[j] = = 'a' and string[j + 1 ] = = 'c' : j + = 2 # If current character is b elif string[j] = = 'b' : j + = 1 # if current char is 'c && last char in output # is 'a' so delete both elif i > = 0 and string[j] = = 'c' and string[i] = = 'a' : i - = 1 j + = 1 # Else copy curr char to output string else : i + = 1 string[i] = string[j] j + = 1 i + = 1 return toString(string[:i]) # Driver program string1 = "ad" print "Input => " + string1 + "Output => " , print stringFilter(toList(string1)) + "" string2 = "acbac" print "Input => " + string2 + "Output => " , print stringFilter(toList(string2)) + "" string3 = "aaac" print "Input => " + string3 + "Output => " , print stringFilter(toList(string3)) + "" string4 = "react" print "Input => " + string4 + "Output => " , print stringFilter(toList(string4)) + "" string5 = "aa" print "Input => " + string5 + "Output => " , print stringFilter(toList(string5)) + "" string6 = "ababaac" print "Input => " + string6 + "Output => " , print stringFilter(toList(string6)) + "" string7 = "abc" print "Input => " + string7 + "Output => " , print stringFilter(toList(string7)) + "" # This code is contributed by BHAVYA JAIN |
C#
// C# program to remove "b" and 'ac' from input string using System; class GfG { // The main function that removes occurrences of // "a" and "bc" in input string static void stringFilter( char []str) { int n = str.Length; int i = -1; // previous character int j = 0; // current character while (j < n) { /* check if current and next character forms ac */ if (j < n-1 && str[j] == 'a' && str[j+1] == 'c' ) j += 2; /* if current character is b */ else if (str[j] == 'b' ) j++; /* if current char is 'c && last char in output is 'a' so delete both */ else if (i >= 0 && str[j] == 'c' && str[i] == 'a' ) { i--; j++; } /* else copy curr char to output string */ else str[++i] = str[j++]; } Console.WriteLine( new String(str)); } // Driver Code public static void Main() { String str1 = "ad" ; stringFilter(str1.ToCharArray()); String str2 = "acbac" ; stringFilter(str2.ToCharArray()); String str3 = "aaac" ; stringFilter(str3.ToCharArray()); String str4 = "react" ; stringFilter(str4.ToCharArray()); String str5 = "aa" ; stringFilter(str5.ToCharArray()); String str6 = "ababaac" ; stringFilter(str6.ToCharArray()); } } // This code is contributed by //PrinciRaj1992 |
输出：
Input => ad Output => ad Input => acbac Output => Input => aaac Output => aa Input => react Output => ret Input => aa Output => aa Input => ababaac Output => aaa Input => abc Output =>
感谢Gaurav Ahirwar提出了这个更简单的解决方案。
本文由 瓦伦·詹 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
