Z 字形变换

题目：

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、',' 和 '.' 组成
• 1 <= numRows <= 1000

自行解答：

string convert(string s, int numRows) {
    if(numRows == 1){
        return s;
    }
    //每一份对应多少列
    int partColum = numRows-1;
    //每一份含有的字符的长度
    int partLength = 2 *numRows-2;
    //总共多少份
    int partNum = s.length() / partLength;
    //所有的列数
    int columNum = 0;
    //整份剩下的字符长度
    int partReset = s.length() % partLength;

    if(partReset == 0){
        columNum =  partNum *partColum;
    } else if(partReset <=numRows){
        columNum =  partNum *partColum +1;
    } else {
        columNum = partNum *partColum + partReset - numRows+1;
    }
    vector< vector<string> > arrResult;
    for(int i = 0;i<numRows;i++){
        vector<string> v1;
        v1.resize(columNum);
        arrResult.push_back(v1);
    }
    int m =0;
    int n = 0;
    int numCount = 0;
    for(int i = 0;i<=partNum;i++){
        if(i!= partNum){
            numCount = partLength;
        } else{
            numCount =  partReset;
        }
        for(int count = 0;count <numCount;count++){
            arrResult[m][n] = s[i*partLength +count];
            if(count < numRows-1){
                m++;
            } else{
                m--;
                n++;
            }

        }
    }
    string result = "";
    for(int i = 0;i<numRows;i++){
        for(int j = 0;j<columNum;j++){
            if(arrResult[i][j].size() != 0){
                result += arrResult[i][j];
            }
        }
    }
    return result;
}

思路分析：

思路比较简单，按照字符串走向将字符按个记录在二维数组中，最后按行遍历取出来数组即可，具体需要借助的变量参数 即含义见上面的代码注释，但是此算法时间和空间复杂度较高，可进一步推出另外一种算法

空间复杂度：使用了二维数组存储变量，也就是arrResult大小的变量，所以空间复杂度应该为：O(numrows *columNum ) 即O（N2），占用了额外的空间

时间复杂度： 因为只遍历原数组一次，也就是O(N)

官方解答

官方 提供了2种解答，方案2是按照排列而成的字符进行位置规律进行数学计算，是自行解答的思路的进一步体现，再此不赘述，可参考官方解法2_按行访问，提供下官方的解法一，代码实现如下：

class Solution {
public:
    string convert(string s, int numRows) {

        if (numRows == 1) return s;

        vector<string> rows(min(numRows, int(s.size())));
        int curRow = 0;
        bool goingDown = false;

        for (char c : s) {
            rows[curRow] += c;
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }

        string ret;
        for (string row : rows) ret += row;
        return ret;
    }
};

思路分析：

1：遍历字符串s ，准备结果动态数组 rows，准备2个变量，

• curRow：遍历字符s的时候，当前字符按照题目要求应该所处的行的位置
• goingDown：每次遍历时，遍历的顺序是向上还是向下，根据循环的位置会进行更新

2：遍历字符s

• 将字符s的当前位置的字符c 加到对应的row对应的行中
• 更新goingDown当前结果
• 根据goingDown确认当前行 curRow的结果

3：整合结果字符，将rows按照行输出，即最终结果

复杂度分析：

时间复杂度：只遍历1次字符串，因此复杂度为 O（n）

空间复杂度：有限的变量 + 存储Z字形的数组（长度为s的长度），复杂度O（N）