5

我最近接受了一家知名公司的软件开发人员职位面试，这是被问到的问题之一：

“鉴于以下方法：

List subDirectories(String directoryName){ ... }; 
List filesInDirectory(String directoryName) { ... };

顾名思义，第一种方法返回输入目录（'directoryName'）中直接子目录的名称列表，第二种方法返回此文件夹中所有文件的名称列表。

打印文件系统中的所有文件。”

我想了想，给了面试一个非常明显的递归解决方案。然后她告诉我不要递归地做。由于递归使用调用堆栈，我告诉她我将使用辅助堆栈，此时她告诉我也不要使用堆栈。不幸的是，我无法提出解决方案。我确实问过如何在没有递归/堆栈的情况下完成它，但她不会说。

如何才能做到这一点？

4

3 回答 3

3

您想使用队列和 BFS 算法。

我想一些伪代码会很好：

files = filesInDirectory("/")
foreach (file in files) {
   fileQ.append(file)
}

dirQ = subDirectories("/")
while (dirQ != empty) {
   dir = dirQ.pop
   files = filesInDirectory(dir)
   foreach (file in files) {
      fileQ.append(file)
   }
   dirQ.append(subDirectories(dir))
}

 while (fileQ != empty) {
   print fileQ.pop
 }
于 2012-10-30T04:57:25.757 回答
1

如果我理解正确，直接子目录只是该文件夹中的目录。我的意思是如果 I=我们有这三个路径 和/home/user，我们可以说两者和都是 的直接子目录，但不是。这同样适用于 if和are 文件（是立即的，而不是）。/home/config/home/user/u001userconfig/home/u001useru001useru001

因此，您实际上并不需要递归或堆栈来返回直接子目录或文件的列表。

编辑：我认为 OP 想要实现subDirectories()andfilesInDirectories()功能。

因此，您可以执行打印所有文件（一种伪代码）之类的操作：

List subd = subDirectories(current_dir);
List files = filesInDirectories(current_dir);

foreach (file in files) {
    print file.name();
}

while (!subd.empty()) {
    dir = subd.pop();

    files = filesInDirectory(dir.name());

    foreach (file in files) {
        print file.name();
    }

    subd.append(subDirectories(dir.path()));
}
于 2012-10-30T04:43:03.400 回答
1

我认为@lqs 建议的确实是她可能一直在寻找的一个可以接受的答案：将完整路径存储在一个变量中，如果您输入子目录，则将目录名称附加到它，并在您删除最后一个目录名称时别管它。这样，您的完整路径将充当指向您当前在文件系统中的位置的指针。

因为完整路径总是在最后被修改，所以完整路径的行为（并不奇怪）就像你的堆栈一样。

除了面试问题，我想我仍然会选择一个真正的堆栈而不是字符串操作......

于 2012-10-30T11:28:53.783 回答