#P3260. 模拟目录管理功能(200分)
-
1000ms
Tried: 74
Accepted: 19
Difficulty: 8
所属公司 :
华为od
模拟目录管理功能(200分)
思路:DFS模拟
使用嵌套哈希表来实现文件系统。
每一个dict就是一个文件夹,他存储了
path , 代表路径,供pwd使用
next , 也是一个dict,存储了当前文件夹下的所有子文件夹。特别的next[".."] 存储了当前文件夹的父文件夹.
然后模拟这个过程即可。具体见代码细节。
JavaScript
class Node {
constructor(path, fa) {
this.path = path;
this.next = new Map();
this.next.set('..', fa);
}
}
function newNode(path, fa) {
return new Node(path, fa);
}
function check1(s) {
return /^[a-z]+$/.test(s); // 检查字符串是否为小写字母
}
function check2(s) {
return s === '..' || /^[a-z]+$/.test(s); // 检查字符串是否为小写字母或者".."
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let tree = newNode('/', null); // 创建根节点
let nowNode = tree; // 当前所在节点
let result = ''; // 存储结果的字符串
rl.on('line', (input) => {
const s = input.split(' '); // 按空格分割指令和参数
if (s[0] === 'mkdir') { // 创建文件夹指令
if (s.length !== 2 || !check1(s[1]) || nowNode.next.has(s[1])) {
result += '\n';
} else {
nowNode.next.set(s[1], newNode(nowNode.path + s[1] + '/', nowNode)); // 创建新文件夹节点
result += '\n';
}
} else if (s[0] === 'cd') { // 切换目录指令
if (s.length !== 2 || !check2(s[1]) || s[1].includes('/') || !nowNode.next.has(s[1]) || nowNode.next.get(s[1]) === null) {
result += '\n';
} else {
nowNode = nowNode.next.get(s[1]); // 切换到目标文件夹
result += '\n';
}
} else {
if (s.length !== 1) {
result += '\n';
} else {
result += nowNode.path + '\n'; // 输出当前所在文件夹路径
}
}
});
rl.on('close', () => {
const resArray = result.split('\n').filter(Boolean);
console.log(resArray[resArray.length - 1]); // 输出最终结果
});
C++
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <memory>
#include <stack>
using namespace std;
string ans;
struct FileTable{
string m_name;
shared_ptr<FileTable> m_pre;
vector<shared_ptr<FileTable>> m_self;
FileTable(string name, shared_ptr<FileTable> pre=nullptr):m_name(name), m_pre(pre){};
};
class FileSystem{
public:
shared_ptr<FileTable> root, now;
FileSystem(){
root = make_shared<FileTable>("/");
now = root;
}
void mkdir(string name){
auto Name = name + "/";
for(auto&a : now->m_self){
if(a->m_name == Name){
return;
}
}
auto dir = make_shared<FileTable>(name+"/", now);
now->m_self.push_back(dir);
}
void cd(string name){
if(name == ".."){
if(now->m_pre)now = now->m_pre;
return;
}
auto Name = name + "/";
for(auto&a : now->m_self){
if(a->m_name == Name){
now = a;
}
}
}
void pwd(){
ans = "";
stack<string> stk;
auto noww = now;
while(noww->m_pre){
stk.push(noww->m_name);
noww = noww->m_pre;
}
stk.push("/");
while(stk.size()){
//cout << stk.top();
ans += stk.top();
stk.pop();
}
//cout << endl;
ans += '\n';
}
};
int main(){
string str;
FileSystem fs;
while(getline(cin,str)){
stringstream ss(str);
ss >> str;
if(str == "pwd"){
fs.pwd();
}
else if(str == "mkdir"){
ss >> str;
fs.mkdir(str);
}
else if(str == "cd"){
ss >> str;
fs.cd(str);
}
}
cout << ans;
return 0;
}
Java
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
static class Node {
String path;
Map<String, Node> next;
Node(String path, Node fa) {
this.path = path;
this.next = new HashMap<>();
this.next.put("..", fa);
}
}
static Node newNode(String path, Node fa) {
return new Node(path, fa);
}
static boolean check1(String s) {
return s.matches("[a-z]+"); // 检查字符串是否为小写字母
}
static boolean check2(String s) {
return s.equals("..") || s.matches("[a-z]+"); // 检查字符串是否为小写字母或者".."
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Node tree = newNode("/", null); // 创建根节点
Node nowNode = tree; // 当前所在节点
StringBuilder result = new StringBuilder(); // 存储结果的字符串
while (true) {
try {
String input = scanner.nextLine(); // 输入操作指令
String[] s = input.split(" "); // 按空格分割指令和参数
if (s[0].equals("mkdir")) { // 创建文件夹指令
if (s.length != 2 || !check1(s[1]) || nowNode.next.containsKey(s[1])) {
result.append("\n");
} else {
nowNode.next.put(s[1], newNode(nowNode.path + s[1] + "/", nowNode)); // 创建新文件夹节点
result.append("\n");
}
} else if (s[0].equals("cd")) { // 切换目录指令
if (s.length != 2 || !check2(s[1]) || s[1].contains("/") || !nowNode.next.containsKey(s[1]) || nowNode.next.get(s[1]) == null) {
result.append("\n");
} else {
nowNode = nowNode.next.get(s[1]); // 切换到目标文件夹
result.append("\n");
}
} else {
if (s.length != 1) {
result.append("\n");
} else {
result.append(nowNode.path).append("\n"); // 输出当前所在文件夹路径
}
}
} catch (Exception e) {
break;
}
}
String[] resArray = result.toString().split("\n");
for (int i = resArray.length - 1; i >= 0; i--) {
if (!resArray[i].isEmpty()) {
System.out.println(resArray[i]); // 输出最终结果
break;
}
}
}
}
Python
def newNode(path, fa): # 创建一个新节点
node = {}
node['path'] = path # 文件夹路径
node['next'] = {"..": fa} # 子文件夹列表,包括父文件夹
return node
def check1(s):
return s.islower() # 检查字符串是否为小写字母
def check2(s):
return s == ".." or s.islower() # 检查字符串是否为小写字母或者".."
tree = newNode("/", None) # 创建根节点
now_node = tree # 当前所在节点
res = [] # 存储结果的列表
while True:
try:
s = input() # 输入操作指令
except:
break
s = s.split(" ") # 按空格分割指令和参数
if s[0] == 'mkdir': # 创建文件夹指令
if len(s) != 2:
res.append("")
continue
to = s[1] # 目标文件夹名称
if not check1(to): # 检查文件夹名称是否符合要求
res.append("")
continue
if to in now_node['next']: # 检查文件夹名称是否已存在
res.append("")
continue
now_node['next'][to] = newNode(now_node["path"] + to + "/", now_node) # 创建新文件夹节点
res.append("")
elif s[0] == 'cd': # 切换目录指令
if len(s) != 2:
res.append("")
continue
to = s[1] # 目标文件夹名称
if not check2(to): # 检查文件夹名称是否符合要求
res.append("")
continue
if "/" in to: # 检查文件夹名称是否包含"/"
res.append("")
continue
if to not in now_node['next'] or now_node['next'][to] is None: # 检查目标文件夹是否存在
res.append("")
continue
now_node = now_node['next'][to] # 切换到目标文件夹
res.append("")
else:
if len(s) != 1:
res.append("")
continue
res.append(now_node['path']) # 输出当前所在文件夹路径
while res and res[-1] == "": #gggg
res.pop()
print(res[-1]) # 输出最终结果
题目描述
实现一个模拟目录管理功能的软件,输入一个命令序列,输出最后一条命令运行的结果。
支持命令:
1)创建目录命令:mkdir 目录名称,如 mkdir abc为在当前目录创建 abc 目录,如果已存在同名目录则不执行任何操作。此命令无输出。
2)进入目录命令:cd 目录名称,如 cd abc 进入 abc 目录,特别地, cd .. 为返回上级目录,如果目录不存在则不执行任何操作。此命令无输出。
3)查看当前所在路径的命令:pwd ,输出当前路径字符串。
约束:
1)目录名称仅支持小写字母;mkdir 和 cd 命令的参数仅支持单个目录,如:mkdirabc 和 cdabc;不支持嵌套路径和绝对路径,如:mkdir abc/efg,cd abc/efg , mkdir /abc/efg , cd /abc/efg 是不支持的。
2)目录符号为 / ,根目录/作为初始目录
3)任何不符合上述定义的无效命令不做任何处理并且无输出。
输入描述
输入 N 行字符串,每一行都是一条命令
输出描述
输出最后一条命令运行结果字符串
样例
输入
mkdir abc
cd abc
pwd
输出
/abc/
说明:在根目录创建一个 abc 的目录并进入 abc 目录中查看当前目录所在路径,输出当前路径 /abc/