6. ZigZag Conversion

锯齿形转换

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"

词义分析：首先一定得弄清楚zigzag是“之字形”的意思，“之字形”是“锯齿形”的意思，可以脑补一下锯齿形的画面，实在想不出可以看下图，因为这个词一定得弄清楚不然会影响你的理解，甚至会直接引导你到错误的方向。

大致意思：给定连续几行的字符串以锯齿形的形式排列显示，编写代码实现将按照锯齿形顺序排列的字符转换成按照一行接一行的字符顺序显示，就是将示例中的

锯齿形顺序的”PAYPALISHIRING“转换成行读顺序的”PAHNAPLSIIGYIR“。

常规解法：以一个正常的思路来思考这个问题，大多数人都会采用一个比较通俗易懂的方法来解决，就是将锯齿形顺序排列的字符依次存入一个二维数组中，然后按照正常遍历的顺序也就是题目中的一行接一行的顺序遍历显示出来即可。

class Solution {
public:
    string convert(string s, int numRows) {
        char tb[1000][1000]={NULL};
        int len=s.length();
        if(numRows==1)
            return "";
        if(numRows==1)
            return s;
        int z=ceil((double)(len+numRows-2)/(2*(numRows-1)));
        int col=0;
        int flag=0;
        for(int i=0;i<z && flag<=len;++i)
        {
            int row=0;
            while(row<numRows && flag<=len)
            {
                tb[row++][col]=s[flag++];
            }
            --row;
            for(int ct=0;ct<numRows-2 && flag<=len;++ct)
            {
                tb[--row][++col]=s[flag++];
            }
            ++col;
        }
        string ot;
        int lie=z+(numRows-2)*(z-1);
        for(int i=0;i<numRows;++i)
        {
            for(int j=0;j<lie;++j)
            {
                if(tb[i][j]!=NULL)
                ot.append(1,tb[i][j]);
            }
        }
        return ot;
    }
};

代码解释：首先开辟了一个很大的二维数组，因为题目没要求字符串的长度限制，所以一般不会特别大。思路是：先算出以锯齿形排列的主干列数(完整的列)，也就是最高的行列数，从二维数组的左上角开始：1.从上到下依次填满字符；2.然后再沿对角线的方向依次填满字符；不断重复这两个操作直到将字符串中的字符按照锯齿形填完为止。整个过程要注意行标和列标的变化。最后遍历输出即可。

其他解法：两个完整的列，如示例中的“PAY”和“ALI”之间会有1个字符，也就是（numRows-2）个字符，这样整个字符串就划分成了很多个numRows+numRows-2个字符串，当然尾部不一定满足，这样第一行和最后一行就可以以此为间隔依次取原字符串中字符生成，中间的行需要加上锯齿形中间的字符。到这里大家会发现其实就是下标计算的问题，注意不要越界就行。

class Solution {
public:
   string convert(string s, int numRows) {
       if(numRows <= 0) return "";
       if(numRows == 1) return s;
       string rst = "";
       int sz = s.size();
       for(int i=0; i<numRows; ++i) {
           int idx = i;
           while(idx < sz) {
               rst += s[idx];
               if(i!=0 && i!=numRows-1) {
                   idx += (numRows-1-i)*2;
                   if(idx >= sz) break;
                   else rst += s[idx];
                   idx += i*2;
               }
               else idx += (2*numRows-2);
           }
       }
       return rst;
   }
};