简化路径问题解析及实现（LeetCode 71）

在本文中，我们将探讨如何解决 LeetCode 上的第 71 题："简化路径"。该问题要求将给定的 Unix 风格绝对路径转换为更简洁的规范路径，并提供了一些规则和示例。

问题描述

给定一个字符串 path，表示指向某一文件或目录的 Unix 风格绝对路径（以 '/' 开头），要求将其转化为更简洁的规范路径。

具体规则如下：

点 . 表示当前目录本身；
两个点 .. 表示将目录切换到上一级（指向父目录）；
连续的斜杠 '//' 被视为单个斜杠 '/'；
其他格式的点如 '...' 均被视为文件/目录名称。

要求返回的规范路径必须遵循以下格式：

始终以斜杠 '/' 开头；
两个目录名之间只有一个斜杠 '/'；
最后一个目录名（如果存在）不能以斜杠 '/' 结尾；
路径仅包含从根目录到目标文件或目录的路径上的目录，不含 '.' 或 '..'。

解题思路

我们可以使用栈来处理这个问题。首先，我们将路径按照 '/' 进行分割，并遍历分割后的部分。然后根据规则将每个部分入栈或者出栈，最后将栈中的元素拼接成简化后的路径。

具体步骤如下：

将路径根据 '/' 分割成数组 parts；
创建一个空栈 stack；
遍历 parts 数组：
- 如果当前部分是 '..'，则出栈一个元素；
- 如果当前部分是 '.' 或者为空字符串，则跳过；
- 否则，将当前部分入栈；
最后，将栈中的元素用 '/' 连接起来，并在开头加上 '/'。

JavaScript 实现

下面是用 JavaScript 实现的简化路径函数：

const simplifyPath = function (path) {
  path.replace(/\/+/g, '/'); // 优化，把连续的/替换成当个/，防止生成过多空格
  const parts = path.split('/'); // 把路径分隔开
  const len = parts.length;
  const stack = [];
  for (let i = 0; i < len; i++) {
    switch (parts[i]) {
      case '..':
        stack.pop();
        break;
      case '.':
      case '':
        break;
      default:
        stack.push(parts[i]);
    }
  }
  return `/${stack.join('/')}`;
};

示例和测试

使用上述函数，我们可以进行一些示例和测试，例如：

console.log(simplifyPath('/../')); // 输出 "/"
console.log(simplifyPath('/home//foo/')); // 输出 "/home/foo"
console.log(simplifyPath('/a/./b/../../c/')); // 输出 "/c"

总结

简化路径问题需要我们根据规则对给定的路径进行处理，将其转化为更简洁的形式。通过使用栈来辅助处理，我们可以高效地解决这个问题，并通过示例验证函数的正确性。

目录CONTENT

简化路径（LeetCode 71）