White's Studio.

unix简化路径

Leedcode
2018/07/31 Share

unix简化路径

在 leedcode 里做了一道题， 题目是这样的

给定一个文档 (Unix-style) 的完全路径，请进行路径简化。

例如，
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

边界情况:

  • 你是否考虑了 路径 = "/../" 的情况？
    在这种情况下，你需返回 "/" 。
  • 此外，路径中也可能包含多个斜杠 '/' ，如 "/home//foo/" 。
    在这种情况下，你可忽略多余的斜杠，返回 "/home/foo" 。

我的算法很简单， 首先先把所有的 “/” 去掉，因为路径就是用“/”分割了，内容都是在“/”之间，

而内容只有几种类型:

​ 1）目录名；

​ 2）“.”; 表示当前目录

​ 3) “..”; 表示上级目录

​ 在本题中，2）和 3）都是需要消灭掉的，所以我遍历每个数组的，遇到“.”就直接取当前目录，直接把当前数组的值推出来；遇到“..”，就当前一个数组的内容也切掉

​ 当然还有些一些特殊处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
  let pathArray = path.split("/")
  for (let i = 0; i < pathArray.length; i++) {
    if (pathArray[i] === '.' || (i > 0 && pathArray[i] === '') ) {
      pathArray.splice(i, 1)
      i = i - 1
    } else if (pathArray[i] === '..') {
      if (i > 0) {
        pathArray.splice(i - 1, 2)
        i = i - 2
      } else {
        pathArray.splice(i, 1)
        i = i - 2
      }
    }
  }

  if (pathArray.length === 1) return `/${pathArray[0]}`
  if (pathArray.length === 0) return `/`
  if (pathArray[0] !== '') return `/${pathArray.join('/')}`
  return pathArray.join('/')
}

然后我看了一下这个算法的执行效率还是蛮高的：我的提交执行用时 已经战胜 97.06 % 的 javascript 提交记录

而在我这个算法前面的只有一个算法了， 如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
  const len = path.length
  let arr = Array.from({length: 10}).map(() => '/')
  let point = 0
  let i = 0
  while (i < len) {
    i++
    let mid = ''
    while (i < len && path[i] !== '/') {
      mid += path[i++]
    }
    if (mid === '..') {
      point = point > 0 ? point - 1 : 0
    } else if (mid && mid !== '.') {
      arr[++point] = mid
    }
  }
  let res = ''
  for (let j = 1; j <= point; j++) {
    res += '/' + arr[j]
  }
  if (!point) res = '/'
  return res
};

原文作者: White

原文链接: http://yuchenzhen.github.io/2018/07/31/simplifyPath/

发表日期: July 31st 2018, 10:12:18

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. unix简化路径
Total : 31
2019
2018
Java Binary_Tree Python Node.js RPC git List Leetcode Leedcode LeetCode LintCode Node.js dubbo electron Java Spring-boot hexo 脑洞题 消息队列 Leetcode Java 数据结构，二叉树 Algorithm