これは面接の質問です。労働者の作業履歴を文字列として表すとします。各文字列は文字で構成されていNます。各文字は、{ A-"absence"、L-"late"、およびO-"ok"）のいずれかです。2つの「不在」または3つの後続の「遅延」がある場合、システムはアラームを発生させます。例：AOOAO-アラームを発生させますが、ALLOL-発生させません。
Nアラームを発生させるサイズのすべての文字列を生成する関数を（Javaで）記述します。
考えられるすべての「作業履歴」文字列をループして（それらを生成する方法は非常に明白です）、正規表現で必要な文字列をフィルタリングすることを提案します。
この問題にどのようにアプローチしますか？
これは、何もチェックせず、正しいケースのみを直接生成するスマートなアプローチです。
N-2 日 (つまり 3^(N-2) の組み合わせ) ですべての可能なバリエーションを作成します。そのようにして得られたすべてのバリエーションについて、可能なすべての位置で「AA」を接合することにより、N-1 の最終的な文字列を作成します (さらに、最後に単純に追加するため、N-1 になります)。
N-3 日と「LLL」でスプライシングを繰り返します。
これで完了です。
これで、欠席が連続している必要はないことがわかりました。これにより、解決策が少し変わります。最初のケースでは、2 つの「A」を個別に結合し、最初に 1 つ、次にもう 1 つを結果の文字列に結合します。
スプライシング時に重複を回避する、対称的な追加チェックがあります。両方のステップで、挿入ポイントの左側にある文字をチェックします。ステップ 1 で、それが A の場合、現在のスプライシングの繰り返しを停止します (これは、2 番目の A のスプライシングも制御します)。手順 2 で、それが L の場合は、次の挿入ポイントに移動します (現在の挿入ポイントをスキップします)。
完全に異なるものについては、必要な文字列だけを生成するアプローチを次に示します。それをステート マシンと見なし、各ステートを関数にします。非常に冗長ですが、簡単です。(これを頻繁に行っている場合は、このコードを自動生成するように簡単に調整できます。)
Javaを求められたので、Javaです。(同じコードを Perl でも書きました。代わりに文字列に対して.=andを実行しただけで、Java バージョンよりも 3 倍高速に実行されました。奇妙なことです。)chopStringBuilder
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');
}
}
これは、いくつかの最適化を除いて、ブルート フォースに似たソリューションです。アイデアは、可能なすべてのシーケンスの組み合わせを作成することです (アラーム文字列を返す必要があるため、追加コストはかかりません)。次に、現在の文字のみをチェックする必要があるように、アラーム条件を追跡します (絶対に正規表現はありません) (#2 を参照)。部分文字列がアラームを発生させると、たとえば位置 i によって、関数はアラーム条件をチェックせずに ni 文字の組み合わせを作成し続けることができます。
3^N) を作成します。numLateこれまでの一連の連続した「L」を追跡する変数と、これまでのnumAbsences一連の「A」の数を追跡する変数を作成します。match == true) 続行します。numAbsences。の場合numAbsences > 1、 を設定しmatch = trueます。継続する。numLate、そうでない場合は set numLate = 0。の場合numLate > 2、 を設定しmatch = trueます。継続する。組み合わせ中、N 番目の文字が設定されている場合match==trueは、現在の文字列を返します。それ以外の場合はスキップします。一致しません。最後の文字にいて、これまで欠席が 0 だった場合、欠席をチェックしないことで、追加の (マイナーな) 最適化を行うことができます。または組み合わせの最後の 2 文字で、遅れた日数が 0 日です。
編集:再帰的な (グルーヴィーな) ソリューションを投稿しています。たとえば、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);
}
}
}
}