[Leetcode]388. Longest Absolute File Path

[Leetcode]388. Longest Absolute File Path
https://leetcode.com/problems/longest-absolute-file-path/#/description

据说这是google的OA题目, 改了一些, 原来是求图片文件的路径和, 这里只求最大的文件数, 但是思路还是一样的。

拿到题完全没有头绪。只是觉得\n \t很重要。无论如何肯定要\n不管你是不是属于同一个目录下面的。\t呢就是如果和前一个t一样多，就是同一个目录，如果多一个或者少一个就不是同一个目录了。开始觉得同一个目录里只要比末尾的长短就行了，因为前面是一样长的嘛。但是如果末尾的一个是file另一个是文件夹，这么想就不对，最末尾没文件，只有文件夹的不算到达file最长路径。

初步想法，这是一个找爸爸游戏，n就说明有新换行了，而3个t的爸爸就是2个t，2个t的爸爸就是1个t，1个t的爸爸就是没有t。但是如果按照这个思路想，复杂度是n²，有什么办法可以是n复杂度呢？看过的不要看， 难道是DP？第一个可行的办法是Hashmap，存下来我们已知的路径，等看到它的自路径的时候，直接去找就好了。

解题思路：

思路一：HashMap解法
1. 用HashMap存下来不同深度的文件夹的长度；
2. 遇到file，更新最大file路径长度；
3. 遇到文件夹，更新HashMap里文件夹长度；

我们这里只要储存文件夹长度就行，因为遇到file其实就直接能算出结果了。然后遇到文件夹如果没有那个深度的对应map，就加进去，有的话就更新。Java里put这个函数，有的话直接更新，不用再判断一次了。

我一开始有个担心的地方，就是我们如果更新了这个深度的map，那上一个深度的文件夹长度就不见了啊。但是，这个担心是多余的，因为整个扫的过程是顺序的，我们到达了这个最新的文件夹的时候，上一个文件夹里面的文件已经都处理过了，不需要了。代码十分简洁。

思路二： Stack解法
细心地你一定可以发现，我们上面用HashMap的时候，如果遇到下一个文件夹的时候，可以overwirte上一个在深度map里的长度值。因为当你跳出更深的文件夹之后，来到深度浅的文件夹，以前的深度都没用了，因为上一段说了的原因，就是顺序的读取字符串，我们已经把深度深的文件读完了。所以map中就保留了多余的东西。因此，我们可以考虑用stack，这样没有用的就直接pop走就好。stack里面存什么呢？就存到目前为止，文件夹的长度，一样，我们不存文件名字，文件名字只用来计算。这时，深度信息由stack的长度记录，我们就不需要一个新的数据结构啥的记录了，当然，带来的问题就是我们需要数stack长度。


闲言少叙，直接上代码。

AC答案 一 HashMap：

public class Solution {
    public int lengthLongestPath(String input) {
        String[] list = input.split("\n");
        Map<Integer, Integer> depthHash = new HashMap<Integer, Integer>();
        depthHash.put(0,0);
        int result = 0;
        for(String s : list){
            int d = s.lastIndexOf("\t") + 1;
            int len = s.substring(d).length();
            if(s.contains(".")){
                int dirLen = depthHash.get(d);
                result = Math.max(result, dirLen + len);
            }else{
                depthHash.put(d+1, depthHash.get(d) + len +1); // 1 for /
            }
        }
        return result;
    }
}

思路里面有两个小坑，第一个是文件夹长度加的时候要在加一个1， 以为数长度的时候还数了那个左斜杠。第二个是在更新文件长度的时候读取的是它前一个hashmap元素，但是更新文件夹的时候要更新自己的长度，所以深度d要加1. 另外就是，长度len需要用substring，毕竟我们不想要前面的t。这个d很神奇啊，d不但表示了深度，还在substring的时候表达了起始值。substring这个函数是闭开区间，所以这个d正好合适。

还有一点发现就是，HashMap是两个大写，但是Hashtable只有开头大写，神奇吧。


AC答案二 Stack：

public class Solution {

    public int lengthLongestPath(String input) {
        String[] dirList = input.split("\n");
        Stack stack = new Stack<Integer>();
        stack.push(0);
        int result = 0;                              
        for(String s : dirList){
            int depth = s.lastIndexOf("\t") + 1;
            String dir = s.substring(depth);
            int dirLen = dir.length();
            while(stack.size()>depth+1){
                stack.pop();
            }
            if(s.contains(".")){
                result = Math.max(result, dirLen + (int)stack.peek());
            }else{
                stack.push((int)stack.peek() + dirLen + 1);
            }
        }                                       
        return result;                                                                 
    }
}

这个调试了好久，主要是在while的pop上面，depth +1 很重要，我们初始化stack，放进去个0，这样就不用验证stack为空的情况， depth 加一保证不为空。peek有结果