一、題目原型：
將字符串 "PAYPALISHIRING" 以Z字形排列成給定的行數(shù)：
輸入: s = "PAYPALISHIRING", numRows = 3
輸出: "PAHNAPLSIIGYIR"
輸入: s = "PAYPALISHIRING", numRows = 4
輸出: "PINALSIGYAHRPI"
實(shí)現(xiàn)一個將字符串進(jìn)行指定行數(shù)變換的函數(shù):
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字轉(zhuǎn)換規(guī)律”保存進(jìn)一個二維數(shù)組
3.2.將該二維數(shù)組橫豎對調(diào)，得到最后的二維數(shù)組
3.3.用字符串拼接得到最后的答案
核心思路：找規(guī)律，找關(guān)鍵的幾個數(shù)據(jù)和numRows、字符串總長度之間的關(guān)系。
下圖中方框內(nèi)表示一個單元格。
筆記思路
第一步：能夠看出，這個排列是由一個個單元格(相同的排列)組成。
P I N
A L S I G
Y A H R
P I
其中，單元格是
P
A L
Y A
P
第二步：算出每一個單元所包含的字符個數(shù)
很簡單可以看出，每個單元是由最長的那一列+中間的那幾個字符。
而中間那些字符，剛好是除去最上面和最下面的那些。
所以：
let letterCount = numRows + (numRows - 2)
第三步：每個單元格包含的列數(shù)
1表示是行數(shù)最大那一列，(numRows - 2)是中間過渡的那幾列
let cols: Int = 1 + (numRows - 2)
第四步：總共有多少個單元格
var count: Int = 0
while letterCount*count <= letters.count {
count = count + 1
}
// 因?yàn)樽詈骳ount會再次累加1，所以需要減1.
count = count - 1
第五步：總共列數(shù)
// 最終列數(shù)
var allCols: Int = 0
// 余數(shù)：比如字符長度為17，17 % 6 = 5
let remainder = letters.count % letterCount
if remainder == 0 { // 說明剛好有整數(shù)個單元格
allCols = count * cols
}else if remainder >= numRows && remainder < letterCount {
//如果余數(shù)大于或者行數(shù)，并且小于一個單元格所包含的最大字符數(shù)，allCols = 前面整數(shù)個的單元格列數(shù) + 1 + (余數(shù) - numRows)
allCols = count * cols + 1 + (remainder - numRows)
}else {
// 比如上面的例子， PAYPALISHIRING中，結(jié)果余數(shù) = 14%6 = 2，2 < numRows，所以allCols = 前面整數(shù)個的單元格列數(shù) + 1
allCols = count * cols + 1
}
// 1.前二維數(shù)組
var allConvert = dim(allCols, dim(numRows, "*"))
var index: Int = 0 // 總字符串索引
for i in 0..<allCols {
// i % cols，余數(shù) - 指的是字母離底部多長。
if i % cols == 0 { // 當(dāng)余數(shù)為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 { // 其他時候，就是用（ 最大行數(shù) - 1 - 余數(shù) ）
var convert: [String] = Array.init(repeating: "*", count: numRows)
convert[numRows - 1 - i%cols] = letters[index]
allConvert[i] = convert
index = index + 1
}
}
print(allConvert)
這里需要一個創(chuàng)建二維數(shù)組的函數(shù)
// 創(chuàng)建二維數(shù)組
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", "*", "*"]]
// 將數(shù)組橫轉(zhuǎn)，橫 -> 豎
// 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就是我們需要的答案
四、小結(jié)
總提交數(shù)
提交結(jié)果
有其他好的方法請極速留言，非常樂意一起探討。??
個人博客地址
