LeetCode.71-简化路径

简介: LeetCode.71-简化路径

以 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('/');
};



相关文章
|
12月前
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
93 0
|
算法 Unix 测试技术
力扣经典150题第五十二题:简化路径
力扣经典150题第五十二题:简化路径
128 0
|
5月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
255 14
|
6月前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
120 4
|
6月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
137 10
|
12月前
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
88 0
|
机器人 Python
【Leetcode刷题Python】62. 不同路径
LeetCode 62题 "不同路径" 的Python解决方案,使用动态规划算法计算机器人从网格左上角到右下角的所有可能路径数量。
200 0
|
存储 SQL 算法
LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
|
Python
【Leetcode刷题Python】113. 路径总和 II
LeetCode上113号问题"路径总和 II"的Python实现,通过深度优先搜索来找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
95 3
【Leetcode刷题Python】113. 路径总和 II
|
存储 Python
【Leetcode刷题Python】64. 最小路径和
一种使用动态规划解决LeetCode上64题“最小路径和”的Python实现方法,通过维护一个一维数组来计算从网格左上角到右下角的最小路径总和。
78 1
【Leetcode刷题Python】64. 最小路径和

热门文章

最新文章