每日一练:LeeCode-71. 简化路径(中)【栈】

2024-01-02 18:55:16

本文是力扣LeeCode-71. 简化路径(中) 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐LeeCode

给你一个字符串 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 风格绝对路径。

栈方法

思路:
按照题意,我们不需要处理:空字符串、一个点,因为 空字符串 没有任何含义,而 一个点 表示当前目录本身,我们无需切换目录,我们只需要处理以下情况即可:

  • 两个点 ".."
  • 只包含英文字母、数字或的目录名

对于以上情况,我们可以用一个栈来维护路径中的每一个目录名。当我们遇到".."时,需要将目录切换到上一级,因此只要栈不为空,我们就弹出栈顶的目录当我们遇到「目录名」时,就把它放入栈

因此,我们只需要遍历每个字符串并进行上述操作即可。在所有的操作完成后,我们将从栈底到栈顶的字符串用 进行连接,再在最前面加上"/" 表示根目录,就可以得到简化后的规范路径。

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new LinkedList<>();
        for(String pItem : path.split("/")){ //直接以"/"切割即可,切割后的结果(".","..","a",空字符串)
            if(pItem.equals("..")){
                //需要将目录切换到上一级,因此只要栈不为空,我们就弹出栈顶的目录 
                if(!stack.isEmpty())stack.pop();    
            }else if(!pItem.isEmpty()&&!pItem.equals(".")){ //排除空字符串和(.)入栈的情况,保证只有目录名入栈即可
                stack.push(pItem);
            }
        }
        String result = "";
        for(String s: stack){   //拼接路径
            result = "/" + s + result;  
        }
        return result.isEmpty()?"/":result; //处理这种情况"/../"
    }
}

大家有更好的方法,请不吝赐教。

文章来源:https://blog.csdn.net/kdzandlbj/article/details/135346203
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。