网站 制作免费发布广告

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 简化路径

原题连接


思路如下：

1. 我们根据 "/" 去拆分字符串，得到每个子目录。这里拿到的子目录可能是空字符串，需要注意一下。
2. 我们遍历这个目录，用一个双向队列存储合法的子目录。
3. 如果遇到的子目录是 ". ." ，说明是向上层目录前进，我们从移除队尾元素。
4. 如果遇到的子目录是 "."，咱啥也不用管。
5. 剩余的子目录都是有效路径，我们往队尾塞。
6. 最后我们再次遍历双向队列，从队首开始取，拼接字符串得到最终的简化路径。

public String simplifyPath(String path) {LinkedList<String> queue = new LinkedList<>();for (String item : path.split("/")) {if (item.equals("..")) {// 队列必须非空，我们才能移除if (!queue.isEmpty()) {queue.pollLast();}} else if (!".".equals(item) && !item.isEmpty()) {// 这里注意一下，空元素以及 "." 我们都不用管queue.addLast(item);}}StringBuilder res = new StringBuilder();// 从队首元素开始取元素，拼接字符while (!queue.isEmpty()) {res.append("/" + queue.pollFirst());}String rr = res.toString();// 最后再判空一下return rr.isEmpty() ? "/" : rr;
}