@(LeetCode)
问题描述
假设我们将文件系统抽象为如下的字符串表示方式。
栗 1：
"dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" 表示如下文件目录结构：
dir
subdir1
subdir2
file.ext
其含义为：dir 包含两个子文件夹 subdir1 和 subdir2，subdir2 中包含一个文件 file.ext。
栗 2：
"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 表示如下文件目录结构：
dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext
其含义为：dir 包含两个子文件夹 subdir1 和 subdir2，其中 subdir1 包含文件 file1.ext 和子文件夹 subsubdir1，subdir2 包含一个子文件夹 subsubdir2，subsubdir2 又包含一个文件 file2.ext。
我们需要找出最长的文件路径长度。比如在第二个例子中，最长的路径为 dir/subdir2/subsubdir2/file2.ext，其长度为 32。
给定一个以上格式的字符串，返回最长文件路径长度，如果不存在文件，则返回 0。要求时间复杂度为 O(n)，n 为字符串的长度。
注意：
- 文件名至少包含一个
.和后缀。 - 文件夹名不会包含
.。
解题思路
题目的意思很明确，只需要求出文件路径最大长度。其目录层级以 \n\t... 来划分，可以看出 \t 的个数代表层级深度。
我的解法
思路
一开始想的挺复杂，想到了递归求解，因为这样的结构很容易陷入递归的思路。但是有时间复杂度的要求，决定了其不可能是以这种方式求解。
于是另外想思路。由于没有注意到是只需要求文件的最长路径，而不是文件夹/文件的最长路径，所以想的复杂了些，但是大致思路是相通的。
其实求总路径长度，只需要记下每级路径的长度，然后做加法求和即可。
其中平级的路径长度，永远记录的是当前层级。因为其是顺序排布，当平级的一个文件夹内部完全遍历完后，才会进行下一个平级文件夹的遍历。
在这个例子中：
dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext
subdir1 和 subdir2 是平级，并且是顺序遍历的，subdir1 在前， subdir2 在后。当遍历 subdir1 时，当前层级长度记录的是 subdir1 的长度；当遍历 subdir2 时，记录的则是 subdir2 的长度。
我们将路径层级记为从 0 开始。上述例子中，dir 代表 0 级，subdir1 代表 1 级，file.ext 代表 2 级。
记录的结果如下：
{
0:3,
1:7,
2:9
}
当遇到文件 file1.ext 时，其路径总长度为，将 depth = [0,2] 的所有路径长度相加，再额外加上 / 的个数（为当前层级深度）即可。结果为 3+7+9+2。
当遇到 subsubdir1 时，由于它是 2级目录，更新当前层级路径长度。结果为：
{
0:3,
1:7,
2:10,
}
当遇到 subdir2 时，由于它是 1 级目录，只需更新 1 级目录的值。结果为：
{
0:3,
1:7,
2:10
}
当遇到 file2.ext 时，它是 3 级目录，此时插入 3 级目录的路径长度。且其为文件，需要计算总的路径长度，方式同上：即 [0,3] 层级的路径长度之和 + / 个数。
{
0:3,
1:7,
2:10,
3:9
}
大体思路如上。
文件夹/文件的路径最大长度
顺便提一下，如果要求文件夹/文件的路径最大长度，那么需要判断当前路径是否为最深。
这种情况下需要求出紧接其后的层级。如果当前层级 >= 后面层级，则说明已经到底了。计算当前的路径长度，并与最大值进行比较即可。
比如 dir/subdir1，当前层级为 1，其后的层级 dir/subdir1/file1.ext为 2，说明当前还不是最深的路径。
又比如 dir/subdir1/file1.ext，当前层级为 2，其后的层级 dir/subdir1/subsubdir1 为 2，说明达到最深。
代码实现
在具体实现中，我没有使用类似 split 的方法，完全是一个个字符从头到尾的遍历，手动计算层级深度。同时加上了当前是否是最深路径的判断，但在这题中，其实只用判断是否为文件即可。
代码如下。
var lengthLongestPath = function(input) {
if (input && input.length > 0) {
const length = input.length
let maxLength = 0
// 当前路径深度
let curDepth = 0
// 记录每层路径的文件名长度
let map = new Map()
let i = 0
while (i < length) {
// 取出文件名
let name = ''
while (i < length && input[i] !== '\n') {
name += input[i]
i += 1
}
// 记录当前深度对应的文件名长度
if (name.length > 0) {
map.set(curDepth, name.length)
}
// 计算下一个路径深度
i += 1
let depth = 0
while (i < length && input[i] === '\t') {
depth += 1
i += 1
}
// 下一个深度比当前的小，说明当前路径达到最深，计算路径长度。且为文件
if ((depth <= curDepth) && (name.includes('.'))) {
// 从 0 到 lastDepath
let j = 0
let sum = 0
while (j <= curDepth) {
if (map.has(j)) {
sum += map.get(j)
}
j += 1
}
// 加上 '/' 个数
sum += curDepth
if (sum > maxLength) {
maxLength = sum
}
}
curDepth = depth
}
return maxLength
}
return 0
};
但这种方法，需要每次都需要从头遍历求和，效率还不算好。
优化解法
为了省去求和的过程，我们可以将存储的信息稍微变一下。之前存的是当前层级文件/文件夹的长度，但如果存为当前路径的总长度，就不需要计算了。
核心计算思想为：
当前层级的长度 = 上一层级的路径长度 + 当前文件/文件夹长度 + 1。
代码变动比较小，只贴出改动的部分：
// 记录总长度
if (curDepth >= 1) {
// 上一层的路径长度+文件长度+'/'
map.set(curDepth, map.get(curDepth - 1) + name.length + 1)
} else {
map.set(curDepth, name.length)
}
// 下一个深度比当前的小，说明当前路径达到最深，计算路径长度，且为文件。或者仅仅判断为文件。
if ((depth <= curDepth) && (name.includes('.'))) {
let sum = map.get(curDepth)
if (sum > maxLength) {
maxLength = sum
}
}
其他解法
在 discuss 区查看解法，发现有一种使用栈的方法。
其主要思想是，用栈来保存每一层级的总路径长度。其主要目的是用来找到上一层级的路径长度，当前层级的长度计算方式跟第二种解法一样。
如何找上一层级的路径长度时，其方式也比较简单，如下：
如果栈顶元素的层级 >= 当前元素层级，则循环出栈，直至找到其上一个层级，然后计算当前路径长度后入栈。否则，直接入栈。也就是说，栈中保存的始终为当前遍历路径上的各个层级路径长度。
若以代码实现的方式来表述，则为如下所述。
因为栈的长度 - 1 代表了栈顶元素的层级，判断条件变为: 当前的层级 <= 栈的长度 - 1，则循环出栈，否则，直接入栈。
比如：
dir
subdir1
subdir2
file.ext
在遍历 dir，subdir1 后，栈中的元素为 [dir, dir/subdir1]。这里是为了方便理解，将元素写成了路径，其实元素是路径的总长度。
在遍历 subdir2 时，当前层级为 1，这时需要找到 0 级目录才能拼成完整的路径。而此时栈顶是 1 级，那么就需要将其出栈，这样栈顶变为了 0 级目录 [dir]。再将计算结果入栈，变为 [dir, dir/subdir2]。
同样的道理，如果当前层级为 2，上一层级为 1，而假设此时栈中有 4 个元素
[dir, dir/subdir1, dir/subdir1/ss1, dir/subdir1/ss1/ss2]，那么需要连续出栈 2 次，计算后再将结果入栈。
网友评论