难以接受Java采访，需要一些提示

这是一个我坚持的面试问题：

给定由a，b和c组成的字符串，我们可以执行以下操作：取两个相邻的不同字符并将其替换为第三个字符。 例如，如果’a’和’c’相邻，则可以用’b’代替。 重复应用此操作可以产生的最小字符串是多少？

我试图解决的问题

import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.List; public class Solution { public static void main(String[] args) { try { BufferedReader in = new BufferedReader(new InputStreamReader( System.in)); System.out.println(solve(in.readLine())); in.close(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } } private static int solve(String testCase) { LinkedList temp = new LinkedList(deconstruct(testCase)); for (int i = 0; i < (temp.size() - 1); i++) { if (!temp.get(i).equals(temp.get(i + 1))) { temp.add(i, getThirdChar(temp.remove(), temp.remove())); i = -1; } } return reconstruct(temp).length(); } private static List deconstruct(String testCase) { List temp = new LinkedList(); for (int i = 0; i < testCase.length(); i++) { temp.add(testCase.charAt(i) + ""); } return temp; } private static String reconstruct(List temp) { String testCase = ""; for (int i = 0; i < temp.size(); i++) { testCase += temp.get(i); } return testCase; } private static String getThirdChar(String firstChar, String secondChar) { return "abc".replaceAll("[" + firstChar + secondChar + "]+", ""); } } 

代码似乎在测试输入“cab”（打印“2”），“bcab”（打印“1”）和“ccccc”（打印“5”）上正常工作。 但我一直被告知我的代码是错误的。 任何人都可以帮我弄清楚bug的位置吗？

Answer 1

正如人们已经指出的那样，错误是您的算法以预定义的顺序进行替换。 您的算法将进行转换：

abcc --> ccc而不是abcc --> aac --> ab --> c

如果要使用生成缩减字符串的技术，则需要：

• 在可以想象的所有顺序中的一个级别上执行替换（而不是仅一个预定义的迭代顺序）
• 找到一种聪明的方法来决定哪个替换最终会产生最短的字符串

如果您只需要缩减字符串的长度，则可以实现更简单的实现，而不需要生成缩减字符串。 这是@Matteo答案的扩展版本，包含更多细节和工作（非常简单）的算法。

简单的属性

我假设在给定的规则集下，关于abc-strings，以下三个属性都是正确的。

1. 如果无法进一步减少字符串，则该字符串中的所有字符必须是相同的字符。

2. 不可能： 2 < answer < string.length为真

3. 在执行缩小操作时，如果操作之前的每个字母的计数是偶数，则操作之后的每个字母的计数将是奇数。 相反，如果在操作之前每个字母的计数是奇数，则在操作之后计数将是均匀的。

物业1

财产一是微不足道的。

属性2（示例说明）

假设：我们有一个减少的长度为5的字符串，可以不再减少。

AAAAA

由于此字符串是还原操作的结果，因此前一个字符串必须包含一个B和一个C 以下是可能的“父字符串”的一些示例：

BCAAAA ， AABCAA ， AAACBA

对于所有可能的父字符串，我们可以很容易地看到C：s和B：中的至少一个可以与A：s而不是彼此组合。 这将产生长度为5的串，这将进一步减少。 因此，我们已经说明了我们有一个长度为5的不可缩减字符串的唯一原因是我们在执行缩减操作时错误地选择了要组合的字符。

这种推理适用于任何长度为k的所有减少的字符串，使得2 < k < string.length 。

财产3（示例说明）

如果我们有例如[numA, numB, numC] = [even, even, even]并执行还原操作，其中我们用C替换[numA, numB, numC] = [even, even, even]和B的计数将减少1，使得计数为奇数，而C的计数将增加1，使计数也变为奇数。

与此类似，如果两个计数是偶数而一个是奇数，则两个计数将是奇数，一个甚至在操作之后，反之亦然。

换句话说，如果所有三个计数具有相同的“均匀度”，则没有减少操作可以改变它。 并且，如果计数的“均匀性”存在差异，则减少操作不会改变这一点。

得出由属性产生的结论

考虑两个不可简化的字符串：

A和AA

对于[numA, numB, numC] = [odd, even, even]通知对于AA通知， [numA, numB, numC] = [even, even, even]

现在忘记这两个字符串并假设我们得到一个长度为n的输入字符串。

如果字符串中的所有字符都相等，答案显然是string.length。

另外，我们从属性2知道可以将字符串减小到小于3的长度。我们也知道执行还原操作对均匀性的影响。 如果输入字符串包含所有字母的偶数或所有字母的奇数，则不可能将其减少为单字母字符串，因为无法将均匀性结构从[even, even, even]更改为[odd, even, even]通过执行还原操作。

因此，更简单的算法如下：

算法

 Count the number of occurences of each letter in the input string [numA, numB, numC] If two of these counts are 0, then return string.length Else if (all counts are even) or (all counts are odd), then return 2 Else, then return 1 

Answer 2

这个问题也出现在HackerRank中作为动态编程的介绍。 尽管许多海报已经提出了很好的封闭式解决方案，但我发现仍然可以使用古老的动态编程方式来解决它。 即找到一个好的递归关系并缓存中间结果以避免不必要的计算。

正如一些人已经注意到的那样，当输入字符串很长时，迭代输入字符串的连续字母和所有产生的缩减字符串的暴力方法将不起作用。 这样的解决方案只能通过HackerRank上的一个测试用例。 存储所有减少的字符串也是不可行的，因为这种字符串的数量可以指数增长。 我受益于一些人的评论，即字母的顺序无关紧要，只有每个字母的数字很重要。

只要每个字符串有两个以上不同的字母，就可以减少每个字符串。 每次减少一个字符串时，每个不同字母中的一个消失，第三种字母被添加到字符串中。 这给了我们一个递归关系。 设f(a,b,c)为给定a字母’a’， b的字母’b’和输入字符串中字母’c’的c的最小字符串的长度，则

 f(a,b,c) = min(f(a-1,b-1,c+1), f(a-1,b+1,c-1), f(a+1,b-1,c-1)); 

因为减少字符串有三种可能性。 当然，每个复发关系都受到一些初始条件的影响。 在这种情况下，我们有

 if(a < 0 || b < 0 || c < 0) return MAX_SIZE+1; if(a == 0 && b == 0 && c == 0) return 0; if(a != 0 && b == 0 && c == 0) return a; if(a == 0 && b != 0 && c == 0) return b; if(a == 0 && b == 0 && c != 0) return c; 

这里MAX_SIZE是HackerRank问题中给定字母的最大数量。 每当我们用完一个给定的字母时，返回的最大大小表示此字符串缩减无效。 然后我们可以使用这些初始条件和递归关系计算最小缩减字符串的大小。

但是，这仍然无法通过HackerRank测试用例。 而且，这导致了太多的重复计算。 因此，我们希望在给定元组(a,b,c)缓存计算结果。 我们可以缓存结果的事实是由于字母的顺序不会改变答案，因为上面的许多post已经certificate了。

我的解决方案发布在下面

 #include  #include  #include  #include  #include  #define MAX_SIZE 101 int cache[MAX_SIZE][MAX_SIZE][MAX_SIZE]; void init_cache() { for(int i = 0 ; i < MAX_SIZE; i++) { for (int j = 0; j < MAX_SIZE; j++) { for(int k = 0; k < MAX_SIZE; k++) cache[i][j][k] = -1; } } } void count(char* array, int* a, int* b, int* c) { int len = strlen(array); for(int i = 0; i < len; i++) { if(array[i] == 'a') (*a)++; else if(array[i] == 'b') (*b)++; else (*c)++; } } int solve(int a, int b, int c) { if(a < 0 || b < 0 || c < 0) return MAX_SIZE+1; if(a == 0 && b == 0 && c == 0) return 0; if(a != 0 && b == 0 && c == 0) return a; if(a == 0 && b != 0 && c == 0) return b; if(a == 0 && b == 0 && c != 0) return c; if(cache[a][b][c] != -1) { return cache[a][b][c]; } int ci = solve(a-1, b-1, c+1); int bi = solve(a-1, b+1, c-1); int ai = solve(a+1, b-1, c-1); if(a > 0 && b > 0) cache[a-1][b-1][c+1] = ci; if(a > 0 && c > 0) cache[a-1][b+1][c-1] = bi; if(b > 0 && c > 0) cache[a+1][b-1][c-1] = ai; return ci < bi ? (ci < ai ? ci : ai) : (ai < bi ? ai : bi); } int main() { int res, T, i; scanf("%d", &T); assert(T<=100); char arr[100001]; init_cache(); for(i = 0; i < T; i++) { scanf("%s",arr); int a = 0; int b = 0; int c = 0; count(arr, &a, &b, &c); int len = solve(a, b, c); printf("%d\n", len); } return 0; } 

Answer 3

在我看来，答案是一个数字（或一个生成数字的程序），而不是应用所描述的转换的程序。

出于这个原因，（如果字符串不为空），答案将是1，有几个输入。

但是，如果输入由重复多次的单个字符组成，则不能详细说明字符串，因此输出字符串将与输入字符串相同（即，相同的长度）。

请注意，输入字符串必须由单个字符组成; 如果它有两个字符，输出将为1：baaaa – > caaa – > baa – > ca – > b

请注意，尚未指定替换顺序（如果有超过1个替换可用）。 因此我们不能说更多，但是我们可以观察到一些不是由单个字符组成的字符串不能简化为长度为1的字符串。当所有三个字母按顺序出现时（例如，abc）就是这种情况。 当处理该字符串时，输出将是两个相等字符（例如，cc或aa）的字符串，其不能进一步减少。

Answer 4

你对LinkedList的使用是有趣的（并且可能是意外的），但是其他一些方面有点奇怪和分散注意力……

我的第一直觉是反复遍历String，将字符替换为StringBuilder – 在foor循环周围有一个while循环（如sehe所示）。 这可能是面试官所期待的，而不是你聪明地使用LinkedList。

面试官可能会被这些其他方面分心。 例如：

1. 为什么不使用LinkedList而不是LinkedList 。
2. 为什么不直接从deconstruct(String)返回一个LinkedList 。 不需要包装它。
3. 你真的不需要reconstruct()方法。 只需使用temp.size()

4. 正则表达式是获得第三个字符的一种不受欢迎的方式。 我想不出一个单行，但你可以使用一个数组，如下所示：

    private static Character getThirdChar(Character firstChar, Character secondChar) { List li= new ArrayList(Arrays.asList('a', 'b', 'c')); li.remove(firstChar); li.remove(secondChar); return li.get(0); } 

在这些编辑之后，面试官可能会更清楚地关注您非常有趣的解决方案。

编辑 ：也许问题是要求你返回最小的字符串本身，而不是它的长度。 我认为面试问题的最后一行应该如下所示：“对于给定的字符串，返回可以通过重复应用此操作而产生的最小字符串”

HTH

Answer 5

编辑为了好玩，我做了我自己的版本，在char[]就地操作：

 public class Main { public static void main(String[] args) { System.out.println(solve("abbccaacba")); } private static int solve(String testCase) { if (!testCase.matches("^[abc]*$")) throw new IllegalArgumentException("invalid input"); char[] chars = new char[testCase.length()]; testCase.getChars(0, testCase.length(), chars, 0); int remaining = chars.length; for (int i=0; (i1);) { int next = i+1; while (next < chars.length && (' '==chars[next])) ++next; if (next >= chars.length) break; if (chars[i]!=chars[next]) { switch (chars[i]) { case 'a': chars[next] = ('b'==chars[next])? 'c':'b'; break; case 'b': chars[next] = ('a'==chars[next])? 'c':'a'; break; case 'c': chars[next] = ('b'==chars[next])? 'a':'b'; break; } chars[i] = ' '; // mark as removed remaining--; while (i>0 && (' '!=chars[i-1])) --i; if (' '==chars[i]) i = next; } else ++i; } return remaining; } } 

在http://ideone.com/yhK9t上查看，带有调试输出：

 a 

我在评论中仍然提到注意事项： 编辑嗯，不知何故，我发表评论说答案会因换人的顺序而有所不同

• 从左到右或从右到左（我的版本使用从左到右）
• 深度优先（或广度优先）（我的版本使用深度优先）

Answer 6

 import java.io.BufferedReader; import java.io.InputStreamReader; class Solution { public static void main(String args[]) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(in.readLine()); for (int i = 0; i < T; i++) { String line = in.readLine(); System.out.println(solve(line)); } } public static int[] countOccurrences(String input) { int r[] = new int[3]; char inputArr[] = input.toCharArray(); for (int i = 0; i < inputArr.length; i++) { if (inputArr[i] == 'a') { r[0]++; } else if (inputArr[i] == 'b') { r[1]++; } else if(inputArr[i] == 'c') { r[2]++; } } return r; } private static int solve(String input) { int num[] = countOccurrences(input); if ((num[0]==0 && num[1]==0 )||(num[0]==0 && num[2]==0 )||(num[1]==0 && num[2]==0 )) { return input.length(); } if((num[0]%2==0 && num[1]%2==0 && num[2]%2==0)||(num[0]%2==1 && num[1]%2==1 && num[2]%2==1)) { return 2; } return 1; } } 

Answer 7

Scala中的模式匹配使得更容易选择这样的项目列表。 要减少字符串：

  def reduce[T](xs: List[T]): List[T] = { def reduceImpl(xs1: List[T], accumulator: List[T] = List.empty): List[T] = { xs1 match { case w :: x :: y :: tail if (w != x) => if (w != x) reduceImpl(y :: tail, accumulator) else reduceImpl(x :: y :: tail, w :: accumulator) case remainder => remainder.reverse ::: accumulator } } reduceImpl(xs).reverse } 

然后你可以在结果上调用长度。

是的，我会给出一个Java问题的答案。 100次访谈者中99次不会关心你用什么语言来谈论代码，使用像Scala，Clojure，F＃等东西是正确的方法。 （或者如果没有，他们是找出你实际上并不想在那里工作的正确方法。）

（也是的，那些说答案是一个数字的人是正确的。然而，就像其他人说的那样，这更多是关于面试问题，并且说他们问的不是他们想要问的问题可能是正确的。如果这是他们不止一次使用的标准问题，那么在那里工作是一个（小）坏标志。如果他们在自动屏幕上使用这个问题，那真的不是一个好兆头。）

Answer 8

这是InteviewStreet上的示例问题之一。 我尝试用Java解决它，我的代码产生了给出的三个测试用例的预期结果，但是只传递了十个实际测试用例中的一个。 我在编程和Java方面都很生疏，但这就是我想出来解决三个给定的例子……

我无法正确地获得代码格式…

 import java.io.*; import java.util.Scanner; public class Solution { public String transform(String input) { String output = new String(input); // System.out.println(input); if(output.length() > 1) { int i = 0; while (i < (output.length() - 1)) { if(output.charAt(i) != output.charAt(i+1)) { StringBuffer sb = new StringBuffer(); if (output.charAt(i) == 'a') { // next character is b or c if (output.charAt(i+1) == 'b') { sb.append('c'); } else { sb.append('b'); } } else if (output.charAt(i) == 'b') { // next character is a or c if (output.charAt(i+1) == 'a') { sb.append('c'); } else { sb.append('a'); } } else { // next character is a or b if (output.charAt(i+1) == 'a') { sb.append('b'); } else { sb.append('a'); } } String remainder = output.substring(i+2); if (remainder.length() > 0) { sb.append(remainder); } Solution anotherAnswer = new Solution(); output = anotherAnswer.transform(sb.toString()); } i++; } } return output; } /** * @param args * @throws Exception */ public static void main(String[] args) throws Exception { // TODO Auto-generated method stub Scanner sc; try { sc = new Scanner(new BufferedReader(new FileReader("input.txt"))); // sc = new Scanner(System.in); int numberOfTests = sc.nextInt(); for (int i = 1; i <= numberOfTests; i++) { String testData = sc.next(); Solution answer = new Solution(); String transformedData = answer.transform(testData); System.out.println(transformedData.length()); } } catch (Exception e) { throw new Exception(e); } } }