leetcode每日一题——简化路径（算法待验证）

本文主要是介绍leetcode每日一题——简化路径（算法待验证），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：简化路径

题目链接：https://leetcode-cn.com/problems/simplify-path

一、问题描述

给你一个字符串 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第一个/压入栈底，这个必须留下，就不用动它了，接下来将字符串依次入栈，入栈过程中需要进行判断

　　1、当栈顶元素为”/“时：若入栈元素为”/“，则不入栈；若入栈元素为数字字母下划线则入栈；若入栈元素为”."也进行入栈。

　　2、当栈顶元素为”.“时：若入栈元素为”/“，则不入栈并且将”.“弹出直到栈顶元素为“/”时；若入栈元素为字母数字下划线就入栈；若入栈元素为“.”则也压入栈。

　　3、当栈顶元素为字母数字下划线时；入栈元素都可以入栈。

　　上面的只是基本思路，其实这个代码最难的地方在于处理"..."这种目录名，这很容易就被判断成返回上级目录的那种文件操作了。

　　所以我还需要维护一个栈来判断当前出栈的元素是“..”还是“.”还是目录名

　　从栈1出栈的元素依次压入栈2，然后把栈2清空并拼接成一个字符串，对这个字符串判断即可

　　如果字符串是".."则弹出栈1中元素直到"/"停止

　　如果字符串是"."则什么都不做

　　如果字符串不属于上面两种情况则将这个字符串再压回栈1，并且在栈尾加“/”；

　　最后遍历完path串后弹出栈1全部元素，（可以把这些元素压入栈2做个逆序），或者把这些元素反转都可以完成路径的简化

三、代码

　　代码过程以后给出，我认为上述方法是可行的。

这篇关于leetcode每日一题——简化路径（算法待验证）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！