Z 字形变换

题目链接

Z 字形变换

题目描述

注意点

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

解答思路

方法一是模拟整个Z字形变换思路，使用一个二维数组存储变换后的矩阵，首先需要确定这个矩阵的行数row和列数col，可以找到规律：
- row为字符串长度和numRows中的最小值
- col可以由此推出：对于任意numRows，可以将Z字形左侧和中间分为一组，如下图红线所示，每组的字符数量为(numRows - 1) * 2，可以看到，最终变换的图形是由多个|/组成，计算|/的数量以及剩余字符填充的列数就可推出col
- 找到二维矩阵的row和col后，就可以模拟Z字形变换往矩阵中填充字符，过程为：当划到最后一行时，往右上划动；当划到第一行时，往下划动，以此类推即可
方法二也是模拟整个Z字形变换思路，因为本题每一行每个字符中间并不需要添加空格，所以不需要确定col。每一行只使用一个StringBuilder进行存储，所以整个结果需要用大小为numRows的StringBuilder数组进行存储。整个模拟过程只需要一个flag区分两个步骤，一个是从第一行到第numRows行，另一个是从第numRows行到第一行，不断将s中的字符添加到StringBuilder[rowIdx]即可

代码

方法一：

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        StringBuilder res = new StringBuilder();
        int n = s.length();
        int row = Math.min(n, numRows);
        int divide = n / ((numRows - 1) * 2);
        int remainder = n % ((numRows - 1) * 2);
        int col = divide * (numRows - 1) + (remainder <= numRows ? 1 : (remainder - numRows + 1));
        char[][] arr = new char[row][col];
        // 是否是Z字形左侧
        boolean isLeft = true;
        int currRow = 0;
        int currCol = 0;
        for (int i = 0; i < n; i++) {
            arr[currRow][currCol] = s.charAt(i);
            // Z字形左侧已写完
            if (currRow == numRows - 1) {
                isLeft = false;
            }
            if (currRow == 0) {
                isLeft = true;
            }
            if (isLeft) {
                currRow++;
            }
            if (!isLeft) {
                currRow--;
                currCol++;
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (arr[i][j] != '\u0000') {
                    res.append(arr[i][j]);
                }
            }
        }
        return res.toString();
    }
}

方法二：

class Solution {
    public String convert(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }
        StringBuilder res = new StringBuilder();
        StringBuilder[] arr = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            arr[i] = new StringBuilder();
        }
        // flag标记行索引增大或缩小
        boolean flag = false;
        int rowIdx = 0;
        for (char c : s.toCharArray()) {
            arr[rowIdx].append(c);
            if (rowIdx == 0 || rowIdx == numRows - 1) {
                flag = !flag;
            }
            rowIdx += flag ? 1 : -1;
        }
        for (StringBuilder sb : arr) {
            res.append(sb);
        }
        return res.toString();
    }
}