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

Question

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

给定由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<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")上正常工作.但我一直被告知我的代码是错误的.任何人都可以帮我找出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代替AB.A和B的计数将减少1,使计数变为奇数,而C的计数将增加1,使得计数奇数为好.

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

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

得出由属性产生的结论

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

A 和 AA

如需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

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).我们可以缓存结果的事实是由于字母的顺序不会改变答案,因为上面的许多帖子已经证明了.

我的解决方案发布在下面

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

#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;
}