记录字节算法实习岗面试的一道算法题

问题描述

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（..）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径

请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

示例 1：

1
2
3

输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2：

1
2
3

输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。

示例 3：

1
2
3

输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

1 2	输入："/a/./b/../../c/" 输出："/c"

示例 5：

1 2	输入："/a/../../b/../c//.//" 输出："/c"

示例 6：

1 2	输入："/a//b////c/d//././/.." 输出："/a/b/c"

逻辑清晰的解答

这道题是面试字节暑期实习算法岗的一道算法题。没通过AC，思路也没写对。通过这次面试，让我明白了原来“算法题”不仅仅考察算法，也考察我们的逻辑清晰度，这道题几乎没有什么算法在里面，只要我们考虑全面，基本都可以做出来。写的代码不被AC，或者思路不正确的大部分原因是输入情况未考虑全面，例如本题，当时我仅考虑到：

1. 含有一个点
2. 含有两个点
3. 开头有没有'/'，没有斜杠要怎么处理(与面试官讨论)
4. 结尾有没有'/'

5. 甚至误以为一个文件名只有一个字符，切到上一级目录使用了固定偏移(错的太多了)
6. 甚至没有考虑还有两个连续的'/'
7. 更别提考虑连续多级'..'

总之有太多case没考虑到，这提醒我们，在写代码之前一定不能只针对一种case写。很有可能自己想的算法本身就是错误的、行不通的。只有全面考虑多种case，并且认为自己的算法能够处理这么多种情况，或者很容易扩展处理，才可以写代码。

我总想着把所有操作融入到一个循环中，以此提高效率，而没有从解决问题的本身出发。搞清楚本题本身是最重要的，效率其次之~

这道题，我们延续数据清洗的思路，对字符串路径以此按/ . ..顺序清洗，然后最后再连接符合要求的字符串。

class Solution {
public:
    string simplifyPath(string path) {
        int size = path.size();
        if (size == 0) return path;

        // 处理'/'
        stack<string> st;
        int last_seq = 0;
        for (int i = 0; i < size; ++i) {
            // 从左向右处理
            if (path[i] == '/') {
                if (i - last_seq > 1) {
                    st.push(path.substr(last_seq+1, i-last_seq-1));
                    printf("%s ", st.top().c_str());
                }
                last_seq = i;
            }
        }
        if (path[size-1] != '/') st.push(path.substr(last_seq+1));

        // 处理'.'
        queue<string> st_c;
        while (!st.empty()) {
            // 从右向左处理
            if (st.top().compare(".") != 0) st_c.push(st.top());
            st.pop();
        }

        // 处理".."
        int last_nums = 0;
        while (!st_c.empty()) {
            // 从右向左处理
            if (st_c.front().compare("..") == 0) ++last_nums;
            else {
                if (last_nums == 0) st.push(st_c.front());
                if (last_nums > 0) --last_nums;
            }
            st_c.pop();
        }

        // 连接字符串
        string new_path = "";
        while (!st.empty()) {
            // 从左向右处理
            new_path += "/" + st.top();
            st.pop();
        }
        if (new_path.size() == 0) return "/";
        return new_path;
    }
};

如果还需要处理其它情况，也非常容易在此基础上扩展。逻辑复杂的题，代码运行效率往往不是首先要考虑的因素。首先应该要以清晰的代码梳理逻辑，通过所有情况的测试，然后才去考虑如何优化效率。

PS：很多情况下逻辑比效率更重要。错误的目标会导致白费的努力~