6. Z 字形变换（中等）

• 难度: 中等
• 考察: 数组
• 来源: https://leetcode-cn.com/problems/zigzag-conversion/
• 题解: https://github.com/MisterBooo/LeetCodeAnimation/blob/master/0006-ZigZag%20Conversion/Article/0006-ZigZag%20Conversion.md

题目

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 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"
解释:
L   C   I   R
E T O E S I I G
E   D   H   N

示例2:

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

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

思路

这道题是一道模拟题，题目的要求就是答案，我们只需要读懂题意就很容易实现。

我们最终要输出的是以蛇形摆放之后的字符串再按行串联在一起之后的结果，也就是说每一个字母摆放的列并不重要，重要的是摆放的行号。我们可以很容易想到通过数组维护每一行当中摆放的字母，最后将每一行的结果串联即可。所以问题就只剩下了，我们如何知道每一个字母应该摆放在哪一行？

其实这也是有规律的，我们通过观察样例可以发现，我们每一个字母摆放的行号先是从0递增到n-1，再从n-1递减到0。我们就模拟这个过程，一个字符一个字符的放置即可。

比如字符串是“PAYPALISHIRING ”，rowNum=4。我们可以创建四个空串：

“” “” “” “”

然后我们按照蛇形一个字母一个字母地放进这些空串当中：

当放了第一个字母p之后，变成：

“p” “” “” “”

接着放第二个：

“p” “a” “” “”

接着第三个：

“p” “a” “y” “”

当我们把所有字母都放完了之后，可以得到这样的四个串：

“PIN” “ALSIG” “YAHR” “PI”

然后把这四串拼接在一起就行了。

关键点

• 读懂题意

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(N)

代码

func convert(s string, numRows int) string {
	if s == "" || numRows <= 1 {
		return s
	}
	result := make([][]byte, numRows)

	i := 0
	turnUp := true
	for j := 0; j < len(s); j++ {
		result[i] = append(result[i], s[j])
		if i == numRows-1 {
			turnUp = false
		}
		if i == 0 {
			turnUp = true
		}
		if turnUp {
			i++
		} else {
			i--
		}
	}

	var b strings.Builder
	b.Grow(len(s))
	for _, s := range result {
		b.WriteString(string(s))
	}
	return b.String()
}