[LeetCode] 用 Table 來解 #6 ZigZag Conversion

LeetCode #6 官網的解答第一個其實就很好了解，所以似乎這題看起來沒必要寫文章?

但我就想用一些原創、網路上找不到的方法、又簡單的把他解掉。

題目與解法

例如他把一疊標記 ABCD... 的卡片擺成這樣:

你要從左到右，從上到下的順序把卡片重新排列輸出:

當然我第一個想到的就是用 table 的方式讓他把字串擺進我的 table 中，我再來從左到右、從上到下慢慢掃就結束啦。

最後再把 "*" 的字元刪掉就好了。

因為我們變成 table 所以我們需要知道 table 的寬度才能正確計算從 2D 變成 1D 的 index，我們其實可以把它變成一個一個 group 來算:

程式碼

所以 C++ 程式碼就會長這樣:

#include <algorithm>

class Solution {
 public:
  std::string convert(std::string s, int numRows) {
    if (numRows == 1) return s;
    const int numColumns = calcNumColumns(s, numRows);
    std::string output(numRows * numColumns, '*');
    int row = 0, col = 0;
    bool goingDown = true;
    for (const char c : s) {
      const int index = row * numColumns + col;
      output[index] = c;

      row += (goingDown ? 1 : -1);
      col += (goingDown ? 0 : 1);
      if (row == 0) goingDown = true;
      if (row == numRows - 1) goingDown = false;
    }
    output.erase(std::remove(output.begin(), output.end(), '*'), output.end());
    return output;
  }

 private:
  int calcNumColumns(const std::string &s, const int numRows) {
    const int len = (int)s.size();
    const int groupSize = 2 * (numRows - 1);
    const int groupWidth = numRows - 1;
    const int numGroups = len / groupSize;
    const int remainder = len % groupSize;
    int lastGroupSize = 0;
    if (remainder > 0 && remainder <= numRows) {
      lastGroupSize = 1;
    } else if (remainder > numRows) {
      lastGroupSize = 1 + (remainder - numRows);
    }
    return numGroups * groupWidth + lastGroupSize;
  }
};

比較麻煩的是我要用 row 和 col 去追蹤他上上下下的位置，還有一開始要計算 columns 總共有幾個，看起來比 vector<string> 的要複雜多了。

不過我們可以再稍微想一下，我們一定要算出精準的 columns 數量嗎? 如果多加幾列(還是行)應該沒差吧:

反正多出來的 "*" 最後還是會被刪掉，所以我們可以粗略的計算一下就好，我們可以把 calcNumColumns 改一下，我們就不去計較最後一個 group 到底是一行還是兩行了:

  int calcNumColumns(const std::string &s, const int numRows) {
    const int groupSize = 2 * (numRows - 1);
    const int groupWidth = numRows - 1;
    const int numGroups = s.size() / groupSize;
    return (numGroups + 1) * groupWidth;
  }

結果當然會慢一點點，不過程式碼看起來就稍微變簡單了一點。

結果

前後兩個解法的結果分別是:

更棒的解法?

這個解法因為裡面有很多沒作用的 "*" 字元太佔空間了，我們有辦法不要用這些字元嗎?

有沒有什麼技巧可以忽略它?

下一篇我們就來介紹一個更棒的解法，而且最棒的是我們不用分析一堆奇怪的 index 計算。

GitHub

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