康瑞部落

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".

解题思路：

1、一般这种矩形的变换，直接想到的办法是按照它的规则模拟一遍即可。下面是相关代码，其时间复杂度和空间复杂度均为O(n*nRows)

class Solution {
public:
    string convert(string s, int nRows) {
        if(nRows<2){
            return s;
        }
        int len=s.length();
        char matrix[nRows][len];
        for(int i=0; i<nRows; i++){
            for(int j=0; j<len; j++){
                matrix[i][j]=0;
            }
        }
        int colum=0;    //当前放到了第colum列
        int row = 0;    //当前放到了第row行
        bool down = true;   //向下还是向上走
        for(int i=0; i<len; i++){
            matrix[row][colum]=s[i];
            if(down){
                row++;
                if(row==nRows){
                    row=row-2;
                    colum++;
                    down=false;
                }
            }else{
                row--;
                colum++;
                if(row<0){
                    row=1;
                    colum--;
                    down=true;
                }
            }
        }
        string result="";
        for(int i=0; i<nRows; i++){
            for(int j=0; j<len; j++){
                if(matrix[i][j]!=0){
                    result+=matrix[i][j];
                }
            }
        }
        return result;
    }
};

2、看来我发现规律的能力有些欠缺。其实每一竖一提的字符个数为2*nRows-2，其中-2是第一层和最后一层只有一个元素。对于非第一行和非最后一行，元素在s中的下标为j+2*nRows-2-2*i，其中i是当前行，j是当前列。下面是代码。时间复杂度为O(n*nRows)，空间复杂度为O(1)。

class Solution {
public:
    string convert(string s, int nRows) {
        if(nRows<2){
            return s;
        }
        int len=s.length();
        int step = 2*nRows-2;
        string result="";
        for(int i=0; i<nRows; i++){
            for(int j=i; j<len; j=j+step){
                result += s[j];
                if(i!=0 && i!=nRows-1 && j+step-2*i<len){   //除了第一行和最后一行，两列之间都有一个字符，其下标为j+step-2*i
                    result += s[j+step-2*i];
                }
            }
        }
        return result;
    }
};

二次刷题（2015-07-28）：

n行，主列相邻的两个下标相距2*（numRows - 1）。除了第0行和第n-1行，每两个主列之间有且仅有一个元素，该元素的下标为前一个主列下标+2*（n- i - 1）。

比如：

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

共有4行，0到6下标相距2*(4-1)=6,1到7下标相距2*(4-1)=6,等等。1到5下标相距2*(4-1-1)=4，2到4下标相距2*(4-2-1)=2,等等。

知道这个规律，我们就能很容易得到下面的代码：

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