「LeetCode」71-简化路径⚡️

简介: 「LeetCode」71-简化路径⚡️

image.png

前言🌧️


算法,对前端人来说陌生又熟悉,很多时候我们都不会像后端工程师一样重视这项能力。但事实上,算法对每一个程序员来说,都有着不可撼动的地位。


因为开发的过程就是把实际问题转换成计算机可识别的指令,也就是《数据结构》里说的,「设计出数据结构,在施加以算法就行了」。


编写指令的好坏,会直接影响到程序的性能优劣,而指令又由数据结构和算法组成,所以数据结构和算法的设计基本上决定了最终程序的好坏


题目🦀



71. 简化路径


难度中等


给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/' 开头),请你将其转化为更加简洁的规范路径。


在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,'//')都被视为单个斜杠 '/' 。 对于此问题,任何其他格式的点(例如,'...')均被视为文件/目录名称。


请注意,返回的 规范路径 必须遵循下述格式:


  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/'
  • 最后一个目录名(如果存在)不能'/' 结尾。
  • 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含 '.''..')。


返回简化后得到的 规范路径


示例 1:


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

示例 2:


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

示例 3:


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

示例 4:


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


提示:


  • 1 <= path.length <= 3000
  • path 由英文字母,数字,'.''/''_' 组成。
  • path 是一个有效的 Unix 风格绝对路径。


解题思路🌵


  • 利用栈这个数据结构来解决
  • 现将path根据/分割
  • 将文件名的入栈
  • 遇到..出栈

解题步骤🐂



  • 先split分割path
  • 用stack栈来维护数据结构
  • 遍历path
  • 遇到..弹栈
  • 遇到文件名入栈
  • 最后利用join 返回结果


源码🔥


/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
    const pathArr = path.split('/')
    const stack = []
    for(const identifier of pathArr){
        if(identifier==='..'){
            stack.pop()
        }
        else if(identifier && identifier!='.'){
            stack.push(identifier)
        }
    }
    return '/'+stack.join('/')
};

时间复杂度:O(n)


空间复杂度:O(n)


结束语🌞


image.png


那么鱼鱼的LeetCode算法篇的「LeetCode」71-简化路径⚡️ 就结束了,算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾,欢迎加我好友,一起沙雕,一起进步

业转载请注明出处。

相关文章
|
30天前
【LeetCode 35】112.路径总和
【LeetCode 35】112.路径总和
22 0
|
4月前
|
算法 Unix 测试技术
力扣经典150题第五十二题:简化路径
力扣经典150题第五十二题:简化路径
42 0
|
30天前
【LeetCode 36】113.路径总和II
【LeetCode 36】113.路径总和II
27 0
|
3月前
|
机器人 Python
【Leetcode刷题Python】62. 不同路径
LeetCode 62题 "不同路径" 的Python解决方案,使用动态规划算法计算机器人从网格左上角到右下角的所有可能路径数量。
68 0
|
5月前
|
存储 SQL 算法
LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
|
30天前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
11 0
|
3月前
|
Python
【Leetcode刷题Python】113. 路径总和 II
LeetCode上113号问题"路径总和 II"的Python实现,通过深度优先搜索来找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
41 3
【Leetcode刷题Python】113. 路径总和 II
|
3月前
|
存储 Python
【Leetcode刷题Python】64. 最小路径和
一种使用动态规划解决LeetCode上64题“最小路径和”的Python实现方法,通过维护一个一维数组来计算从网格左上角到右下角的最小路径总和。
32 1
【Leetcode刷题Python】64. 最小路径和
|
3月前
|
存储 算法 Linux
LeetCode第71题简化路径
文章讲述了LeetCode第71题"简化路径"的解题方法,利用栈的数据结构特性来处理路径中的"."和"..",实现路径的简化。
LeetCode第71题简化路径
|
3月前
|
算法
LeetCode第64题最小路径和
LeetCode第64题"最小路径和"的解题方法,运用动态规划思想,通过构建一个dp数组来记录到达每个点的最小路径和,从而高效求解。
LeetCode第64题最小路径和