Java&C++题解与拓展——leetcode388.文件的最长绝对路径【么的新知识】

• 题目要求
• 思路：哈希表模拟
• • 记录路径【更通用】
  • • Java
    • C++
    • • C++中的`getOrDefault`方法
  • 记录长度【更符合本题场景】
  • • Java
    • C++
• 总结

【题目老长，其实就是目前的文件系统表示方式，从输入的一堆n t里找到文件、然后输出路径长度】

• 用一个哈希表存放每一级文件夹路径（或只存路径长度），若当前为文件则更新结果字符串，否则更新哈希表。
• t表示开启新的层级，层级相对于根目录，可理解为图中位于根目录下的第几行，是唯一值。
• n表示当前文件夹或文件结束。

【注意反斜杠作为转义字符不计入长度，所以类似t或n算一个字符，在这个地方判断卡了好久】

在哈希表中存放每一层到根目录的绝对路径。

class Solution {
    public int lengthLongestPath(String input) {
        Map map = new HashMap<>(); // 存当前层级（Integer）与相应路径（String）
        int n = input.length();
        String res = null;
        for(int i = 0; i < n; ) {
            int level = 0;
            while(i < n && input.charAt(i) == 't' && ++level >= 0)
                i++;
            int j = i;
            boolean isDir = true; // 是否为文件夹
            while(j < n && input.charAt(j) != 'n')
                if(input.charAt(j++) == '.') // 为文件
                    isDir = false;
            String cur = input.substring(i, j); // 当前文件名or文件夹名
            String pre = map.getOrDefault(level - 1, null); // 定位之前层级路径
            String path = pre == null ? cur : pre + "/" + cur; // 拼接绝对路径
            if(isDir) // 文件夹则更新哈希表
                map.put(level, path);
            else if(res == null || path.length() > res.length()) // 文件则更新结果
                res = path;
            i = j + 1;
        }
        return res == null ? 0 : res.length();
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

class Solution {
public:
    int lengthLongestPath(string input) {
        unordered_map map; // 存放当前层级（int）与相应路径（string）
        int n = input.size();
        string res = "";
        for(int i = 0; i < n; ) {
            int level = 0;
            while(i < n && input[i] == 't' && ++level >= 0)
                i++;
            int j = i;
            bool isDir = true; // 是否为文件夹
            while(j < n && input[j] != 'n')
                if(input[j++] == '.') //为文件
                    isDir = false;
            string cur = input.substr(i, j - i); // 当前文件名or文件夹名
            string pre = map[level - 1]; // 定位之前层级路径            
            string path = pre == "" ? cur : pre + "/" + cur; //拼接绝对路径
            if(isDir) // 文件夹则更新哈希表
                map[level] = path;
            else if(res == "" || path.size() > res.size()) // 文件则更新结果
                res = path;
            i = j + 1;
        }
        return res == "" ? 0 : res.size();
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

• 学习参考链接
• 其实就是判断有没有该元素，可以使用find判断迭代器是否在末尾，或者判断count是否为0。
• 上面没有用到，C++有自己的默认初值，但是就是忽然想到查了一下。

输出只需要长度，所以可以简化，只存长度不存路径。
可以将哈希表简化为数组，也可避免字符串的拼接操作。

class Solution {
    static int[] hash = new int[10001]; // 存放相应路径长度
    public int lengthLongestPath(String input) {
        Arrays.fill(hash, -1);
        int n = input.length(), res = 0;
        for(int i = 0; i < n; ) {
            int level = 0;
            while(i < n && input.charAt(i) == 't' && ++level >= 0)
                i++;
            int j = i;
            boolean isDir = true; // 是否为文件夹
            while(j < n && input.charAt(j) != 'n')
                if(input.charAt(j++) == '.') // 为文件
                    isDir = false;
            Integer cur = j - i; // 当前文件名or文件夹名长度
            Integer pre = level - 1 >= 0 ? hash[level - 1] : -1; // 定位之前层级路径长度
            Integer path = pre + 1 + cur; // 拼接绝对路径长度
            if(isDir) // 文件夹则更新哈希表
                hash[level] = path;
            else if(path > res) // 文件则更新结果
                res = path;
            i = j + 1;
        }
        return res;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( C ) O(C) O(C)

class Solution {
    int hash[10001]; // 存放相应路径长度
public:
    int lengthLongestPath(string input) {
        memset(hash, -1, 10001);
        int n = input.size(), res = 0;
        for(int i = 0; i < n; ) {
            int level = 0;
            while(i < n && input[i] == 't' && ++level >= 0)
                i++;
            int j = i;
            bool isDir = true; // 是否为文件夹
            while(j < n && input[j] != 'n')
                if(input[j++] == '.') //为文件
                    isDir = false;
            int cur = j - i; // 当前文件名or文件夹名长度
            int pre = level - 1 >= 0 ? hash[level - 1] : -1; // 定位之前层级路径长度
            int path = pre + 1 + cur; //拼接绝对路径长度
            if(isDir) // 文件夹则更新哈希表
                hash[level] = path;
            else if(path > res) // 文件则更新结果
                res = path;
            i = j + 1;
        }
        return res;
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( C ) O(C) O(C)

一道需要小思考的类“模拟”题目，上面用哈希表存放每一层级，其实也可改用栈存放，依次压入前序已遍历路径。