一、题目原型：
将字符串 "PAYPALISHIRING" 以Z字形排列成给定的行数：
输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"
输入: s = "PAYPALISHIRING", numRows = 4
输出: "PINALSIGYAHRPI"
实现一个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);
二、题目意思剖析：
numRows = 3
P A H N
A P L S I I G
Y I R
numRows = 4
P I N
A L S I G
Y A H R
P I
三、解题思路：
3.1. 将原字符串按照“z字转换规律”保存进一个二维数组
3.2.将该二维数组横竖对调，得到最后的二维数组
3.3.用字符串拼接得到最后的答案
核心思路：找规律，找关键的几个数据和numRows、字符串总长度之间的关系。
下图中方框内表示一个单元格。
笔记思路
第一步：能够看出，这个排列是由一个个单元格(相同的排列)组成。
P I N
A L S I G
Y A H R
P I
其中，单元格是
P
A L
Y A
P
第二步：算出每一个单元所包含的字符个数
很简单可以看出，每个单元是由最长的那一列+中间的那几个字符。
而中间那些字符，刚好是除去最上面和最下面的那些。
所以：
let letterCount = numRows + (numRows - 2)
第三步：每个单元格包含的列数
1表示是行数最大那一列，(numRows - 2)是中间过渡的那几列
let cols: Int = 1 + (numRows - 2)
第四步：总共有多少个单元格
var count: Int = 0
while letterCount*count <= letters.count {
count = count + 1
}
// 因为最后count会再次累加1，所以需要减1.
count = count - 1
第五步：总共列数
// 最终列数
var allCols: Int = 0
// 余数：比如字符长度为17，17 % 6 = 5
let remainder = letters.count % letterCount
if remainder == 0 { // 说明刚好有整数个单元格
allCols = count * cols
}else if remainder >= numRows && remainder < letterCount {
//如果余数大于或者行数，并且小于一个单元格所包含的最大字符数，allCols = 前面整数个的单元格列数 + 1 + (余数 - numRows)
allCols = count * cols + 1 + (remainder - numRows)
}else {
// 比如上面的例子， PAYPALISHIRING中，结果余数 = 14%6 = 2，2 < numRows，所以allCols = 前面整数个的单元格列数 + 1
allCols = count * cols + 1
}
// 1.前二维数组
var allConvert = dim(allCols, dim(numRows, "*"))
var index: Int = 0 // 总字符串索引
for i in 0..<allCols {
// i % cols，余数 - 指的是字母离底部多长。
if i % cols == 0 { // 当余数为0时，就是最长列的时候。
var convert: [String] = Array.init(repeating: "*", count: numRows)
var j: Int = 0
while index < letterCount * (i/cols + 1) && index < letters.count && j < numRows {
convert[j] = letters[index]
allConvert[i] = convert
index = index + 1
j = j + 1
}
}else { // 其他时候，就是用（ 最大行数 - 1 - 余数 ）
var convert: [String] = Array.init(repeating: "*", count: numRows)
convert[numRows - 1 - i%cols] = letters[index]
allConvert[i] = convert
index = index + 1
}
}
print(allConvert)
这里需要一个创建二维数组的函数
// 创建二维数组
func dim<T>(_ count: Int, _ value: T) -> [T] {
return [T](repeating: value, count: count)
}
第六步：横竖置换
[["a", "b", "c", "d"],
["*", "*", "e", "*"],
["*", "f", "*", "*"],
["g", "h", "i", "j"],
["*", "*", "k", "*"],
["*", "l", "*", "*"]]
变成
[["a", "*", "*", "g", "*", "*"],
["b", "*", "f", "h", "*", "l"],
["c", "e", "*", "i", "k", "*"],
["d", "*", "*", "j", "*", "*"]]
// 将数组横转，横 -> 竖
// i[0,6) j[0,4) -> i[0,4) j[0,6)
var resultConverts = dim(numRows, dim(allCols, "*"))
for i in 0..<allCols {
for j in 0..<numRows {
resultConverts[j][i] = allConvert[i][j]
}
}
第七步：拼接最终字符串
var result: String = ""
for i in 0..<numRows {
for j in 0..<allCols {
if resultConverts[i][j] != "*" {
result.append(resultConverts[i][j])
}
}
}
print(resultConverts)
// result就是我们需要的答案
四、小结
总提交数
提交结果
有其他好的方法请极速留言，非常乐意一起探讨。😄
个人博客地址
