Leetcode 6. Z 字形变换

题干

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

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

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

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

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

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

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

• 1 <= s.length <= 1000

• s 由英文字母（小写和大写）、',' 和 '.' 组成

• 1 <= numRows <= 1000

初见

直接模拟 。

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        int numColumns = (int) (s.length() * (numRows - 1.0) / (numRows * 2.0 - 2.0)) + 1;
        char[][] map = new char[numRows][numColumns];
        int currentRow = 0, currentColumn = 0;
        boolean downFlag = true;
        for (int i = 0; i < s.length(); i++) {
            map[currentRow][currentColumn] = s.charAt(i);
            if (downFlag) {
                currentRow++;
                if (currentRow == numRows - 1) {
                    downFlag = false;
                }
            } else {
                currentRow--;
                currentColumn++;
                if (currentRow == 0) {
                    downFlag = true;
                }
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numColumns; j++) {
                if (map[i][j] != '\u0000') {
                    stringBuilder.append(map[i][j]);
                }
            }
        }
        return stringBuilder.toString();
    }
}

优化

解法一

对于每一行，行内的相对顺序在最终字符串中是一致的。当移动到某一行时，在这一行末尾直接添加即可。

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        List<List<Character>> list = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            list.add(new ArrayList<>());
        }
        int currentRow = 0;
        boolean downFlag = true;
        for (int i = 0; i < s.length(); i++) {
            list.get(currentRow).add(s.charAt(i));
            if (downFlag) {
                currentRow++;
                if (currentRow == numRows - 1) {
                    downFlag = false;
                }
            } else {
                currentRow--;
                if (currentRow == 0) {
                    downFlag = true;
                }
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            for (Character c : list.get(i)) {
                stringBuilder.append(c);
            }
        }
        return stringBuilder.toString();
    }
}

解法二

根据推导公式直接构造字符串。字符的位置具有周期性 T = 2r - 2，对于矩阵第一行的非空字符，其对应的 index 均为 T 的倍数，即 index == 0 (mod t)；对于矩阵最后一行的非空字符，满足 index == r − 1 (mod t)。对于矩阵的其余行（行号设为 i），每个周期内有两个字符，第一个字符满足 index == i (mod t)，第二个字符满足 index == t − i (mod t)。

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1 || numRows >= s.length()) {
            return s;
        }
        StringBuilder stringBuilder = new StringBuilder();
        int term = numRows * 2 - 2;
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; i + j < s.length(); j += term) {
                stringBuilder.append(s.charAt(i + j));
                if (i > 0 && i < numRows - 1 && j + term - i < s.length()) {
                    stringBuilder.append(s.charAt(j + term - i));
                }
            }
        }
        return stringBuilder.toString();
    }
}