LeetCode-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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zigzag-conversion
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

审题：

将字符串按照z字型排列，然后再按照一列一列的方式组合起来。构成一个新的数组。

思考：

方法1，可以通过确定每个字母再每列的位置，最后将三列字母组合起来。

如果是三列，159第一列，2468第二列，3，7，11第三列。但是四列五列不好处理，不可取。

方法2

解题：

方法一：

我们可以使用min(numRows,len(s)) 个列表来表示 Z 字形图案中的非空行。

从左到右迭代 ss，将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。

只有当我们向上移动到最上面的行或向下移动到最下面的行时，当前方向才会发生改变。

	public String convert(String s, int numRows) {
		// 如果只排一行，输入和输出相同
		if (numRows == 1)
			return s;
		//
		List<StringBuilder> rows = new ArrayList<StringBuilder>();
		// min() 方法用于返回两个参数中的最小值。我们可以使用Math.min(numRows, s.length())个列表来表示 Z 字形图案中的非空行。
		for (int i = 0; i < Math.min(numRows, s.length()); i++) {
			rows.add(new StringBuilder());
		}
		int curRow = 0;
		boolean goingDown = false;
         //curRow的值就是0，1，2，1，0，2在变换。保证下来到最低或者最顶端行能够变换方向。
		for (char c : s.toCharArray()) {
			rows.get(curRow).append(c);
			if (curRow == 0 || curRow == numRows - 1)
				goingDown = !goingDown;
			curRow += goingDown ? 1 : -1;
		}

		StringBuilder ret = new StringBuilder();
		for (StringBuilder row : rows)
			ret.append(row);
		return ret.toString();
	}

方法一：按行访问

按照与逐行读取 Z 字形图案相同的顺序访问字符串。

首先访问 行 0 中的所有字符，接着访问 行 1，然后 行 2，依此类推...

对于所有整数 k，

行 0中的字符位于索引 k(2⋅numRows−2) 处;
行numRows−1 中的字符位于索引 k(2⋅numRows−2)+numRows−1 处;
内部的 行 i 中的字符位于索引 k(2⋅numRows−2)+i 以及(k+1)(2⋅numRows−2)−i 处;

	public String convertI(String s, int numRows) {
        //如果长度为1返回本身。
		if (numRows == 1)
			return s;
		StringBuilder ret = new StringBuilder();
		int n = s.length();
		//这个值是每行前一个值和下一个值的下标距离，是二倍的numRows减去最顶一行和最底一行。
		int cycleLen = 2 * numRows - 2;
        //从第一行开始遍历，
		for (int i = 0; i < numRows; i++) {
			//每行的第一个值就是行下标，第二个值就是加上cycleLen
			for (int j = 0; j + i < n; j += cycleLen) {
				//将值直接接到后边。
				ret.append(s.charAt(j + i));
				//因为这下边判断是是否是第一行或者最后一行，中间的行的字母要比上下两行多。
				//因为一个V循环，从下到下，再到上去。中间这个字母会出现两次。
				if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
					ret.append(s.charAt(j + cycleLen - i));
			}
		}
		return ret.toString();
	}