2024华为OD笔试机试 - 模拟目录管理功能 (python/c++/java D卷C卷真题算法)

华为OD机试（C卷+D卷）2024真题目录(Java & c++ & python)

题目描述

实现一个模拟目录管理功能的软件，输入一个命令序列，输出最后一条命令运行结果。

支持命令：

• 创建目录命令：mkdir 目录名称，如 mkdir abc 为在当前目录创建abc目录，如果已存在同名目录则不执行任何操作。此命令无输出。
• 进入目录命令：cd 目录名称，如 cd abc 为进入abc目录，特别地，cd … 为返回上级目录，如果目录不存在则不执行任何操作。此命令无输出。
• 查看当前所在路径命令：pwd，输出当前路径字符串。

约束：

• 目录名称仅支持小写字母；mkdir 和 cd 命令的参数仅支持单个目录，如：mkdir abc 和 cd abc；不支持嵌套路径和绝对路径，如 mkdir abc/efg，cd abc/efg，mkdir /abc/efg，cd /abc/efg 是不支持的。
• 目录符号为/，根目录/作为初始目录。
• 任何不符合上述定义的无效命令不做任何处理并且无输出。

输入描述

输入 N 行字符串，每一行字符串是一条命令。

输出描述

输出最后一条命令运行结果字符串。

备注

命令行数限制100行以内，目录名称限制10个字符以内。

用例

输入

mkdir abc
cd abc
pwd

输出

/abc/

说明 在根目录创建一个abc的目录并进入abc目录中查看当前目录路径，输出当前路径/abc/。

解题思路

目录结构，实际就是一颗多叉树。

树节点定义如下：

class TreeNode {

    String dicName; // 当前目录的名字

    TreeNode father; // 当前目录的父目录

    List<TreeNode> children; // 当前目录的子目录

}

树结构：

class Tree {

    TreeNode root; // 树的根目录

    TreeNode cur; // 当前所在目录

}

• mkdir，其实就是在 tree.cur 目录下创建一个子目录，但是前提是 tree.cur 下面不存在对应子目录名，否则不操作。mkdir操作不改变 tree.cur 指向。

cd，有两种情况：

• cd … 是返回上级目录（父目录），但是前提是 tree.cur.father 存在，否则不操作。如果 tree.cur.father 存在，则cd … 会改变 tree.cur = tree.cur.father。

• cd 目录名 是进入子目录，但是前提是 tree.cur 包含对应目录名的子目录，否则不操作。如果 存在对应子目录，则 cd操作会改变 tree.cur = 对应子目录

• pwd 是输出当前目录的路径字符串，我们可以不停进行 tree.cur = tree.cur.father 的倒序遍历，获取遍历过程中目录名tree.cur.dicName，直到 tree.cur == NULL。最后拼接时注意反转。

C++、Java、Python代码如下：

C++参考代码

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
public:
    string directoryName;
    TreeNode* parent;
    unordered_map<string, TreeNode*> children;

    TreeNode(string dirName, TreeNode* parent) 
        : directoryName(move(dirName)), parent(parent) {}
};

class FileSystem {
public:
    TreeNode* root;
    TreeNode* current;

    FileSystem() {
        root = new TreeNode("/", nullptr);
        current = root;
    }

    void mkdir(const string& dirName) {
        if (current->children.count(dirName) == 0) {
            current->children[dirName] = new TreeNode(dirName + "/", current);
        }
    }

    void cd(const string& dirName) {
        if (dirName == "..") {
            if (current->parent != nullptr) {
                current = current->parent;
            }
        } else {
            if (current->children.count(dirName) > 0) {
                current = current->children[dirName];
            }
        }
    }

    string pwd() const {
        string path;
        TreeNode* node = current;
        while (node != nullptr) {
            path = node->directoryName + path;
            node = node->parent;
        }
        return path;
    }
};

int main() {
    FileSystem fs;
    string lastOutput = "/";

    do {
        string s;
        getline(cin, s);

        stringstream ss(s);
        string command;
        vector<string> args;

        while (ss >> command) {
            args.push_back(command);
        }

        if (args.empty()) continue;

        const string& cmd = args[0];

        if (cmd == "pwd" && args.size() == 1) {
            lastOutput = fs.pwd();
        } else if ((cmd == "mkdir" || cmd == "cd") && args.size() == 2) {
            const string& dirName = args[1];
            bool isValid = all_of(dirName.begin(), dirName.end(), [](char c) {
                return islower(c);
            });

            if (isValid) {
                if (cmd == "mkdir") {
                    fs.mkdir(dirName);
                } else if (cmd == "cd") {
                    fs.cd(dirName);
                }
            }

            lastOutput = "/";
        }
    } while (!cin.eof());

    cout << lastOutput << endl;

    return 0;
}

Java参考代码

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    static class TreeNode {
        String directoryName;
        TreeNode parent;
        HashMap<String, TreeNode> children;

        public TreeNode(String directoryName, TreeNode parent) {
            this.directoryName = directoryName;
            this.parent = parent;
            this.children = new HashMap<>();
        }
    }

    static class Tree {
        TreeNode root;
        TreeNode current;

        public Tree() {
            // root是根目录，根目录 / 作为初始目录
            this.root = new TreeNode("/", null);
            // current用于指向当前正在操作的目录
            this.current = root;
        }

        public void mkdir(String directoryName) {
            // mkdir 目录名称，如 mkdir abc 为在当前目录创建abc目录，如果已存在同名目录则不执行任何操作
            this.current.children.putIfAbsent(
                directoryName, new TreeNode(directoryName + "/", this.current)); // 目录符号为 /
        }

        public void cd(String directoryName) {
            if (directoryName.equals("..")) {
                // cd .. 为返回上级目录，如果目录不存在则不执行任何操作
                if (this.current.parent != null) {
                    // current 变更指向上级目录
                    this.current = this.current.parent;
                }
            } else {
                // cd 目录名称，如 cd abc 为进入abc目录，如果目录不存在则不执行任何操作
                if (this.current.children.containsKey(directoryName)) {
                    // current 变更指向下级目录
                    this.current = this.current.children.get(directoryName);
                }
            }
        }

        public String pwd() {
            // 输出当前路径字符串
            StringBuilder sb = new StringBuilder();

            // 倒序路径，即不停向上找父目录
            TreeNode current = this.current;
            while (current != null) {
                // 头插目录名，保证路径中目录层级正确
                sb.insert(0, current.directoryName);
                current = current.parent;
            }

            return sb.toString();
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 初始化目录结构
        Tree tree = new Tree();

        // 记录最后一条命令的输出
        String lastCommandOutput = "/";

        outer:
        while (sc.hasNextLine()) {
            String line = sc.nextLine();

            String[] tmp = line.split(" ");

            if (tmp.length == 0) continue;

            String cmdKey = tmp[0];

            if (cmdKey.equals("pwd")) {
                // pwd 命令不需要参数
                if (tmp.length != 1) continue;
                lastCommandOutput = tree.pwd();
            } else if ((cmdKey.equals("mkdir") || cmdKey.equals("cd")) && tmp.length == 2) {
                String directoryName = tmp[1];

                if (!(cmdKey.equals("cd") && directoryName.equals(".."))) {
                    // 目录名约束校验
                    // 目录名称仅支持小写字母
                    for (char c : directoryName.toCharArray()) {
                        if (!Character.isLowerCase(c)) {
                            continue outer;
                        }
                    }
                }

                if (cmdKey.equals("mkdir")) {
                    tree.mkdir(directoryName);
                } else {
                    tree.cd(directoryName);
                }

                lastCommandOutput = "/";
            }
        }

        System.out.println(lastCommandOutput);
    }
}

Python参考代码

class TreeNode:
    def __init__(self, directory_name, parent):
        self.directory_name = directory_name
        self.parent = parent
        self.children = {}

class Tree:
    def __init__(self):
        # root 是根目录，根目录 / 作为初始目录
        self.root = TreeNode("/", None)
        # current 用于指向当前正在操作的目录
        self.current = self.root

    def mkdir(self, directory_name):
        # mkdir 目录名称，如 mkdir abc 为在当前目录创建 abc 目录，如果已存在同名目录则不执行任何操作
        self.current.children.setdefault(directory_name, TreeNode(directory_name + "/", self.current))

    def cd(self, directory_name):
        if directory_name == "..":
            # cd .. 为返回上级目录，如果目录不存在则不执行任何操作
            if self.current.parent is not None:
                # current 变更指向上级目录
                self.current = self.current.parent
        else:
            # cd 目录名称，如 cd abc 为进入 abc 目录，如果目录不存在则不执行任何操作
            if directory_name in self.current.children:
                # current 变更指向下级目录
                self.current = self.current.children[directory_name]

    def pwd(self):
        # 输出当前路径字符串
        path = []
        # 倒序路径，即不停向上找父目录
        node = self.current
        while node:
            path.append(node.directory_name)
            node = node.parent
        # 反转后拼接
        return ''.join(reversed(path))

# 算法逻辑
# 初始化目录结构
tree = Tree()

# 记录最后一条命令的输出
last_command_output = "/"

while True:
    try:
        line = input().strip()
        if not line:
            continue

        tmp = line.split()
        cmd_key = tmp[0]

        if cmd_key == "pwd":
            # pwd 命令不需要参数
            if len(tmp) == 1:
                last_command_output = tree.pwd()
        elif cmd_key in {"mkdir", "cd"} and len(tmp) == 2:
            cmd_val = tmp[1]

            if cmd_val.isalpha() and cmd_val.islower() or (cmd_key == "cd" and cmd_val == ".."):
                if cmd_key == "mkdir":
                    tree.mkdir(cmd_val)
                else:
                    tree.cd(cmd_val)

                # 题目要求输出最后一个命令的运行结果，对于无输出的命令，覆盖前面的命令的输出结果
                last_command_output = "/"
    except EOFError:
        break

print(last_command_output)