コマンドラインCDコマンドの実装
3738 ワード
ある面接問題はcdコマンドを実現することを要求し、実現構想は以下の通りである:cdが到達する目標経路をスキャンし、ディレクトリ分割子/をスキャンを切り替える分割点とし、スキャンすると.番号は現在のディレクトリに変わりません.「…」文字列にスキャンすると、現在のパスを後ろから/番号を探します.現在のパスは前からこの/番号の位置にあるコンテンツです.他の合法的な文字列にスキャンすると、現在のコンテンツをこの文字列につづります.例を挙げると、現在のパスは、/a/b/cがターゲットディレクトリにカットされ、それぞれ「...」、「d」にスキャンされます.「e」の3つの文字列が「…」にスキャンされると、「/a/b/c」の後から最初の「/」にスキャンされ、現在のパスが「/a/b」になり、「d」にスキャンされると、現在のパスに「d」、すなわち「/a/b/d」が追加され、「e」にスキャンされると、現在のパスに「e」、すなわち「/a/b/d/e」が実装されるアルゴリズムプロセスが追加され、空間を考慮すると、直接ソース文字列上で動作し、スペースを考慮しないと比較的簡単で、毎回新しい文字列を生成するように切り替えられます.また、最初の文字が「/」で始まる場合、パスは直接この場所に切ります.
ここでは、ループ回数を目標文字列の長さ+1に等しくすることで、後ループ後に1回以上繰り返される論理的判断を低減することができ、例えば「/」または「または」に遭遇する場合、「def」という文字が1文字しかなく、パス分割子がない場合.
まとめ
この問題は個人的にはやはり文字に対する操作能力を考察していると思います.例えば、キャッシュ不足、特殊な状況、文字スキャンなど、実現方法はたくさんあります.スキャン過程はもっと複雑であれば、コンパイル原理の中の文法分析を使うことができますが、実現も少し複雑です.
public class WorkSpace3 {
private String path;
public WorkSpace3(String dir) {
this.path = dir;
}
private char[] set(char[] arr, int index, char ch) {
if (index >= arr.length) {
char[] t = new char[arr.length * 2];
for (int i = 0; i < arr.length; i++) {
t[i] = arr[i];
}
t[index] = ch;
return t;
} else {
arr[index] = ch;
return arr;
}
}
private boolean isValidChar(char ch) {
if ((ch >= 'a' && ch <= 'z') || (ch == '.')) {
return true;
} else {
return false;
}
}
private char[] append(char[] arr, int index, String str) {
if (index + str.length() > arr.length) {
char[] t = new char[arr.length * 2];
for (int i = 0; i < arr.length; i++) {
t[i] = arr[i];
}
for (int i = 0; i < str.length(); i++) {
t[index + i] = str.charAt(i);
}
return t;
} else {
for (int i = 0; i < str.length(); i++) {
arr[index + i] = str.charAt(i);
}
return arr;
}
}
public void changeDirectory(String target) {
char[] arr = target.toCharArray();
if (arr.length == 0) {
return;
}
char[] temp = path.toCharArray();
int p = temp.length;
int l = 0;
for (int i = 0; i <= arr.length; i++) {
if (i < arr.length && (arr[i] == '/' || i == arr.length) {
if (i == 0) {
p = 0;
//set(p++, '/');
l = i + 1;
} else {
String str = new String(arr, l , i - l);
l = i + 1;
if (str.equals(".")) {
// current dir do nothing
} else if (str.equals("..")) {
// up parent dir
for (int j = p - 1; j >= 0; j--) {
if (temp[j] == '/') {
p = j;
break;
}
}
} else {
// append
temp = set(temp, p++, '/');
temp = append(temp, p, str);
p += str.length();
}
}
} else if (i < arr.length && isValidChar(arr[i])) {
} else {
return;
}
}
this.path = new String(temp, 0, p);
}
public void show() {
System.out.println(path);
}
}
ここでは、ループ回数を目標文字列の長さ+1に等しくすることで、後ループ後に1回以上繰り返される論理的判断を低減することができ、例えば「/」または「または」に遭遇する場合、「def」という文字が1文字しかなく、パス分割子がない場合.
まとめ
この問題は個人的にはやはり文字に対する操作能力を考察していると思います.例えば、キャッシュ不足、特殊な状況、文字スキャンなど、実現方法はたくさんあります.スキャン過程はもっと複雑であれば、コンパイル原理の中の文法分析を使うことができますが、実現も少し複雑です.