题目: Z 字形变换

分析

矩阵法

Z字形变换

将字符串转为Z字型本质上是一个二维矩阵，所以可以按照规则将该矩阵构造出来，之后逐行从左到右输出即可。

构造一个矩阵，矩阵可以通过计算行数和列数精确构造，也可以直接构造一个较大的矩阵，最终空白数据不影响最后的数据展示，但是会影响空间复杂度。

矩阵的行数已经给出，从图中的Z字型的形状可以看出，去掉Z字型最下面横线的斜钩形状构成了一组循环，该循环的字符个数一共是2*numRows-2。从而通过该循环可以计算出循环的次数为len(s)/2*numRows-2,而每组循环的宽度即列数为len(s)/2*numRows-2，通过计算该值可以得处最终二维矩阵的列数。

len(s)%2*numRows-2的余数部分需要额外处理，余数部分可能还有（0～numRows-1）列。

构造矩阵的过程需要遍历该字符串，而计算该字符串的位置，计算方式分为下列几种：

当上一个字符在Z字型的第一个竖线的时候，同时上一个字符的行值小于numRows-1时候，行值+1，列值不变。

当上一个字符在Z字型的第一个竖线的时候，同时上一个字符的行值等numRows-1时候，此时行值-1，列值+1，进入Z字型中间的斜线部分。

当上一个字符在Z字型中间的斜线的时候，同时上一个字符的行值不等于1的时候，每次遍历一个字符，则行值-1，列值+1。

当上一个字符在Z字型中间的斜线的时候，同时上一个字符的行值等于1的时候，则行值-1，列值+1。进入Z字型的最右侧的竖线，也可以作为一轮新的循环，也就是作为Z 字型的第一个竖线。

矩阵构造完成之后，从左到右输出即可。

采用矩阵进行构造的时间复杂度是O（n），

空间复杂因为需要转为矩阵进行存储，所以空间复杂度是O（n²）。

位置法

矩阵法可以进行如下优化。

因为最终的目标结果只需要按行输出，所以不需要关注准确的列值。

在计算过程中存储每一行的值即可，不需要构造完整的矩阵。

计算方式同样需要遍历所有的字符，但是每次只需要计算该数字放入的行号即可，具体方式也是按照2*numRows-2一轮循环的方式进行计算。

固定周期的循环可以用双层循环来实现，也可以用数学的取余操作完成循环。

每轮循环的钱numRow个值，从0开始每次的行数会进行加一操作，之后的numRow-2个元素会依次存入的行数会依此减一，直到行数变为1位置。

计算法的空间占用较矩阵法类似，因为需要声明numRow个数组用来存放每一行的字符。

遍历完成，将行依此输出即可。

时间复杂度是O（n），

空间复杂度也是O（n）。

题解

class Solution {
    public String convert(String s, int numRows) {
        if(numRows < 2) return s;
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());
        int i = 0, flag = -1;
        for(char c : s.toCharArray()) {
            rows.get(i).append(c);
            if(i == 0 || i == numRows -1) flag = - flag;
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : rows) res.append(row);
        return res.toString();
    }
}