一、Z字形变换
难度：中等
题目传送门：Z字形变换
题目
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行Z 字形排列。
比如输入字符串为 “PAYPALISHIRING”行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。
示例 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"
提示：
- 1 <= numRows <= 1000
- 1 <= s.length <= 1000
- s 由英文字母（小写和大写）、’,’ 和 ‘.’ 组成
思路
Z字形变换后，可以视为多个三角形组成，每个三角形两条实线边：竖边和一条对角线。为了规律的按照三角形划分，三角形最右边的顶点划给下一个三角形。
则图形大致如下所示：
1 * * *
1 * 1 *
1 1 * *
1 * * *
所以一个三角形需要字符数量为：2 * 行数 - 2 （式-1）. 每行需要一个字符，所以下文中提到行数或者行，数值上等同于numRows。
题目需要变换后的顺序，则变换思路：求每个字符对应变换后的字符串的位置。
按行设计思路，位置有两种：
- 首尾两行：每一行只有一个元素
- 中间的行：第一个元素在第一列，第二个元素在中间。
那么首行元素的下标 = 横着数过来三角形所需要的元素个数；
根据（式-1）得：
首行元素的下标 =三角形的个数 * 一个三角形所需要的元素个数（式-2）
同理得，尾行下标 = 横着数过来三角形所需要的元素个数 + 行的下标。
（数组下标从0开始，长度从1开始，要注意区分）
中间的行分两种：
- 第一个元素下标 = 横着数过来三角形所需要的元素个数 + 行的下标。
- 中间元素的下标 = 横着数过来三角形所需要的元素个数 + 总行数 + (位于当前行下面的行数) = 横着数过来三角形所需要的元素个数 + 总行数 + (总行数 - 当前行的下标 - 2)
其中-2为：末尾行 -1 ，下标和长度的差值-1。
到此所有情况下标都就绪可，接下来处理越界情况。按照上文推理，只要元素存在于需要变换的原始字符中，则必然在结果列表中。
所以只需要判断计算出来的元素在原始字符串中是否存在即可。
以上是按行的思路，同理可以设计出按列计算的方式，不再展开。
代码
func convert(s string, numRows int) string {
if s == "" || len(s) <= numRows || numRows < 2 {
return s
}
// 如果是包含中文等特殊字符，需要改用rune。
// 本题干限定输入的字符大小，所以可以使用byte
sLen := len(s)
// 接下来必有一个三角形
triangleSize := numRows + (numRows - 2)
triangleN := sLen / triangleSize
if sLen%triangleSize > 0 {
triangleN++
}
result := make([]byte, sLen)
rIndex := 0
for r := 0; r < numRows; r++ {
if r == 0 || r == numRows-1 {
//首尾
for j := 0; j < triangleN; j++ {
tIndex := j*triangleSize + r
if tIndex > sLen-1 {
break
}
result[rIndex] = s[tIndex]
rIndex++
}
} else {
//中间的
for j := 0; j < triangleN; j++ {
//第一个贴边
skipEle := j * triangleSize
tIndex := skipEle + r
if tIndex > sLen-1 {
break
}
result[rIndex] = s[tIndex]
rIndex++
tIndex = skipEle + numRows + (numRows - r) - 2
if tIndex > sLen-1 {
break
}
result[rIndex] = s[tIndex]
rIndex++
}
}
}
return string(result)
}
性能
来自Leetcode, 0表示小于1个单位。
- 执行用时: 0ms
- 内存消耗: 3.7 MB