[LeetCode] 把 #6 ZigZag Conversion 當作蛇一樣，用圖像來解題

上一篇文章我們用了 Table 方式來嘗試解題，但程式碼有點複雜而且還比較慢。

我後來想了一下，原來我們只要畫蛇添足就可以用最快最省記憶體的方式來解這題！

畫蛇添足法

因為題目說要擺成這個方式，我們就真的要乖乖擺成這樣嗎?

這就讓我想到之前有 9 個點要你畫 4 條直線的思考遊戲，雖然我也滿討厭那個解答，不過我得說他可能貢獻了 8.7% 讓我想到下面這個方法:

如果我們把它擺成這樣方方正正的有什麼好處呢? 我們可以繼續用上一篇的 Table 方法來解:

只是這次我們非常好判斷什麼時候他會變成 '\0' 了，主要就是因為變成方方正正的。

唯一的例外就是每個字串的第一個頭，就把他想成蛇的頭好了。

我們只要 col=0~N, row=0~M 慢慢一個一個拜訪，然後再轉成像蛇在走路的 index 去讀 s 就行了:

看到這邊我相信你應該不用什麼複雜的 index 分析就知道該怎麼解了吧?

C++ 程式碼

根據上面投影片來實作，我們應該可以得到像下面這樣的程式碼:

class Solution {
 public:
  std::string convert(std::string s, int numRows) {
    if (numRows <= 1) return s;
    const int numCols = s.size() / (numRows - 1) + 1;
    std::string output;
    for (int r = 0; r < numRows; r++) {
      for (int c = 0; c < numCols; c++) {
        const int snakeIndex = getSnakeIndex(r, c, numRows);
        const char ch = getChar(s, snakeIndex, numRows);
        if (ch != '\0') output += ch;
      }
    }
    return output;
  }

 private:
  char getChar(const std::string &s, const int snakeIndex, const int numRows) {
    if (snakeIndex == 0) return s.at(0);
    if (snakeIndex % numRows == 0) return '\0';
    const int numEmpty = snakeIndex / numRows;
    const int realIndex = snakeIndex - numEmpty;
    if (realIndex >= s.size()) return '\0';
    return s.at(realIndex);
  }

  int getSnakeIndex(const int r, const int c, const int numRows) {
    const int baseIndex = c * numRows;
    if (c % 2 == 0) {
      // Downward
      return baseIndex + r;
    } else {
      // Upward
      return baseIndex + (numRows - 1 - r);
    }
  }
};

計算有幾個 columns 的 numCols 後面要 +1, + 2, +3 都隨意，有點類似上一篇的技巧，我們沒有要算的剛剛好，多一點點也沒差，因為 getChar 倒數第二行裡面會去檢查。不過因為我們底下的程式假設是會有空洞 ('\0') 的發生，所以 numRows 如果是 1 的話我們還是要把他先擋掉不然下面要例外處理反而會寫更多 code。

結果

和官網第二個解應該是不分上下的，第一次跑竟然還 0ms 但我覺得那應該只是 machine loading 比較低的時候才發生，我們還是貼一個比較合理的數據:

可以看到記憶體比上一篇的方法改善了非常多。

額外的優點: 可以平行化

上面的解法兩層 for 迴圈那邊其實並不用一定要按照那樣的順序，因為 (row, col) 到 snake index 其實是一對一的轉換關係。

如果用 functional programming 或 parallel programming 的角度來看其實這個解會比官方的第二個解好，我們來看一下 LeetCode 官方第二個解答:

for (int i = 0; i < numRows; i++) {
  for (int j = 0; j + i < n; j += cycleLen) {
    ret += s[j + i];
    if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
      ret += s[j + cycleLen - i];
  }
}

i 雖然看起來很單純但是 j 的終止條件和每次加多少就看起來複雜多了，這個情形下要平行化就比較困難一點。

GitHub

以上的 code 和投影片我都放在 GitHub 上了，有興趣的歡迎參考。