ZigZag Converesion 之字型转换字符串

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 text, int nRows); convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

刚开始看了很久这个问题，不明白是怎么变的。我在网上查了一些资料，终于明白了，就是把字符串放成一个字形，参考网络。

例如，有一个字符串 “0123456789ABCDEF”转为zigzag

当 n = 2 时：

0 2 4 6 8 A C E

1 3 5 7 9 B D F

当 n = 3 时：

0…..4…..8…..C

1 3 5 7 9 B D F

2…..6…. A…..E

当 n = 4 时：

0……6……C

1… 5 7…B D

2 4…8 A…E

3…… 9…… F

我们发现，除了第一行和最后一行之间没有形成的字形数字外，还有其他数字，而第一行中相邻两个元素的index之间的差异与行数有关 2*nRows - 2, 根据这一特点，我们可以找到元字符串中所有黑色元素的位置，并将其添加到新字符串中。红色元素的位置也是有规律的，每个红色元素的位置都是 j + 2*nRows-2 - 2*i, 其中，j是前一个黑色元素的列数，i是当前行数。 比如当n = 4中的红5，它的位置是 1 + 2*4-2 - 2*1 = 5.是原字符串的正确位置。当我们知道所有黑色元素和红色元素位置的正确算法时，我们可以按顺序将它们添加到新字符串中。代码如下：

class Solution {public:    string convert(string s, int nRows) {        if (nRows <= 1) return s;        string res = "";        int size = 2 * nRows - 2;        for (int i = 0; i < nRows; ++i) {            for (int j = i; j < s.size(); j += size) {                res += s[j];                int tmp = j + size - 2 * i;                if (i != 0 && i != 0 && i != nRows - 1 && tmp < s.size()) res += s[tmp];            }        }        return res;    }};