华为OD机试：模拟目录管理功能

题目描述

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

支持命令：

1.创建目录命令：mkdir 目录名称，如 mkdir abc 为在当前目录创建abc目录，如果已存在同名目录则不执行任何操作。此命令无输出。

2.进入目录命令：cd 目录名称，如 cd abc 为进入abc目录，特别地，cd .. 为返回上级目录，如果目录不存在则不执行任何操作。此命令无输出。

3.查看当前所在路径命令：pwd，输出当前路径字符串。

约束：

1.目录名称仅支持小写字母；mkdir 和 cd 命令的参数仅支持单个目录，如：mkdir abc 和 cd abc；不支持嵌套路径和绝对路径，如 mkdir abc/efg，cd abc/efg，mkdir /abc/efg，cd /abc/efg 是不支持的。

2.目录符号为/，根目录/作为初始目录。

3.任何不符合上述定义的无效命令不做任何处理并且无输出。

输入描述

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

输出描述

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

备注

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

用例

题目解析

1.首先，我们需要定义一个类来表示目录结构，包括目录名称和子目录列表。

2.然后，我们需要实现创建目录、进入目录和查看当前路径的功能。

3.在创建目录时，我们需要检查目录是否已存在，如果不存在则创建一个新的目录。

4.在进入目录时，我们需要检查目录是否存在，如果存在则切换到该目录。

5.在查看当前路径时，我们需要返回当前目录的完整路径。

6.最后，我们需要处理输入的命令序列，依次执行每个命令，并输出最后一条命令的结果。

JavaScript算法源码
const rl = require("readline").createInterface({ input: process.stdin });
const iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

(async function () {
  class TreeNode {
    constructor(curDicName, father) {
      this.curDicName = curDicName;
      this.father = father;
      this.children = {};
    }
  }

  class Tree {
    constructor() {
      this.root = new TreeNode("/", null);
      this.cur = this.root;
    }

    mkdir(dicName) {
      if (!this.cur.children[dicName]) {
        this.cur.children[dicName] = new TreeNode(dicName + "/", this.cur);
      }
    }

    cd(dicName) {
      if (dicName === "..") {
        if (this.cur.father !== null) {
          this.cur = this.cur.father;
        }
      } else {
        if (this.cur.children[dicName]) {
          this.cur = this.cur.children[dicName];
        }
      }
    }

    pwd() {
      const arr = [];
      let cur = this.cur;
      while (cur !== null) {
        arr.push(cur.curDicName);
        cur = cur.father;
      }
      return arr.reverse().join("");
    }
  }

  const tree = new Tree();
  let lastCommandOutPut = "";

  outer: while (true) {
    try {
      const line = await readline();
      const [cmd_key, cmd_val] = line.split(" ");

      if (cmd_key === "pwd") {
        if (cmd_val !== undefined) continue;
        lastCommandOutPut = tree.pwd();
      } else if (cmd_key === "mkdir" || cmd_key === "cd") {
        if (cmd_val === undefined) continue;

        if (cmd_key !== "cd" || cmd_val !== "..") {
          for (let c of cmd_val) {
            if (c < "a" || c > "z") continue outer;
          }
        }

        if (cmd_key === "mkdir") {
          tree.mkdir(cmd_val);
          lastCommandOutPut = "";
        } else {
          tree.cd(cmd_val);
          lastCommandOutPut = "";
        }
      }
    } catch (e) {
      break;
    }
  }

  console.log(lastCommandOutPut);
})();

Java算法源码
import java.util.HashMap;
import java.util.Scanner;

public class Main {
  static class TreeNode {
    String curDicName;
    TreeNode father;
    HashMap<String, TreeNode> children;

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

  static class Tree {
    TreeNode root;
    TreeNode cur;

    public Tree() {
       this.root = new TreeNode("/", null);
         this.cur = root;
    }

    public void mkdir(String childDicName) {
 this.cur.children.putIfAbsent(
          childDicName, new TreeNode(childDicName + "/", this.cur)); // 目录符号为 /
    }

    public void cd(String dicName) {
      if (dicName.equals("..")) {
          if (this.cur.father != null) {
           this.cur = this.cur.father;
        }
      } else {
         if (this.cur.children.containsKey(dicName)) {
           this.cur = this.cur.children.get(dicName);
        }
      }
    }

    public String pwd() {
       StringBuilder sb = new StringBuilder();

       TreeNode cur = this.cur;
      while (cur != null) {
         sb.insert(0, cur.curDicName);
        cur = cur.father;
      }

      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(" ");

      String cmd_key = tmp[0];

      if (cmd_key.equals("pwd")) {
       
        if (tmp.length != 1) continue;
        lastCommandOutPut = tree.pwd();
      } else if (cmd_key.equals("mkdir") || cmd_key.equals("cd")) {
         if (tmp.length != 2) continue;

         String cmd_val = tmp[1];

        if (!(cmd_key.equals("cd") && cmd_val.equals(".."))) {
            for (int i = 0; i < cmd_val.length(); i++) {
            char c = cmd_val.charAt(i);
            if (c < 'a' || c > 'z') continue outer;
          }
        }

        if (cmd_key.equals("mkdir")) {
          tree.mkdir(cmd_val);

           lastCommandOutPut = "";
        } else {
          tree.cd(cmd_val);
           lastCommandOutPut = "";
        }
      }
    }

    System.out.println(lastCommandOutPut);
  }
}

Python算法源码
   
class TreeNode:
    def __init__(self, curDicName, father):
        self.curDicName = curDicName
        self.father = father
        self.children = {}


class Tree:
    def __init__(self):
        self.root = TreeNode("/", None)
        self.cur = self.root

    def mkdir(self, dicName):
        self.cur.children.setdefault(dicName, TreeNode(dicName + "/", self.cur))

    def cd(self, dicName):
        if dicName == "..":
            if self.cur.father is not None:
                self.cur = self.cur.father
        else:
            self.cur = self.cur.children.get(dicName)

    def pwd(self):
        lst = []
        cur = self.cur
        while cur is not None:
            lst.append(cur.curDicName)
            cur = cur.father
        return "".join(reversed(lst))


tree = Tree()
lastCommandOutput = ""

while True:
    try:
        line = input()
        tmp = line.split()
        cmd_key = tmp[0]

        if cmd_key == "pwd":
            if len(tmp) != 1:
                continue
            lastCommandOutput = tree.pwd()
        elif cmd_key in ["mkdir", "cd"]:
            if len(tmp) != 2:
                continue
            cmd_val = tmp[1]
            if not (cmd_val.isalpha() and cmd_val.islower()) and not (cmd_key == 'cd' and cmd_val == '..'):
                continue
            if cmd_key == "mkdir":
                tree.mkdir(cmd_val)
                lastCommandOutput = ""
            else:
                tree.cd(cmd_val)
                lastCommandOutput = ""
    except:
        break

print(lastCommandOutput)

C算法源码
 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TreeNode {
    char curDicName[11];  
    struct TreeNode *father;  
    struct LinkedList *children;  
} TreeNode;

typedef struct ListNode {
    TreeNode *ele; 
    struct ListNode *next;
} ListNode;

typedef struct LinkedList {
    ListNode *head;
    ListNode *tail;
    int size;
} LinkedList;

typedef struct Tree {
    TreeNode *root; 
    TreeNode *cur;  
} Tree;

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));

    link->head = NULL;
    link->tail = NULL;
    link->size = 0;

    return link;
}

void addLast_LinkedList(LinkedList *link, TreeNode *ele) {
    ListNode *listNode = (ListNode *) malloc(sizeof(ListNode));
    listNode->ele = ele;
    listNode->next = NULL;

    if(link->size == 0) {
        link->head = listNode;
        link->tail = listNode;
    } else {
        link->tail->next = listNode;
        link->tail = listNode;
    }

    link->size++;
}

TreeNode *get_LinkedList(LinkedList *link, char *dicName) {
    ListNode *curListNode = link->head;
    while (curListNode != NULL) {
        if (strcmp(curListNode->ele->curDicName, dicName) == 0) {
            return curListNode->ele;
        }
        curListNode = curListNode->next;
    }
    return NULL;
}

TreeNode *new_TreeNode(char *curDicName, TreeNode *father) {
    TreeNode *treeNode = (TreeNode *) calloc(1, sizeof(TreeNode));

    strcpy(treeNode->curDicName, curDicName);
    treeNode->father = father;
    treeNode->children = new_LinkedList();

    return treeNode;
}

Tree *new_Tree() {
    Tree *tree = (Tree *) malloc(sizeof(Tree));

      tree->root = new_TreeNode("", NULL);
     tree->cur = tree->root;

    return tree;
}

void mkdir_Tree(Tree *tree, char *dicName) {
    TreeNode *p = get_LinkedList(tree->cur->children, dicName);

     if (p != NULL) {
        return;
    }

    TreeNode *treeNode = new_TreeNode(dicName, tree->cur);
    addLast_LinkedList(tree->cur->children, treeNode);
}

void cd_Tree(Tree *tree, char *dicName) {
    if (strcmp(dicName, "..") == 0) {
          if (tree->cur->father != NULL) {
              tree->cur = tree->cur->father;
        }
    } else {
        TreeNode *p = get_LinkedList(tree->cur->children, dicName);

          if (p != NULL) {
              tree->cur = p;
        }
    }
}

char *pwd_Tree(Tree *tree) {
    char *tmp = (char *) calloc(10000, sizeof(char));
    char *res = (char *) calloc(10000, sizeof(char));

     TreeNode *cur = tree->cur;
    while (cur != NULL) {
        strcpy(tmp, res);

        strcpy(res, cur->curDicName);
        strcat(res, "/");
        strcat(res, tmp);
        cur = cur->father;
    }

    return res;
}

int main() { 
    Tree *tree = new_Tree();
 
    char lastCommandOutPut[10000];

    char s[50];
    while (gets(s)) { 
         if(strlen(s) == 0) break;

        char *cmd_key = strtok(s, " ");
        char *cmd_val = strtok(NULL, " ");

        if (strcmp(cmd_key, "pwd") == 0) {
             if (cmd_val != NULL) {
                continue;
            }
            strcpy(lastCommandOutPut, pwd_Tree(tree));
        } else if (strcmp(cmd_key, "mkdir") == 0 || strcmp(cmd_key, "cd") == 0) {
              if (cmd_val == NULL) continue;

            char *p = strtok(NULL, " ");
            if (p != NULL) continue;

            if(!(strcmp(cmd_key, "cd") == 0 && strcmp(cmd_val, "..") == 0)) {
                unsigned long long len = strlen(cmd_val);

                   int i = 0;
                for (; i < len; i++) {
                    char c = cmd_val[i];

                    if (c < 'a' || c > 'z') {
                        break;
                    }
                }

                if(i != len) {
                    continue;
                }
            }

            if(strcmp(cmd_key, "mkdir") == 0) {
                mkdir_Tree(tree, cmd_val);
                  memset(lastCommandOutPut, '\0', strlen(lastCommandOutPut));
            } else {
                cd_Tree(tree, cmd_val);
                  memset(lastCommandOutPut, '\0', strlen(lastCommandOutPut));
            }
        }
    }

    puts(lastCommandOutPut);

    return 0;
}