Stack

【LeetCode】

LeetCode中关于栈的题目其实不算很多，用到的套路也比较单一。

71 Simplify Path。

题目描述：

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Corner Cases:

Did you consider the case where path = "/../"?
In this case, you should return "/".

Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".

这题其实有很大的实际应用意义，主要是对Linux/Unix系统路径的表达。

用ArrayDeque作栈的解法：

 1 class Solution {
 2     public String simplifyPath(String path) {
 3         Deque<String> stack = new ArrayDeque<>();
 4         Set<String> skip = new HashSet<>(Arrays.asList("..", ".", ""));
 5         for(String dir : path.split("/")){
 6             if(dir.equals("..") && !stack.isEmpty())
 7                 stack.pop();
 8             else if(!skip.contains(dir))
 9                 stack.push(dir);
10         }
11         String res = "";
12         for(String str : stack){
13             res = "/" + str + res;
14         }
15         return res.isEmpty() ? "/" : res;
16     }
17 }

其实上面这种解法很慢，相当的慢，在答案的排名中发现了别人的这种的解法，相当于手动模拟栈吧。

 1 class Solution {
 2     public String simplifyPath(String path) {
 3         int l = path.length(), i = 0, k = 0;
 4         char[] C = new char[l];
 5         char ch;
 6         for (; i < l; i++) {
 7             ch = path.charAt(i);
 8             if (ch != '/') {
 9                 C[k++] = ch;
10                 continue;
11             }
12             while (i < l - 1 && path.charAt(i + 1) == '/')
13                 i++;
14             if (i == l - 1)
15                 break;
16             if ((i < l - 3 && path.charAt(i + 1) == '.' && path.charAt(i + 2) == '.' && path.charAt(i + 3) == '/')
17                     || (i == l - 3 && path.charAt(i + 1) == '.' && path.charAt(i + 2) == '.')) {
18                 while (k > 0 && C[--k] != '/')
19                     ;
20                 i += 2;
21             } else if ((i < l - 2 && path.charAt(i + 1) == '.' && path.charAt(i + 2) == '/')
22                     || (i == l - 2 && path.charAt(i + 1) == '.')) {
23                 i++;
24             } else
25                 C[k++] = ch;
26         }
27         return (k == 0) ? "/" : String.valueOf(C, 0, k);
28     }
29 }