春招冲冲冲 008 一道题目

其他学校的考场十分的难找，其他学校面积真的大，饭堂真的豪华。

今天确实忙，半天在路上，一下就结束了一天。

祝考研的朋友们明天下笔如有神！

今天刷道题目。

晚安了，明早赶场。

一道题-简化路径

-> 笔记简化路径

粘贴这里来：

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/simplify-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

路径简化并不算复杂，规则无非就几点：

保留一个斜杠，即不得有连续的/出现
/./表示本路径，可以使用/表示
/a/../中..表示上一层路径
其他都不需要处理

明显，解决问题的时候，只需要按照这个规则描述即可，不难发现我们只需要处理/和.的问题处理即可，那么很简单，只需要保证/前面没有/，而遇到点则处理。

不难发现，对于.来说，除了路径的最后，其前后都需要有/才生效，否则无任何效果。那么对于.的处理应该放在发现/的时候处理，而遇到.时，前面不是/则不予于理会。

不过我们需要一样东西来记录最终的答案，题目属于栈类的题目，我们可以使用栈来作为存储容器。

看代码:

class Solution {
public:
    string simplifyPath(string path) {
        string res;
        std::deque<char> deq;
        int dot_count{0};

        path += '/';

        for (size_t i{0}; i<path.size(); ++i) {
            char ch = path[i];
            switch (ch) {
                case '/':
                    if (0 != dot_count) {
                        if ('.' != path[i-1]) {
                            --i;
                            continue;
                        }

                        switch (dot_count) {
                            case 2: {
                                // 向前
                                int slash{0};
                                while (2 != slash && !deq.empty()) {
                                    if ('/' == *(deq.end() - 1)) {
                                        slash += 1;
                                    }
                                    deq.pop_back();
                                }
                                deq.push_back('/');
                                break;
                            }
                            case 1:
                                deq.pop_back();
                                break;
                            default:
                                break;
                        }
                        dot_count = 0;
                    }

                    if (!deq.empty() && '/' == *(deq.end() - 1)) {
                        deq.pop_back();
                    }
                    deq.push_back('/');
                    break;
                case '.':
                    if ('/' == *(deq.end() - 1)) {
                        deq.push_back('.');
                        dot_count = 1;
                        continue;
                    }
                    deq.push_back('.');
                    if (0 != dot_count) {
                        dot_count+=1;
                    }
                    break;
                default:
                    dot_count = 0;
                    deq.push_back(ch);
                    break;
            }
        }

        if (1 != deq.size() && '/' == *(deq.end()-1)) {
            deq.pop_back();
        }

        while (!deq.empty()) {
            res += *(deq.begin());
            deq.pop_front();
        }

        return res;
    }
};

用例跑完8ms，还算可以，超77%。

首先给原有的字符串添加了/在末尾，这是为了处理原字符串末尾没有/的情况，如果末尾是.，按照里面的代码的思路会将末尾的.忽略掉，最简单的办法是照一个可以被处理的符号在末尾，/很适合。

还有其他的解法，可以尝试将字符串分割，分隔标识符为/，那么最终需要处理的是.，似乎更加简单。

不过现在停留在栈的学习中，对于对应标签的题目尝试使用纯粹的题目来解题。