LeetCode.71-简化路径

395 阅读2分钟

以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。

在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径

请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能/ 结尾。此外,规范路径必须是表示绝对路径的最短字符串。

示例 1:

输入:"/home/"
输出:"/home"
解释:注意,最后一个目录名后面没有斜杠。

示例 2:

输入:"/../"
输出:"/"
解释:从根目录向上一级是不可行的,因为根是你可以到达的最高级。

示例 3:

输入:"/home//foo/"
输出:"/home/foo"
解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。

示例 4:

输入:"/a/./b/../../c/"
输出:"/c"

示例 5:

输入:"/a/../../b/../c//.//"
输出:"/c"

示例 6:

输入:"/a//b////c/d//././/.."
输出:"/a/b/c"

解题思路1:

  1. 需要去除尾部的斜杠
  2. 需要去掉重复的斜杠
  3. 去掉“.”
  4. 把“..”和路径的上一级抵消

代码实现 :

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
  if(path === '/')
    return path;
  
  // 去掉尾部的斜杠
  while(path[path.length-1] === '/') {
    path = path.substr(0, path.length-1);
  } 
  console.log(path);
  // 去掉重复的斜杠
  let arr = path.split('');
  let pre = arr[0];
  let index = 1;
  while(index < path.length) {
    let cur = arr[index];
    if(pre === '/' && cur === '/') {
      arr.splice(index, 1);
    }
    else {
      pre = cur; 
      index++;
    }
  }
  // 重新以斜杠split
  arr = arr.join('').split('/');
  // 去掉.
  arr = arr.filter(item => {
    return item !== '.';
  })
  console.log(arr);
  // 去掉..
  index = arr.length-1;
  let count = 0;
  while(index > 0) {
    const cur = arr[index];
    if(cur ===  '..') {
      count++;
      // 删除..
      arr.splice(index, 1);
    } else {
      if(count > 0) {
        arr.splice(index, 1) ;
        count--;
      } 
    }
    index--;
  }
  
  return arr.join('/') !== '' ? arr.join('/') : '/';
};

解题思路2:

利用栈的思路,从左到右做遍历,遇到不是“..”且不是“.”且不是“”的就存入结果数组,遇到“..”就在结果数组中弹出一个路径做抵消
/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
  if(path === '/')
    return path; 
  
  let stack = path.split('/');
  let res = [];
  
  while(stack.length !== 0) {
    const cur = stack.shift();
    if(cur !== '..' && cur !== '.' && cur !== '/' && cur !== '') {
      res.push(cur);
    } else if(cur === '..') {
      res.pop();
    }
  }
  return '/' + res.join('/');
};
----------------------------------------------------------------