【算法 -- LeetCode】（06） N 字形变换

1、题目

将一个给定字符串 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：

示例 2：

输入：s = “PAYPALISHIRING”, numRows = 4
输出：“PINALSIGYAHRPI”

示例 3：

输入：s = “A”, numRows = 1
输出：“A”

题目链接：

2、图解

假若我们采用示例2的数据来进行分析，输入字符串 s 为 “LEETCODEISHIRING”， numRows 为 4 ，画成图大概长这样：

问题来了，那数组设置多大呢？自然是有多少行我们就设置多大呗，换句话说，numRows多大，我们的数组就设置多大。画成图大概就是下面这个样子：

3、Java 示例代码

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        String[] arr = new String[numRows];
        Arrays.fill(arr, "");
        char[] chars = s.toCharArray();
        int len = chars.length;
        int period = numRows * 2 - 2;
        for (int i = 0; i < len; i++) {
            int mod = i % period;
            if (mod < numRows) {
                arr[mod] += chars[i];
            } else {
                arr[period - mod] += String.valueOf(chars[i]);
            }
        }
        StringBuilder res = new StringBuilder();
        for (String ch : arr) {
            res.append(ch);
        }
        return res.toString();
    }
}

执行结果：