2

这是一道面试题。假设我们将工人的工作历史表示为字符串。每个字符串由N字符组成；每个字符都是 { A-- "absence", L-- "late" 和O-- "ok") 之一。如果有两个“缺席”或三个后续“迟到”，系统会发出警报。例如：AOOAO-- 发出警报，ALLOL-- 不发出警报。

编写一个函数（在 Java 中）生成所有大小为 的字符串N，这会引发警报。

我建议遍历所有可能的“工作历史”字符串（很明显如何生成它们）并使用正则表达式过滤所需的字符串。

你会如何处理这个问题？

4

3 回答 3

4

这将是一种不检查任何内容，但只直接生成正确案例的聪明方法：

  1. 使用 N-2 天（即 3^(N-2) 组合）进行所有可能的变化。对于如此获得的每一个变化，通过在每个可能的位置拼接“AA”来制作 N-1 个最终字符串（加上简单地在末尾附加，这就是为什么它是 N-1）。

  2. 重复 N-3 天并在“LLL”中拼接。

  3. 你都完成了。

编辑

现在我看到缺勤不一定是连续的。这稍微改变了解决方案：在第一种情况下，您将独立拼接两个“A”，第一个，然后另一个到结果字符串中。

编辑 2

有一个非常对称的附加检查，可以在拼接时避免重复。在这两个步骤中，检查插入点左侧的字符。第1步，如果是A，则停止当前的拼接迭代（这也控制了第二个A的拼接）。在第2步中，如果是L，则转到下一个插入点（跳过当前插入点）。

于 2012-05-25T20:02:53.993 回答
1

对于完全不同的东西，这里有一种方法可以准确地生成所需的字符串，仅此而已。将其视为一个状态机，并使每个状态成为一个函数。非常冗长但直截了当。（如果你做了很多这样的事情，你可以很容易地安排自动生成这个代码。）

因为我们被要求使用 Java，所以这里是 Java。（我还在 Perl 中编写了相同的代码。我只是.=用chop字符串代替了StringBuilder它，它的运行速度比 Java 版本快 3 倍。奇怪。）

import java.io.*;

public class ListAllAlarmedStrings {
    static StringBuilder builder;
    static int length;

    public static void main(String[] args) throws IOException {
        length = 5;
        if (args.length > 0) {
            try {
                length = Integer.parseInt(args[0]);
            } catch (NumberFormatException e) {
                System.err.println("Argument" + " must be an integer");
                System.exit(1);
            }
        }
        builder = new StringBuilder(length);
        for (int i = 0; i < length; i++)
          builder.append("O");
        stateA(0, 'A');
        stateL(0, 'L');
        stateNone(0, 'O');
    }

    static void stateNone (int pos, char chr) {
        if (length < pos + 3)
            return;
        builder.setCharAt(pos, chr);
        //System.out.println("stateNone " + pos + " " +builder.toString());
        stateA(pos + 1, 'A');
        stateL(pos + 1, 'L');
        stateNone(pos + 1, 'O');
    }

    static void stateL (int pos, char chr) {
        if (length < pos + 3)
            return;
        builder.setCharAt(pos, chr);
        //System.out.println("stateL " + pos + " " +builder.toString());
        stateA(pos + 1, 'A');
        stateLL(pos + 1, 'L');
        stateNone(pos + 1, 'O');
    }

    static void stateLL (int pos, char chr) {
        if (length < pos + 2)
            return;
        builder.setCharAt(pos, chr);
        //System.out.println("stateLL " + pos + " " +builder.toString());
        stateA(pos + 1, 'A');
        stateAlarmed(pos + 1, 'L');
        stateNone(pos + 1, 'O');
    }

    static void stateA (int pos, char chr) {
        if (length < pos + 2)
            return;
        builder.setCharAt(pos, chr);
        //System.out.println("stateA " + pos + " " +builder.toString());
        stateAlarmed(pos + 1, 'A');
        stateAL(pos + 1, 'L');
        stateA(pos + 1, 'O');
    }

    static void stateAL (int pos, char chr) {
        if (length < pos + 2)
            return;
        builder.setCharAt(pos, chr);
        //System.out.println("stateAL " + pos + " " +builder.toString());
        stateAlarmed(pos + 1, 'A');
        stateALL(pos + 1, 'L');
        stateA(pos + 1, 'O');
    }

    static void stateALL (int pos, char chr) {
        if (length < pos + 2)
            return;
        builder.setCharAt(pos, chr);
        //System.out.println("stateALL " + pos + " " +builder.toString());
        stateAlarmed(pos + 1, 'A');
        stateAlarmed(pos + 1, 'L');
        stateA(pos + 1, 'O');
    }

    static void stateAlarmed (int pos, char chr) {
        if (length <= pos)
            return;
        if (length == pos + 1) {
            builder.setCharAt(pos, chr);
            System.out.println(builder.toString());
            return;
        }
        builder.setCharAt(pos, chr);
        stateAlarmed(pos + 1, 'A');
        stateAlarmed(pos + 1, 'L');
        stateAlarmed(pos + 1, 'O');
    }
}
于 2012-05-26T17:50:29.907 回答
1

这是一个类似于蛮力的解决方案，除了一些优化。这个想法是创建所有可能序列的组合（没有额外的成本，因为必须返回警报字符串）。然后跟踪警报条件（绝对没有正则表达式），以便只需要检查当前字符（参见＃2）。一旦子字符串引发了警报，比如说位置 i，该函数可以继续为 ni 字符创建组合，而无需检查警报条件。

  1. 创建一个大小为 N 的 char 数组和一个计算组合的函数 ( 3^N)。
  2. 创建一个变量numLate，它将跟踪到目前为止系列中连续的“L”，以及一个变量numAbsences，它将跟踪迄今为止系列中“A”的数量。
  3. 在组合过程中的每个步骤，检查以下内容：
    • 如果已经找到匹配项 ( match == true) 继续。
    • 否则：
      • 检查当前字符是否为“A”，如果是则增加numAbsences。如果numAbsences > 1，设置match = true。继续。
      • 如果当前字符为 'L' 递增numLate，否则设置numLate = 0。如果numLate > 2，设置match = true。继续。

组合过程中，当设置第 N 个字符时，如果match==true返回当前字符串。否则跳过，不匹配。如果您在最后一个字符上并且到目前为止有 0 次缺席，则可以通过不检查缺席来进行其他（次要）优化。或者在组合的最后 2 个字符上，已经有 0 个迟到了。

编辑：我发布了一个递归（groovy）解决方案。例如，Test.combination(0, new char[10], false, 0, 0);返回 55513 个组合，但不确定它是否正确。

class Test{
    public static final char[] rep = ['O', 'A', 'L'];

    public static void combination(int index, char[] arr, boolean match, int numLate, int numAbsence){
        if(index==arr.length){
            if(match)
                println arr;
            return;
        }
        for(int i=0;i<rep.length;i++){
            arr[index] = rep[i];
            if(!match){
                boolean tempMatch = match;
                int tempNumLate = numLate;
                int tempNumAbsence = numAbsence;
                switch(arr[index]){
                    case 'L': tempNumLate++; break;
                    case 'A': tempNumAbsence++; tempNumLate=0; break;
                    default: tempNumLate = 0; break;
                }
                if(tempNumLate > 2)
                    tempMatch = true;
                if(tempNumAbsence > 1)
                    tempMatch = true;

                combination(index+1, arr, tempMatch, tempNumLate, tempNumAbsence);
            }else{
                combination(index+1, arr, match, numLate, numAbsence);
            }
        }
    }
}
于 2012-05-25T19:23:42.390 回答