1.题目基本信息

1.1.题目描述

假设有一个同时存储文件和目录的文件系统。

这里将 dir 作为根目录中的唯一目录。dir 包含两个子目录 subdir1 和 subdir2 。subdir1 包含文件 file1.ext 和子目录 subsubdir1；subdir2 包含子目录 subsubdir2，该子目录下包含文件 file2.ext 。

在文本格式中，如下所示(⟶表示制表符)：

dir

-> subdir1

-> -> file1.ext

-> -> subsubdir1

-> subdir2

-> -> subsubdir2

-> -> -> file2.ext

如果是代码表示，上面的文件系统可以写为 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 。'\n' 和 '\t' 分别是换行符和制表符。

文件系统中的每个文件和文件夹都有一个唯一的 绝对路径 ，即必须打开才能到达文件/目录所在位置的目录顺序，所有路径用 '/' 连接。上面例子中，指向 file2.ext 的 绝对路径 是 "dir/subdir2/subsubdir2/file2.ext" 。每个目录名由字母、数字和/或空格组成，每个文件名遵循 name.extension 的格式，其中 name 和 extension由字母、数字和/或空格组成。

给定一个以上述格式表示文件系统的字符串 input ，返回文件系统中 指向 文件 的 最长绝对路径 的长度 。 如果系统中没有文件，返回 0。

1.2.题目地址

https://leetcode.cn/problems/longest-absolute-file-path/description/

2.解题方法

2.1.解题思路

栈+遍历

2.2.解题步骤

第一步，构建维护变量。stack的栈顶维护当前遍历字符所在路径的父路径的长度

第二步，遍历字符串，更新维护变量

• 2.1.统计\t的个数，表示当前路径所在的层级

• 2.2.计算当前的路径名长度，并识别当前路径是否为文件

• 2.3.根据当前路径所在的层级，移除栈顶直到栈顶为当前路径名的父路径名

• 2.4.更新维护变量。将当前路径长度添加到栈顶；如果当前路径是文件，则更新结果变量

第三步，返回结果

3.解题代码

python代码

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        # 思路：栈
        n = len(input)
        # 第一步，构建维护变量。stack的栈顶维护当前遍历字符所在路径的父路径的长度
        stack = []
        result = 0
        i = 0
        # 第二步，遍历字符串，更新维护变量
        while i < n:
            # 2.1.统计\t的个数，表示当前路径所在的层级
            k = 0
            while input[i] == "\t":
                i += 1
                k += 1
            # 2.2.计算当前的路径名长度，并识别当前路径是否为文件
            length = 0
            isFile = False
            while i < n and input[i] != "\n":
                if input[i] == ".":
                    isFile = True
                i += 1
                length += 1
            # 2.3.根据当前路径所在的层级，移除栈顶直到栈顶为当前路径名的父路径名
            while len(stack) > k:
                stack.pop()
            # 2.4.更新维护变量。将当前路径长度添加到栈顶；如果当前路径是文件，则更新结果变量
            if stack:
                length += 1
                stack.append(stack[-1] + length)
            else:
                stack.append(length)
            if isFile:
                result = max(result, stack[-1])
            i += 1
        # 第三步，返回结果
        return result

c++代码

class Solution {
public:
    int lengthLongestPath(string input) {
        int n = input.size();
        stack<int> st;
        int result = 0;
        int i = 0;
        while (i < n) {
            int k = 0;
            while (i < n && input[i] == '\t') {
                i++; k++;
            }
            int length = 0;
            bool isFile = false;
            while (i < n && input[i] != '\n') {
                if (input[i] == '.') {
                    isFile = true;
                }
                i++; length++;
            }
            while (st.size() > k) {
                st.pop();
            }
            if (!st.empty()) {
                length++;
                st.push(st.top() + length);
            } else {
                st.push(length);
            }
            if (isFile) {
                result = max(result, st.top());
            }
            i++;
        }
        return result;
    }
};

4.执行结果