LeetCode 006 ZigZag Conversion 解题报告

2015-04-09

问题描述：
给定一个字符串，用Zigzag Pattern模式书写，具体什么是Zigzag Pattern参考维基百科就是按照Z形状写的，现在要求按照正常的顺序读出来。

下面是英文题目描述。
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)
格式如下:

1
2
3

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

要求输出正常的顺序：”PAHNAPLSIIGYIR“

还是老规矩，不想听我废话解释，就直接看代码：

string Solution006::convert(string s, int nRows)
{
    if(nRows < 2)
        return s;
    string result = "";
    for(int row = 0;row < nRows; ++ row)
    {
        if(row == 0|| row == nRows -1)
        {
            int step = nRows + nRows - 2;
            int i=row;
            while(i < s.length())
            {
                result += s[i];
                i += step;
            }
        }
        else
        {
            int i = row;
            int midstepodd = (nRows - 1 - row) * 2;
            int midstepeven = row * 2;
            int col = 1;
            while(i < s.length())
            {
                result += s[i];
                if(col & 0x1)
                    i += midstepodd;
                else
                    i += midstepeven;
                col ++;
            }
        }
    }
    return result;
}

唠叨一下

这种字符排血很容易可以找到规律，找到字符下标的v，逐行读取字符就可以了。
分两种情况：

第一行和最后一行，这两行比较好判断，因为相邻的两垂直列之间没有斜着排列的字符，所以，相邻两垂直列之间的字符是固定的，而且比较容易计算出来：step = nRows + nRows - 2；
中间行，比较讨厌的是中间行相邻的列之间有一个斜着排列的字符，其实，没有去除斜着排列的一列，中间行两垂直列之间的间隔也是固定的，而且跟第一种情况一样，但是既然有了中间这个斜着排列的一列，相当于两个垂直之间添加了一个字符，这个字符的下标也有规律，这个字符的下标将第一种情况的Step分成了两部分，其中前一部分是midstepodd = (nRows - 1 - row) * 2，后一部分是midstepeven = row * 2，两部分在相邻两垂直列之间是交替的，且它们的和是第一种情况的Step。

根据行号分为两种情况，写代码也就轻松了，运行时间也算是比较可以了，26ms。

参考

CSDN博客