每日算法题：Z字形变换算法实现

问题描述

给定一个字符串，将其按Z字形排列，并按行从左到右，再从右到左交替输出。例如，输入字符串为 "LEETCODEISHIRING"，排列成下图所示的样子后输出 "LCIRETOESIIGEDHN"。

L   C   I   R
E T O E S I I G
E   D   H   N

算法步骤

1. 创建一个二维数组；
2. 遍历字符串；
3. 计算每个字符对应的坐标；
4. 将字符填入对应的坐标；
5. 从上到下，从左到右，从右到左遍历二维数组，将每个字符拼接起来。

实现思路

A. 创建一个二维数组

定义一个二维数组zigzag，行数为输入字符串的行数，列数为输入字符串的长度。

char[][] zigzag = new char[numRows][s.length()];

B. 遍历字符串

遍历输入字符串s的每个字符。

C. 计算每个字符对应的坐标

计算每个字符对应的行列坐标。当以Z字形排列时，每一行的字符排列存在一定的规律：

第0行排列：0   6    12
第1行排列：1 5 7  11 13
第2行排列：2 4 8 10  14
第3行排列：3   9    15

当下标i处于0~numRows-1时，表示处于Z字形的上升部分。对应的列坐标可以直接计算出来为i。当下标处于numRows~2*numRows-2时，表示处于Z字形的下降部分。对应的列坐标可以计算出来为(numRows-1)-(i-(numRows-1))。

int row = 0, col = 0;
for (int i = 0; i < s.length(); i++) {
    zigzag[row][col] = s.charAt(i);
    if (row == 0) {
        col++;
    } else if (row == numRows - 1) {
        col++;
        row--;
    } else {
        col++;
        row--;
    }
}

D. 将字符填入对应的坐标

将每个字符填入计算出来的对应坐标。

for (int i = 0; i < numRows; i++) {
    for (int j = 0; j < s.length(); j++) {
        if (zigzag[i][j] != 0) {
            result.append(zigzag[i][j]);
        }
    }
}

代码实现

完整的代码实现如下：

public String convert(String s, int numRows) {
    if (numRows == 1) {
        return s;
    }
    char[][] zigzag = new char[numRows][s.length()];
    int row = 0, col = 0;
    // 遍历字符串，计算每个字符所处的位置
    for (int i = 0; i < s.length(); i++) {
        zigzag[row][col] = s.charAt(i);
        if (row == 0) {
            col++;
        } else if (row == numRows - 1) {
            col++;
            row--;
        } else {
            col++;
            row--;
        }
    }
    StringBuilder result = new StringBuilder();
    // 从上到下，从左到右，从右到左遍历二维数组，将每个字符拼接起来
    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < s.length(); j++) {
            if (zigzag[i][j] != 0) {
                result.append(zigzag[i][j]);
            }
        }
    }
    return result.toString();
}

时间复杂度分析

时间复杂度为$O(n)$，其中$n$为输入字符串的长度。

空间复杂度分析

空间复杂度为$O(n)$，需要存储一个二维数组，数组大小为$numRows \times n$。

优化思路

遍历一次字符串，计算每个字符对应的位置，然后遍历一次数组，按顺序将每个位置上的字符加入结果中。对于长度为$n$的字符串，时间复杂度为$O(n)$。原理上无法得到更快的算法，但是可以通过一些优化方法降低时间复杂度。

扩展点

A. 处理非字母字符

如果输入字符串不仅仅包含字母，还包含其他字符（例如空格、数字等），那么需要对算法进行修改。可以将取值范围限定在字母范围内，当遍历到非字母字符时直接跳过。

B. Z字形变换的逆过程

Z字形变换的逆过程是将排列好的字符串重新排列成原来的字符串。这个过程可以按照原来的方法，计算每个字符在原来字符串中对应的位置，然后按照顺序添加到结果字符串中即可。

总结

本文介绍了Z字形变换算法的实现过程。该算法是一种基于规律的算法，通过计算每个字符对应的行列坐标，然后按照行列坐标填充二维数组。最后，按照约定的顺序从二维数组中取出字符，即可得到排列好的字符串。