☆打卡算法☆LeetCode 71、简化路径 算法解析

发表于

这是我参与11月更文挑战的第30天，活动详情查看：2021最后一次更文挑战

推荐阅读

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个纸箱某一个文件或目录的绝对路径字符串，返回更加简洁的规范路径。”

题目链接：

来源：力扣（LeetCode）

链接：71. 简化路径 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

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

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

  • 始终以斜杠 ‘/‘ 开头。
  • 两个目录名之间必须只有一个斜杠 ‘/‘ 。
  • 最后一个目录名（如果存在）不能 以 ‘/‘ 结尾。
  • 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘..’）。
    返回简化后得到的 规范路径 。
1
2
3
4
ini复制代码示例 1：
输入： path = "/home/"
输出： "/home"
解释： 注意，最后一个目录名后面没有斜杠。
1
2
3
4
ini复制代码示例 2：
输入： path = "/../"
输出： "/"
解释： 从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

二、解题

1、思路分析

这道题，先分析题意，给定一个路径，进行简化，有几种情况：

  • 多个连续/简化为一个/
  • 一个点.表示当前目录，去除
  • 两个点..表示上机目录，需返回上一级

当遇到两个点，需要返回上级目录，类似于弹出栈顶元素的操作。

遍历路径字符串，遇到/就跳过，遇到非斜杠，统计两个斜杠中间的.点数，一个点表示同级目录，跳过；

两个点标识上级目录，弹出栈顶元素。

当为其他字符串即为文件名时，直接入栈。

2、代码实现

代码参考：

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
29
30
31
32
33
34
35
36
37
38
39
40
csharp复制代码public class Solution {
    public string SimplifyPath(string path) {
            Stack<string> s = new Stack<string>();
            string[] spiltArr = path.Split('/');
            for (int i = 0; i < spiltArr.Length; i++)
            {
                if (spiltArr[i] == "")
                {
                    continue;
                }

                if (spiltArr[i] == "..")
                {
                    if (s.Count > 0)
                    {
                        s.Pop();
                    }
                }
                else if (spiltArr[i] != ".")
                {
                    s.Push(spiltArr[i]);
                }
            }

            if (s.Count != 0)
            {
                StringBuilder sb = new StringBuilder();
                while (s.Count != 0)
                {
                    sb.Insert(0, s.Pop());
                    sb.Insert(0, "/");
                }
                return sb.ToString();
            }
            else
            {
                return "/";
            }
    }
}

image.png

3、时间复杂度

时间复杂度 ： O(n)

字符串中每个字符最多被遍历一次。

空间复杂度： O(n)

其中n代表字符串的长度。

三、总结

Linux的目录层级就是用栈实现的, 为了简单，直接使用字符串模拟栈的操作。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%