1700人點反對的LeetCode問題，是因為太難了嗎？

• 2020 年 5 月 27 日
• 筆記
• leetcode, LeetCode題解, Python, 演算法

本文始發於個人公眾號：TechFlow，原創不易，求個關注

今天是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（演算法比賽一般不允許使用Python），三兩行程式碼就可以輕鬆AC，而C++選手卻需要些上百行程式碼來實現高精度計算，這顯然是不公平的。所以acm比賽當中，出題人一定會盡量避免這種語言特性差異巨大的問題，大概這也是這題遭黑的原因吧。

這篇文章就到這裡，如果喜歡本文，可以的話，請點個關注，給我一點鼓勵，也方便獲取更多文章。