#P4279. 第1题-命令行软件
-
1000ms
Tried: 55
Accepted: 17
Difficulty: 4
所属公司 :
华为
时间 :2025年10月23日-留学生非AI方向(通软&嵌软&测试&算法&数据科学)
-
算法标签>树结构哈希
第1题-命令行软件
解题思路
-
用一棵仅包含“目录”的树来模拟文件系统。每个结点表示一个目录,保存:
children:子目录名到子结点的映射parent:父结点指针(便于cd ..)
-
初始时创建根目录
/,并在其下创建默认目录/usr,当前目录指向/usr。 -
对每条指令:
mkdir name:若当前目录无同名子目录则创建。cd ..:当前目录移动到其父目录。cd name:移动到名为name的子目录(题目保证存在)。ls:取出当前目录全部子目录名,按字典序升序排序并输出;若为空,输出单独一个空格。
-
算法要点:树+哈希映射(或字典)维护结构;
ls时对子目录名排序。
复杂度分析
- 设总指令数为
m,单个目录的子数为k。 - 时间复杂度:除
ls外均为O(1)平均;ls为O(k log k)(对子目录名排序)。 - 空间复杂度:
O(N),其中N为总目录数(由所有mkdir决定)。
代码实现
Python
# 中文注释版本
import sys
# 目录结点
class Node:
def __init__(self, parent=None):
self.parent = parent # 父目录指针
self.children = {} # 子目录名 -> Node
# 文件系统功能:与主函数分离
class FileSystem:
def __init__(self):
self.root = Node(None) # 根目录 /
# 根下默认创建 /usr
self.root.children["usr"] = Node(self.root)
self.cur = self.root.children["usr"] # 初始目录为 /usr
def mkdir(self, name: str):
# 若不存在同名子目录则创建
if name not in self.cur.children:
self.cur.children[name] = Node(self.cur)
def cd(self, name: str):
if name == "..":
self.cur = self.cur.parent
else:
self.cur = self.cur.children[name]
def ls(self) -> str:
names = sorted(self.cur.children.keys())
if not names:
return " " # 无子目录则输出单独一个空格
return " ".join(names)
def main():
data = sys.stdin.read().strip().splitlines()
if not data:
return
m = int(data[0].strip())
fs = FileSystem()
out = []
idx = 1
for _ in range(m):
line = data[idx].strip()
idx += 1
if line == "ls":
out.append(fs.ls())
elif line.startswith("cd "):
name = line[3:].strip()
fs.cd(name)
elif line.startswith("mkdir "):
name = line[6:].strip()
fs.mkdir(name)
# 题目保证不会出现其他命令
sys.stdout.write("\n".join(out))
if __name__ == "__main__":
main()
Java
// 中文注释版本(ACM 风格,类名 Main)
import java.util.*;
public class Main {
// 目录结点
static class Node {
Node parent; // 父目录
HashMap<String, Node> children = new HashMap<>(); // 子目录映射
Node(Node p) { this.parent = p; }
}
// 文件系统功能:与主函数分离
static class FileSystem {
Node root;
Node cur;
FileSystem() {
root = new Node(null); // 根目录 /
Node usr = new Node(root);
root.children.put("usr", usr); // 默认 /usr
cur = usr; // 初始目录 /usr
}
void mkdir(String name) {
if (!cur.children.containsKey(name)) {
cur.children.put(name, new Node(cur));
}
}
void cd(String name) {
if ("..".equals(name)) cur = cur.parent;
else cur = cur.children.get(name); // 题目保证存在
}
String ls() {
ArrayList<String> names = new ArrayList<>(cur.children.keySet());
Collections.sort(names);
if (names.isEmpty()) return " "; // 无子目录输出一个空格
StringBuilder sb = new StringBuilder();
for (int i = 0; i < names.size(); i++) {
if (i > 0) sb.append(' ');
sb.append(names.get(i));
}
return sb.toString();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); // m<=200,Scanner足够
if (!sc.hasNextInt()) return;
int m = sc.nextInt();
sc.nextLine(); // 读掉行尾
FileSystem fs = new FileSystem();
StringBuilder out = new StringBuilder();
for (int i = 0; i < m; i++) {
String line = sc.nextLine().trim();
if (line.equals("ls")) {
out.append(fs.ls()).append('\n');
} else if (line.startsWith("cd ")) {
String name = line.substring(3).trim();
fs.cd(name);
} else if (line.startsWith("mkdir ")) {
String name = line.substring(6).trim();
fs.mkdir(name);
}
}
System.out.print(out.toString());
}
}
C++
// 中文注释版本(ACM 风格)
#include <bits/stdc++.h>
using namespace std;
// 目录结点
struct Node {
Node* parent; // 父目录
unordered_map<string, Node*> children; // 子目录映射
Node(Node* p = nullptr) : parent(p) {}
};
// 文件系统功能:与主函数分离
struct FileSystem {
Node* root;
Node* cur;
FileSystem() {
root = new Node(nullptr); // 根目录 /
Node* usr = new Node(root);
root->children["usr"] = usr; // 默认 /usr
cur = usr; // 初始目录 /usr
}
void mkdir(const string& name) {
if (!cur->children.count(name)) {
cur->children[name] = new Node(cur);
}
}
void cd(const string& name) {
if (name == "..") cur = cur->parent;
else cur = cur->children[name]; // 题目保证存在
}
string ls() {
vector<string> names;
names.reserve(cur->children.size());
for (auto &kv : cur->children) names.push_back(kv.first);
sort(names.begin(), names.end());
if (names.empty()) return " "; // 无子目录输出一个空格
string res;
for (size_t i = 0; i < names.size(); ++i) {
if (i) res.push_back(' ');
res += names[i];
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m;
if (!(cin >> m)) return 0;
string dummy;
getline(cin, dummy); // 读掉行尾
FileSystem fs;
string line;
vector<string> output;
for (int i = 0; i < m; ++i) {
getline(cin, line);
// 去除首尾空白
auto l = line.find_first_not_of(" \t\r\n");
auto r = line.find_last_not_of(" \t\r\n");
if (l == string::npos) { --i; continue; }
line = line.substr(l, r - l + 1);
if (line == "ls") {
output.push_back(fs.ls());
} else if (line.rfind("cd ", 0) == 0) { // 以 "cd " 开头
string name = line.substr(3);
// 去除可能空白
size_t l2 = name.find_first_not_of(" \t");
size_t r2 = name.find_last_not_of(" \t");
name = (l2 == string::npos) ? "" : name.substr(l2, r2 - l2 + 1);
fs.cd(name);
} else if (line.rfind("mkdir ", 0) == 0) { // 以 "mkdir " 开头
string name = line.substr(6);
size_t l2 = name.find_first_not_of(" \t");
size_t r2 = name.find_last_not_of(" \t");
name = (l2 == string::npos) ? "" : name.substr(l2, r2 - l2 + 1);
fs.mkdir(name);
}
}
for (size_t i = 0; i < output.size(); ++i) {
cout << output[i] << "\n";
}
return 0;
}
题目内容
提供一个命令行软件,支持用户管理本地的文件系统。文件系统根目录为/,默认创建有/usr目录。命令行初始目录为/usr 。
命令行支持如下命令:
-
mkdir:键入目录名,在当前目录下创建一个目录;当该目录下已经存在同名文件夹时,mkdir 不会创建; -
cd ..: 回退到上一级目录; -
cd name进入当前目录下名为name的目录; -
ls:打印当前目录下所有子目录列表,字典序升序排列。
小华打开了该系统命令行程序,键入了m条指令,需要打印所有ls指令的执行结果。
注意:用例保证所有命令合法,即不会在/目录下cd ..,也不会cd一个不存在的目录。
输入描述
第一行输入一个整数 m(m<=200),表示总共需要执行的命令条目数。
接下来 m 行表示 m 条命令,命令中所有路径不加双引号。
输入的命令不会包含题目描述之外的命令。目录名长度不超过 20 个字符。
输出描述
输出所有ls指令的执行结果,每条ls结果打印一行,目录名用空格隔开。
若当前目录下没有子目录,则打印空格作为单独一行。
样例1
**输入
6
cd ..
ls
cd usr
mkdir usr1
mkdir usr2
ls
输出
usr
usr1 usr2