简化路径标｜Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述：

二、思路分析：

今天给大家分享的这道题目是楼主在翻阅掘金站内面经时看到的，恰巧这道题楼主在当年校招面试微软的时候，遇到过，当时小白，啥都不会。没想到居然是原题，哎。那就来刷一下吧。

• 题目给的输入是一个字符串，表示一个Unix下的文件路径，让我们根据规则简化一下输入；
• 具体简化规则是: 一个 . 表示当前目录；2个 . 表示将当前目录切换到上一级；任意连续 / 被视为单个斜杠。
• 其他格式的都被视为文件名或者目录名

打眼一看，这题应该是用栈，对吧 ？

遍历字符串分隔

直接切分

一开始也想了一下直接按照 / 分隔一下输入，然后处理。不过没想明白。就没继续了，看了大佬的解法后，没想到是这么简单

• 直接按 / 分隔输入,得到 paths
• 然后开始遍历paths,如果遇到 .. 并且栈内有元素的时候，之前弹出栈内元素。
• 遇到 . 和 “” 的时候，跳过。
• 其他情况直接入栈。
• 最后把栈内元素使用 / 链接起来。
• 最后在开头拼上 / 。

三、AC 代码：

//自己写的
class Solution {

    /**
     * @param String $path
     * @return String
     */
    function simplifyPath($path) {
        $len_s = strlen($path);
        $i = 0;
        $arr = [];
        $temp = "";
        while ($i < $len_s) {
            $cur = $path[$i];
            if ($cur == "/") {
                if (empty($temp)) {
                    $temp = "/";
                } else {
                    $arr[] = $temp;
                    $temp = "/";
                }
            } else {
                $temp = $temp . "". $cur;
            }
            $i++;
        }
        $arr[] = $temp;
        $stack = new SplStack();
        for ($i = 0; $i < count($arr); $i++) {
            if ($arr[$i] == "/." || $arr[$i] == "/") {
                continue;
            } elseif ($arr[$i] == "/..") {
                if (!$stack->isEmpty()) {
                    $stack->pop();
                } else {
                    // return "/";
                    // $stack->push("/");
                    continue;
                }
            } else {
                $stack->push($arr[$i]);
            }
        }

        $res = join("", array_reverse(iterator_to_array($stack)));
        return $res === "" ? "/" : $res;
    }
}


//看了评论区的题解后
class Solution {

    /**
     * @param String $path
     * @return String
     */
    function simplifyPath($path) {
        $len_s = strlen($path);
        $paths = explode("/", $path);
        $stack = new SplStack();
        foreach ($paths as $p) {
            if ($p == "..") {
                if (!$stack->isEmpty()) {
                    $stack->pop();
                }
            } elseif ($p == "." || $p === "") {
                continue;
            } else {
                $stack->push($p);
            }
        }

        $res = array_reverse(iterator_to_array($stack));
        return "/".join("/", $res);
    }
}


复制代码

四、总结：

其实本题中隐藏着一个回退到上一级的操作，一般出现这种情况我们会考虑使用栈这种数据结构。