LeetCode | 6. ZigZag Conversion

题目链接：https://leetcode.com/problems/zigzag-conversion/
题目难度：Medium
题目描述：

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"

Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

相关主题：String

思路 1 - 装子弹

如果横向把字符串压扁，让同一行的字符串首尾相接，这个问题可以想象成一个“装子弹”的过程。我们有一大串没有拆封的子弹 s，每个子弹上都印着一个字符，我们需要把这些子弹装到子弹槽中。由上至下，我们总共有numRows 个子弹槽，分别编号 1, 2, ..., numRows。在装子弹时，我们采用 S 形的装填方式，从 1 号开始，到 numRows 号，然后折返，从 numRows-1 号回到 1 号。最后，我们按照子弹槽的编号，依次读出其中装填的子弹上的字符就可以了。

经过观察，我们可以发现，每经过 numRows*2-2 个子弹，装填子弹槽的顺序就会重复。所以我们只要想好前 numRows*2-2 个子弹怎么装填就好了。前 numRows*2-2 个子弹的装填过程又可以分为两个部分，前 numRows 个是顺序装填的过程，第 numRows+1 到第 numRows*2-2 个是折返的过程（numRows >= 3）。

时间复杂度：
空间复杂度：

// C++
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows <= 1) {
            return s;
        }
        vector<char> v[numRows];
        string result = "";
        for (int i = 0; i < s.size(); i++) {
            if (numRows == 2) {
                int mod = i % numRows;
                v[mod].push_back(s[i]);
            } else {
                int mod = i % (numRows * 2 - 2);
                if (mod <= numRows - 1) {
                    v[mod].push_back(s[i]);
                } else {
                    int index = (numRows - 1) - (mod - (numRows - 1));
                    v[index].push_back(s[i]);
                }
            }
        }
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < v[i].size(); j++) {
                result.push_back(v[i][j]);
            }
        }
        return result;
    }
};

思路 2 - 按行筛

思路 1 需要把所有的字符都存储在不同的子弹槽里，然后再按顺序取出来，这带来了额外的开销。然后我想到可以改变遍历的顺序，由原来的按字符遍历改成按行遍历，把需要的字符按行筛选出来，就不用再占用额外的空间了。

思路 1 中已经提到，每经过 numRows*2-2 个子弹，装填子弹槽的顺序就会重复。我们把字符分成若干段，每段的长度是 numRows*2-2，字符在每段中的位置就决定了它会被分配到哪一行。针对每一行，我们遍历所有的字符分段，第 1 行和第 numRows 行最多从每段中取出一个字符；中间的行最多从每段中取出两个字符。对于取出两个字符的情况，可以发现这个两个字符到所在字符段第 numRows 行字符的距离是相等的，因此我们可以通过添加条件让几种情况合并（n > 0 对应第 1 行的情况，i == index 对应第 numRows 行的情况）。

时间复杂度：
空间复杂度：

// C++
class Solution {
   public:
    string convert(string s, int numRows) {
        if (numRows <= 1) {
            return s;
        }
        string result = "";
        int len = s.size();
        for (int n = 0; n < numRows; n++) {
            int i = n;
            while (i < len) {
                result.push_back(s[i]);
                int index = i + 2 * (numRows - 1 - n);
                if (index < len && n > 0 && i != index) {
                    result.push_back(s[index]);
                }
                i = i + (numRows * 2 - 2);
            }
        }
        return result;
    }
};

2019年04月09日