想要精通算法和SQL的成长之路 - 简化路径

前言

想要精通算法和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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21