题目描述

在行数等于3时，将字符串"PAYPALISHIRING"按”N”字形排列，如下所示：

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

此时我们按行读取，会得到"PAHNAPLSIIGYIR".

要求编写一个函数，输入一个字符串和一个整数(表示行数)，输出转换后的字符串：

string convert(string text, int nRows);

例如 convert("PAYPALISHIRING", 3)会返回"PAHNAPLSIIGYIR".

算法

(找规律) $O(n)$

这种按某种形状打印字符的题目，一般通过手画小图找规律来做。
我们先画行数是4的情况：

0     6       12
1   5 7    11 ..
2 4   8 10
3     9

从中我们发现，对于行数是 $n$ 的情况：

1. 对于第一行和最后一行，是公差为 $2(n - 1)$ 的等差数列，首项是 $0$ 和 $n - 1$；
2. 对于第 $i$ 行$(0 \lt i \lt n - 1)$，是两个公差为 $2(n - 1)$ 的等差数列交替排列，首项分别是 $i$ 和 $2n - i - 2$；

所以我们可以从上到下，依次打印每行的字符。

时间复杂度分析：每个字符遍历一遍，所以时间复杂度是$O(n)$.

C++ 代码

class Solution {
public:
    string convert(string s, int numRows) {
        string res;
        if (numRows == 1) return s;
        for (int j = 0; j < numRows; j ++ )
        {
            if (j == 0 || j == numRows - 1)
            {
                for (int i = j; i < s.size(); i += (numRows-1) * 2)
                    res += s[i];
            }
            else
            {
                for (int k = j, i = numRows * 2 - 1 - j - 1;
                        i < s.size() || k < s.size();
                        i += (numRows - 1) * 2, k += (numRows - 1) * 2)
                {
                    if (k < s.size()) res += s[k];
                    if (i < s.size()) res += s[i];
                }
            }
        }
        return res;
    }
};