最新华为OD机试真题-目录管理器(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 目录管理器(200分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

⛽️ 目录管理器

题目描述

K小姐最近在开发一个简易的目录管理器,她希望该管理器能够支持以下几个操作:

1. $mkdir$ 目录名:在当前目录下新建一个名为目录名的目录。如果当前目录下已经存在同名目录,则不进行任何操作。
2. $cd$ 目录名:进入名为目录名的子目录。特别地,$cd$ ..表示返回上一级目录。如果指定目录不存在,则不进行任何操作。
3. $pwd$:输出从根目录到当前目录的路径。

需要注意的是:

1. 目录名仅包含小写字母,且每个命令中的目录名都是一个单独的目录,不考虑多级目录的情况。
2. 根目录用/表示,初始时总是位于根目录。
3. 如果输入命令不属于上述三种格式,则视为无效命令,不进行任何操作。

现在,给你一系列K小姐输入的命令,请你输出最后一条$pwd$命令的结果。

输入格式

输入由若干行组成,每行包含一条命令。

输出格式

输出最后一条$pwd$命令的结果。如果没有$pwd$命令,则不输出任何内容。

样例输入

mkdir abc
cd abc
pwd

样例输出

/abc/

数据范围

• 命令数不超过 条。
• 每条命令的长度不超过 个字符。
• 目录名仅包含小写字母,长度不超过 个字符。

题解

本题是一道简单的模拟题。我们可以用一个字符串 来维护当前的目录路径,用一个 来存储已经创建的目录。

对于每一条命令,我们分情况讨论:

• 如果是 $mkdir$ 目录名 命令,我们判断 是否已经存在于 中。如果不存在,就将其加入 。
• 如果是 $cd$ 目录名 命令,我们判断 是否存在于 中。如果存在,就将 更新为 。特别地,如果目录名为 "..",我们就将 更新为上一级目录。
• 如果是 $pwd$ 命令,我们记录当前的 到答案中。
• 其他命令无需处理。

最后,我们输出最后一次记录的 即可。

时间复杂度 ,空间复杂度 。其中 为命令的数量。

参考代码

• Cpp

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    string path = "/";
    unordered_set<string> dirs;
    string ans;

    string op;
    while (cin >> op) {
        if (op == "mkdir") {
            string dir;
            cin >> dir;
            if (!dirs.count(path + dir + "/")) {
                dirs.insert(path + dir + "/");
            }
        } else if (op == "cd") {
            string dir;
            cin >> dir;
            if (dir == "..") {
                if (path != "/") {
                    path.pop_back();
                    while (path.back() != '/') path.pop_back();
                }
            } else if (dirs.count(path + dir + "/")) {
                path += dir + "/";
            }
        } else if (op == "pwd") {
            ans = path;
        }
    }

    if (ans.size()) cout << ans << endl;

    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String path = "/";
        Set<String> dirs = new HashSet<>();
        String ans = "";

        while (true) {
            String line = br.readLine();
            if (line == null) break;
            String[] op = line.split(" ");
            if (op[0].equals("mkdir")) {
                String dir = op[1];
                if (!dirs.contains(path + dir + "/")) {
                    dirs.add(path + dir + "/");
                }
            } else if (op[0].equals("cd")) {
                String dir = op[1];
                if (dir.equals("..")) {
                    if (!path.equals("/")) {
                        path = path.substring(0, path.length() - 1);
                        int idx = path.lastIndexOf("/");
                        path = path.substring(0, idx + 1);
                    }
                } else if (dirs.contains(path + dir + "/")) {
                    path += dir + "/";
                }
            } else if (op[0].equals("pwd")) {
                ans = path;
            }
        }

        if (ans.length() > 0) System.out.println(ans);
    }
}

• Python

path = "/"
dirs = set()
ans = ""

try:
    while True:
        op = input().split()
        if op[0] == "mkdir":
            dir = op[1]
            if path + dir + "/" not in dirs:
                dirs.add(path + dir + "/")
        elif op[0] == "cd":
            dir = op[1]
            if dir == "..":
                if path != "/":
                    path = path[:-1]
                    path = path[:path.rindex("/")+1]
            elif path + dir + "/" in dirs:
                path += dir + "/"
        elif op[0] == "pwd":
            ans = path
except EOFError:
    pass

if ans:
    print(ans)