acytoo

Leetcode 71 Simplify Path

今天的每日一题是一道老题，2018年就AC过，但是当时是Java写的，今天用C++重写一遍。

非常直白的一道题，这也是早期LeetCode题目的特征：题意明显，不跟你扯一些乱七八糟的东西。要求简化类Unix文件系统下的路径。

直接的想法就是使用栈，遇到".."就弹出一个，遇到"."就忽略，注意，这里"..."一类的，以两个点开头而不仅仅是两个点的按照文件或者文件夹。遇到"/"就处理当前积压的路径。

使用栈的话，只能后进先出，最后组成路径的时候还要reverse一下，直接使用双向队列deque。

static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
class Solution {
 public:
  string simplifyPath(string path) {
    deque<string> dq;
    string cur = "";
    for (int i = 1, n = path.size(); i < n; ++i) {
      if (path[i] == '/') {
        if (!cur.empty()) {
          if (cur == "..") {
            if (!dq.empty())
              dq.pop_back();
          } else if (cur != ".") {
            dq.emplace_back(cur);
          }
          cur.clear();
        }
      } else {
        cur += path[i];
      }
    }
    if (!cur.empty()) {
      if (cur == "..") {
        if (!dq.empty()) dq.pop_back();
      } else if (cur != ".") {
        dq.emplace_back(move(cur));
      }
    }
    string res = "/";
    if (dq.empty()) return res;
    for (int i = 0, n = dq.size() - 1; i < n; ++i) {
      res += dq.front() + '/';
      dq.pop_front();
    }
    res += dq.front();
    return res;
  }
};

通过以后再看代码，感觉写的很丑：想到哪里就写哪里，很多情况可以合并。查看LeetCode其他人的提交，修改代码，使其看起来好看一些。

static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
class Solution {
 public:
  string simplifyPath(string path) {
    vector<string> vec;
    string cur;
    path.push_back('/');
    for (int i = 0, n = path.size(); i < n; ++i) {
      if (path[i] == '/') {
        if (cur.empty()) continue;

        if (cur == "..") {
          if (!vec.empty()) vec.pop_back();
        } else if (cur != ".") {
          vec.push_back(cur);
        }
        cur.clear();
      } else {
        cur.push_back(path[i]);
      }
    }
    string res = "/";
    for (auto &t : vec) res += t + "/";
    if (res.size() > 1) res.pop_back();
    return res;
  }
};
#直达链接

LeetCode 71. Simplify Path

相关文章：