题解 | #命令行软件#

题目链接

命令行软件

题目描述

模拟一个简化的深空分布式文件系统的命令行功能。该文件系统是一个树状结构，初始时存在一个 /usr 目录，且当前工作目录就在 usr。需要处理一系列命令并对 ls 命令作出响应。

支持的指令：
- mkdir <dirname>: 在当前目录下创建新目录。如果已存在则忽略。
- cd ..: 切换到父目录。
- cd <dirname>: 切换到当前目录下的指定子目录。
- ls: 按字典序升序，列出当前目录下的所有子目录。
输出要求：
- 对于每个 ls 指令，输出结果占一行。
- 目录名之间用单个空格分隔。
- 如果当前目录为空，ls 指令输出一个单独的空格。

解题思路

本题的核心是模拟一个树形文件系统的操作。我们可以通过构建一个显式的树结构来解决问题，其中每个节点代表一个目录。

数据结构设计
- 我们定义一个 Node 类（或结构体）来表示一个目录。
- 每个 Node 包含三个关键部分：
  - name (string): 目录的名称。
  - parent (Node*): 一个指向父目录节点的指针。根目录的父节点可以设为 nullptr 或自身。
  - children (map<string, Node*>): 一个存储所有子目录的映射。选择 map (或 Java 中的 TreeMap) 是此题的关键，因为它能同时满足两个需求：
    1. 快速查找：通过目录名（键）快速定位子目录，时间复杂度为对数级别，适用于 cd <dirname> 和 mkdir 的存在性检查。
    2. 自动排序：map 会自动根据键（目录名）按字典序排序，这使得 ls 命令的实现变得非常简单，只需按顺序遍历 map 即可。
系统初始化
- 首先，创建一个根节点 root，代表根目录 /。将其 parent 指向自身或 nullptr。
- 在 root 下创建一个名为 usr 的子节点。
- 维护一个全局的 currentNode 指针，用于表示“当前工作目录”，并将其初始化为 usr 节点。
命令模拟
- 循环读取每条命令，并根据命令类型进行分派。
- mkdir <dirname>:
  - 检查 currentNode->children 中是否已存在键为 <dirname> 的项。
  - 如果不存在，则创建一个新的 Node，设置其 parent 为 currentNode，然后将其插入到 currentNode->children 中。
- cd ..:
  - 检查 currentNode->parent 是否为空或指向自身。
  - 如果不为空，则将 currentNode 更新为其父节点 currentNode = currentNode->parent。
- cd <dirname>:
  - 在 currentNode->children 中查找键为 <dirname> 的项。
  - 如果找到了，则将 currentNode 更新为该子节点 currentNode = currentNode->children[<dirname>]。
- ls:
  - 检查 currentNode->children 是否为空。
  - 如果为空，输出一个空格。
  - 如果不为空，则遍历 map 的所有键，将它们用空格连接并输出。

通过这种方式，我们可以清晰且高效地模拟文件系统的所有操作。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <sstream>

using namespace std;

struct Node {
    string name;
    Node* parent;
    map<string, Node*> children;

    Node(string n, Node* p) : name(n), parent(p) {}
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    Node* root = new Node("/", nullptr);
    root->parent = root; // 根节点的父节点指向自己
    Node* usr = new Node("usr", root);
    root->children["usr"] = usr;

    Node* currentNode = usr;

    string command;
    for (int i = 0; i < n; ++i) {
        cin >> command;
        if (command == "mkdir") {
            string dirname;
            cin >> dirname;
            if (currentNode->children.find(dirname) == currentNode->children.end()) {
                currentNode->children[dirname] = new Node(dirname, currentNode);
            }
        } else if (command == "cd") {
            string target;
            cin >> target;
            if (target == "..") {
                currentNode = currentNode->parent;
            } else {
                if (currentNode->children.count(target)) {
                    currentNode = currentNode->children[target];
                }
            }
        } else if (command == "ls") {
            if (currentNode->children.empty()) {
                cout << " " << "\n";
            } else {
                bool first = true;
                for (auto const& [key, val] : currentNode->children) {
                    if (!first) {
                        cout << " ";
                    }
                    cout << key;
                    first = false;
                }
                cout << "\n";
            }
        }
    }
    
    // Note: In a real application, memory for Nodes should be deallocated.
    // For competitive programming, this is often omitted for speed.

    return 0;
}

import java.util.Scanner;
import java.util.Map;
import java.util.TreeMap;
import java.util.StringJoiner;

public class Main {
    static class Node {
        String name;
        Node parent;
        Map<String, Node> children = new TreeMap<>();

        Node(String name, Node parent) {
            this.name = name;
            this.parent = parent;
        }
    }

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

        Node root = new Node("/", null);
        root.parent = root; // 根节点的父节点指向自己
        Node usr = new Node("usr", root);
        root.children.put("usr", usr);

        Node currentNode = usr;

        for (int i = 0; i < n; i++) {
            String command = sc.next();
            if (command.equals("mkdir")) {
                String dirname = sc.next();
                if (!currentNode.children.containsKey(dirname)) {
                    currentNode.children.put(dirname, new Node(dirname, currentNode));
                }
            } else if (command.equals("cd")) {
                String target = sc.next();
                if (target.equals("..")) {
                    currentNode = currentNode.parent;
                } else {
                    if (currentNode.children.containsKey(target)) {
                        currentNode = currentNode.children.get(target);
                    }
                }
            } else if (command.equals("ls")) {
                if (currentNode.children.isEmpty()) {
                    System.out.println(" ");
                } else {
                    StringJoiner sj = new StringJoiner(" ");
                    for (String key : currentNode.children.keySet()) {
                        sj.add(key);
                    }
                    System.out.println(sj.toString());
                }
            }
        }
    }
}

import sys

class Node:
    def __init__(self, name, parent=None):
        self.name = name
        self.parent = parent
        self.children = {}

def main():
    n = int(input())

    root = Node("/")
    root.parent = root  # 根节点的父节点指向自己
    usr = Node("usr", root)
    root.children["usr"] = usr

    current_node = usr

    for _ in range(n):
        line = input().split()
        command = line[0]

        if command == "mkdir":
            dirname = line[1]
            if dirname not in current_node.children:
                current_node.children[dirname] = Node(dirname, current_node)
        elif command == "cd":
            target = line[1]
            if target == "..":
                current_node = current_node.parent
            else:
                if target in current_node.children:
                    current_node = current_node.children[target]
        elif command == "ls":
            if not current_node.children:
                print(" ")
            else:
                # Python的dict需要手动排序key
                sorted_dirs = sorted(current_node.children.keys())
                print(" ".join(sorted_dirs))

if __name__ == "__main__":
    main()

算法及复杂度

算法: 树、模拟
时间复杂度: $O(N \cdot K \cdot \log K)$ 。
- $N$ 是总指令数。对于每条指令：
- mkdir 和 cd <dirname> 的操作主要是对 map 进行查找和插入，时间复杂度为 $O(\log K)$ ，其中 $K$ 是当前目录下子目录的最大数量。
- cd .. 的时间复杂度为 $O(1)$ 。
- ls 的操作需要遍历当前目录下的所有子目录并排序（Python）。对于 C++ map 和 Java TreeMap 遍历是 $O(K)$ ，Python 排序是 $O(K \log K)$ 。输出字符串的长度也会影响，但主要瓶颈是排序和查找。因此，总的来说，单次操作最坏情况是 $O(K \log K)$ 。
空间复杂度: $O(M \cdot L)$ 。
- $M$ 是创建的目录总数， $L$ 是目录名的平均长度。空间主要用于存储树的节点，每个节点包含名称、父指针和子目录映射。