如有错误，感谢不吝赐教、交流
leetcode6

题目描述

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

构建矩阵法解决

已知字符串s，长度为n，行数为numRows。
特殊情况：
当numRows >= n的时候，即只有一列的情况，或者numRows=1，即只有一行的情况，直接输出s。
剩下情况：创建矩阵存储，再遍历矩阵即可获得返回s。
根据题意，先向下写numRows个，然后再右上写numRows-2个

如图所示，因此在变换过程中可以理解为一个周期大小是t =numRows + numRows - 2，然后每个周期占用numRows - 1列，因此有( n / t ) + 1个周期，向上取整，乘上每个周期的列数（( n / t ) + 1）* （numRows - 1）
于是，创建一个numRows行，（( n / t ) + 1）* （numRows - 1）列的矩阵，然后遍历s，按照Z字形填写到矩阵中。具体：设当前填写的位置为 (x,y)，即矩阵的 x 行 y 列。初始
(x,y)=(0,0)，即矩阵左上角。若当前字符下标i满足i mod t<numRows - 1，则向下移动，否则向右上移动。矩阵填写完成后，逐行扫描，将不为空的字符拼接，得到答案。

如图所示：

代码实现

public String convert(String s, int numRows) {int s_length = s.length();if (numRows == 1 || numRows >= s_length) {return s;}// 构建矩阵的方法存入字符，然后再按行取出int one_t = numRows + numRows - 2;  // 一个周期的字符数量int t = s_length / one_t + 1;  // 周期数量，向上取整int one_t_columns = numRows - 1;  // 1 + numRows - 2  一个周期有多少列int c = t * one_t_columns;  // 总列数// 构建二维矩阵int [][] char_matrix = new int[numRows][c];// 开始将s插入到矩阵中int x = 0, y = 0;  // 初始坐标为0，0for (int i = 0; i < s_length; i++) {char_matrix[x][y] = s.charAt(i);// 这个条件表明是在往下竖着走的列，if (i % one_t < numRows - 1) {x++;} else {y++;x--;}}StringBuilder sb = new StringBuilder();for (int i = 0; i < numRows; i++) {for (int j = 0; j <c; j++) {if (char_matrix[i][j] != 0) {sb.append((char)char_matrix[i][j]);}}}return sb.toString();}

方法二：构建列表存储

在方法一种，矩阵很多空间都是浪费的，可以进行优化。
对于如图：

可以构建三个列表进行存储，具体如下

用三个列表存储，减少浪费空间。
存储规则：
1、向下走到底，触底反弹；
2、反弹后，向上走到顶，触顶反弹；
3、直到遍历完字符串s的所有字符。
具体看代码，很清晰的。

代码实现

public String convert(String s, int numRows) {int s_length = s.length();String res = "";if (numRows == 1 || numRows >= s_length) {return s;}ArrayList<StringBuilder> a_sb = new ArrayList<>();for (int i = 0; i < numRows; i++) {a_sb.add(new StringBuilder());}int index = 0;boolean flag = true;for (int i = 0; i < s_length; i++) {a_sb.get(index).append(s.charAt(i));if (flag) {index++;// 向下走到底，回头flag == falseif (index == numRows) {flag= false;  // 触底反弹index = numRows - 2;}} else {index--;if (index == -1) {flag= true;  // 触顶反弹index = index + 2;}}}for (int i = 0; i < numRows; i++) {res += a_sb.get(i).toString();}return res;}

ps:计划每日更新一篇博客，今日2023-04-21，日更第五天，昨日更新：leetcode3无重复字符的最长子串