• 题目：6. Z字形变换(ZigZag Conversion)
• 难度：中等
• 分类：字符串
• 解决方案：字符串遍历

  <!-- more -->

今天我们学习第6题Z字形变换，这是一个字符串的中等题，像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力，因此最好能手写出该题。下面我们看看这道题的题目描述。

题目描述

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为"LEETCODEISHIRING"行数为3时，排列如下：

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

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

分析

这个题目的难度不太大，主要是对题目的理解，只有理解题目中的Z字形是如何生成后才能做出来。注意，这里的Z字形其实是将Z逆时针旋转90°后形成的，如图1所示。

题目中的示例字符串不容易看出规律，我们假设一个字符串为"ABCDEFGHIJKLMN"，然后看看是如何形成Z字形的，具体过程如图2所示。

由图2可知黑色字符表示Z字形垂直部分，红色字符表示Z字形斜右方向部分。不难看出垂直部分字符的个数为numRows，斜右方向部分子数的个数为numRows-2(除首行和最后一行以外，其余的行数个数)。理解这个形成过程后，我们只需要把这个形成过用代码实现即可。

具体java代码如下所示：

class Solution {
    public String convert(String s, int numRows) {
        // 将字符串转换为字符数组
        char[] arr = s.toCharArray();
        // 构建二维数组（这里使用的StringBuilder是Java面试时的一个考点，可以查看String、StringBuffer和StringBuilder的区别）
        StringBuilder[] sb = new StringBuilder[numRows];
        for(int i=0; i<numRows; i++){
            sb[i] = new StringBuilder();
        }
        int index = 0, len = arr.length;
        // 遍历原始数组，构建Z字形二维数组
        while(index < len){
            // 垂直添加元素
            for(int i=0; i<numRows && index < len; i++){
                sb[i].append(arr[index++]);
            }

            // 斜右向添加元素
            for(int i=numRows-2; i>=1 && index < len; i--){
                sb[i].append(arr[index++]);
            }
        }

        // 将除第0行以外的行有序拼接到第0行后面
        for(int i=1; i<numRows; i++){
            sb[0].append(sb[i]);
        }

        return sb[0].toString();
    }
}

Github地址

LeetCode-6 Z字形变换

参考链接

6.Z字形变换

更多文章请添加公众号：算法半岛（扫描上图二维码即可关注）