难以接受Java采访，需要一些提示 [英] stumped on a Java interview, need some hints

问题描述

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

This is an interview problem that I am stuck on:

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

Given a string consisting of a, b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly?

我尝试的解决方案：

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<String> temp = new LinkedList<String>(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<String> deconstruct(String testCase) {
        List<String> temp = new LinkedList<String>();

        for (int i = 0; i < testCase.length(); i++) {
            temp.add(testCase.charAt(i) + "");
        }

        return temp;
    }

    private static String reconstruct(List<String> 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）。但我一直被告知我的代码是错误的。任何人都可以帮我找出错误的位置吗？

The code seems to work fine on test inputs "cab" (prints "2"), "bcab" (prints "1"), and "ccccc" (prints "5"). But I keep getting told that my code is wrong. Can anyone help me figure out where the bug is?

推荐答案

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

As people have already pointed out the error is that your algorithm makes the substitutions in a predefined order. Your algorithm would make the transformation:

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

如果你想使用生成简化字符串的技巧，你需要：

If you want to use the technique of generating the reduced strings, you need to either:

• 在所有可想象的订单中执行一个级别的替换（而不是只有一个预定义的迭代订单）


• 找到一种明智的方法来决定哪个替换将在最后产生最短的字符串

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

If all you need is the length of the reduced string, there is however a much simpler implementation which does not require the reduced strings to be generated. This is an extended version of @Matteo's answer, with some more details and a working (very simplistic) algorithm.

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

I postulate that the following three properties are true about abc-strings under the given set of rules.

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

1. If it is impossible to reduce a string further, all the characters in that string must be the same character.

不可能： 2<回答< string.length 为真

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

While performing a reduction operation, if the counts of each letter prior to the operation is even, the count of each letter after the operation will be odd. Conversely, if the counts of each letter is odd prior to the operation, the counts will be even after the operation.

物业1

物业一是微不足道的。

Property 1

Property one is trivial.

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

Assume: we have a reduced string of length 5 which can be reduced no more.

AAAAA

这是string是减少操作的结果，前一个字符串必须包含一个 B 和一个 C 。以下是可能的父字符串的一些示例：

As this string is the result of a reduction operation, the previous string must've contained one B and one C. Following are some examples of possible "parent strings":

BCAAAA ， AABCAA ， AAACBA

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

For all of the possible parent strings we can easily see that at least one of the C:s and the B:s can be combined with A:s instead of each other. This will result in a string of length 5 which will be further reducible. Hence, we have illustrated that the only reason for which we had an irreducible string of length 5 was that we had made incorrect choice of which characters to combine while performing the reduction operation.

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

This reasoning applies for all reduced strings of any length k such that 2 < k < string.length.

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

If we have for example [numA, numB, numC] = [even, even, even] and perform a reduction operation in which we substitute AB with a C. The count of A and B will decrease by one, making the counts odd, while the count of C will increase by one, making that count odd as well.

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

Similarly to this, if two counts are even and one is odd, two counts will be odd and one even after the operation and vice versa.

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

In other words, if all three counts have the same "evenness", no reduction operation can change that. And, if there are differences in the "evenness" of the counts, no reduction operation can change that.

考虑两个不可减少的字符串：

Consider the two irreducible strings:

A 和 AA

A 注意 [numA， numB，numC] = [奇数，偶数，偶数]
对于 AA 请注意 [numA，numB ，numC] = [偶数，偶数，偶数]

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

Now forget those two strings and assume we are given an input string of length n.

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

If all characters in the string are equal, the answer is obviously string.length.

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

Else, we know from property 2 that it is possible to reduce the string to a length smaller than 3. We also know the effect on evenness of performing reduction operations. If the input string contains even counts of all letters or odd count of all letters, it is impossible to reduce it to a single letter string, since it is impossible to change the evenness structure from [even, even, even] to [odd, even, even] by performing reduction operation.

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

Hence a simpler algorithm would be as follows:

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

这篇关于难以接受Java采访，需要一些提示的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！