做这题的时候对比了一下之前的代码,为什么差距这么大?

今天是 LeetCode专题的第40篇 文章,我们一起来看的是LeetCode中的71题Simplify Path,中文名是简化路径。

这题的难度是Medium,通过率是 1/3 左右,也是一道踩多捧少的题,一共有737个点赞,1703个反对。老实讲我觉得反对得不冤,我先卖个关子,等会来详细聊聊它为什么会被踩。

题意

题目会给定一个字符串,表示一个 Unix系统 下的文件路径,这个路径当中会包含一些路径的计算, 要求我们返回简化之后的结果。

在Unix系统下用/来分隔文件夹,比如/home/download/file.txt。在这个路径当中支持简单的运算,比如.表示当前文件夹。所以如果我们当前终端在download这个文件夹下,我们要访问file.txt文件,可以使用相对路径./file.txt即可。除此之外,还包括..操作,..表示当前文件夹的 上层文件夹

比如如果我们在download文件夹下,当我们运行cd ..,那么我们就会返回到download文件夹的上层,也就是home文件夹下。我们是可以把..和.嵌入在文件路径中使用的。比如说/home/download/../download/file.txt也是合法的,中间由于我们嵌入了..所以会返回到download的上层也就是home,然后再进入download。虽然这样很费劲,但是是合法的。只要你愿意,可以不停地利用..回到上层,来回穿梭。

我们要返回的是这个路径简化之后的版本也就是:/home/download/file.txt

我们来看几个案例:

Input: "/home/" Output: "/home" Explanation: Note that there is no trailing slash after the last directory name. Input: "/../" Output: "/" Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go. Input: "/a/../../b/../c//.//" Output: "/c" 

题解

这题其实也是 模拟题 ,不过相比之前我们做过的模拟题难度要小上很多。这道题的思路还是蛮明显的,由于存在..和.的操作,我们需要记录下来访问的路径,在..向上移动的时候把之前的文件夹抛弃掉。

举个例子,a/b/../b/d/e

我们在b之后使用了..回到了a,然后我们再次进入b往下。显然这里 由于..导致b在路径当中出现了两次 ,这是多余的。我们需要在..回到上层的时候把b抛弃掉。对于.操作来说,由于它就表示当前路径,所以对于答案并不会影响,我们直接忽略它的存在即可。

理解了这个思路之后,实现是非常简单的,我们只需要 根据/将字符串分 段。每一段当中除了.和..之外就是文件夹,我们用一个list去存储从上到下的经过的文件夹。最后用/将它们join在一起即可,唯一需要注意的是,当我们已经到了顶层的时候,如果我们继续执行..并不会报错,而是会停留在原地。所以我们需要特殊判断这种情况,除此之外就几乎没有难度了。

class Solution:     def simplifyPath(self, path: str) -> str:         folders = []         # 按照/分割         fs = path.split("/")         for f in fs:             # .直接跳过即可,不会影响结果             if f == '.':                 continue             # 如果是..需要判断是否在顶层             # 不在顶层的话抛弃掉最后插入的文件夹             if f == '..':                 if len(folders) > 0:                     folders.pop()             elif f != '':                 folders.append(f)                          return '/' + '/'.join(folders)

代码非常简单,只有10行左右。

总结

到这里,关于题解的部分就结束了。

我们回到标题当中的问题,为什么我会有这样的感受呢?是因为这道题我做过两次,上一次做的时候用的是C++。由于C++的string类型不支持split,所以我需要自己进行split处理。整个的计算过程非常复杂,我放一下C++的AC代码大家自己感受一下就知道了,简直不是一个次元的。

class Solution { public:     vector<string> split(string & path) {         vector<string> vt;         string cur = "";           // 遍历所有字符         for (int i = 0; i < path.length(); i++) {               // 如果是/ 说明需要把之前的内容放入vector             if (path[i] == '/') {                   // 如果是空或者是.就跳过,因为.没有意义                 if (cur != "" && cur != ".") {                     vt.push_back(cur);                 }                 cur = "";             }else cur = cur + path[i];         }           // 要注意最后遗留的字符串         if (cur != "" && cur != ".") vt.push_back(cur);         return vt;     }     string simplifyPath(string path) {         vector<string> dirs = split(path);         string ret = "";           // 存储文件的结构         vector<string> paths;         for (string str : dirs) {               // 如果是.. 则返回上级             if (str == "..") {                 if (paths.size() > 0) {                     paths.pop_back();                 }               // 否则则填入vector,表示合法             }else paths.push_back(str);         }         for (string str : paths) ret = ret + "/" + str;         if (ret == "") return "/";         return ret;     } };

我说这些的重点并不是吐槽C++这门语言有多么落后,或者是证明Python有多么强大。 不同的语言有不同的诞生背景,也有不同的强项 ,这个是很自然的。这题最主要的问题是不应该出这种因为语言本身的特性带来巨大差异的问题,在正规比赛当中出这样的问题一定是会被疯狂吐槽的。

举个例子,比如Java当中有大整数类BigInter,可以用来代替高精度算法来处理超过int64范围的大整数。如果有出题人出了一道非常复杂的大整数问题,那么使用Java的选手使用BigInter,三两行代码就可以轻松AC,而C++选手却需要些上百行代码来实现高精度计算,还不一定能做对。在极度激烈的比赛当中,一题的差距直接关系有无获奖。所以在acm比赛当中,出题人一定会尽量避免这种语言特性差异巨大的问题,大概这也是这题遭黑的原因吧。

这篇文章就到这里,如果喜欢本文,可以的话,请 点个关注 ,给我一点鼓励,也方便获取更多文章。

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章