这是我坚持的面试问题:



我尝试的解决方案:

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”)上正常工作。但是我一直被告知我的代码是错误的。谁能帮助我找出错误所在?

最佳答案

正如人们已经指出的那样,错误是您的算法以预定义的顺序进行替换。您的算法将进行转换:
abcc --> ccc代替abcc --> aac --> ab --> c
如果要使用生成精简字符串的技术,则需要:

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

  • 如果您只需要缩小后的字符串的长度,则可以简单得多
    不需要生成减少的字符串的实现。这是@Matteo答案的扩展版本,具有更多详细信息和有效的(非常简单的)算法。

    简单属性

    我假设以下三个属性对于给定规则下的abc-strings是正确的。
  • 如果无法进一步缩小字符串,则该字符串中的所有字符必须为同一字符。
  • 不可能:2 < answer < string.length是真实的
  • 在执行归约运算时,如果运算前每个字母的计数为偶数,则运算后每个字母的计数将为奇数。相反,如果在操作之前每个字母的计数为奇数,则在操作之后的计数将为偶数。

  • 属性(property)1

    属性一是微不足道的。

    属性2(示例说明)

    假设:我们有一个长度为5的精简串,以后再也不能精简。
    AAAAA
    由于此字符串是归约运算的结果,因此前一个字符串必须包含一个B和一个C。以下是一些可能的“父字符串”的示例:
    BCAAAAAABCAAAAACBA
    对于所有可能的父字符串,我们可以很容易地看到C:s和B:s中的至少一个可以与A:s而不是彼此组合。这将导致长度为5的字符串,该字符串将进一步减少。因此,我们已经说明了我们拥有不可约的长度为5的字符串的唯一原因是,我们在执行归约运算时没有正确选择要合并的字符。

    此推理适用于所有长度为k的简化字符串,例如2 < k < string.length

    属性3(示例说明)

    例如,如果我们有[numA, numB, numC] = [even, even, even]并执行一个归约运算,在该运算中我们用AB代替C。A和B的计数将减少一,使计数为奇数,而C的计数将增加一,使该计数为奇数也一样

    与此类似,如果两个计数为偶数且一个为奇数,则两个计数将为奇数,而一个运算后甚至为一个,反之亦然。

    换句话说,如果所有三个计数都具有相同的“均匀度”,则任何归约运算都不能更改该数值。并且,如果计数的“均匀性”存在差异,则任何减法运算都无法更改该数值。

    从属性得出结论

    考虑两个不可约的字符串:
    AAA
    对于A,请注意[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
    

    关于java - 陷入Java面试中,需要一些提示,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/8033553/

    10-12 02:11