一、题目
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 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
二、解题
根据题目可以看出，文字的排列顺序是倒过来的Z字母（实际就是N形）。
方法一：
我们可以创建numRows字符串，然后遍历字符串，沿着排列顺序处理，先从上往下走（P→A→Y），当到达指定行数后，反转方向，从下往上走（Y→P→A），当到达第0行时再反转方向，如此反复。当到达一个行，将该行的字符串内添加一个字符，这样得到numRows个字符串，将这些字符串拼接，最终得到结果。该算法使用了一个for循环，所以时间复杂度为O(n),使用了数组保存临时的字符串，空间复杂度为O(n)。
方法二:
按行访问，先访第0行的所有字符，再访问第1行所有字符，依次访问到第row行。（下面的k是从0递增至下面索引小于s.count的整数。）
第0行：字符所在的索引在 k * (2 * numRows - 2)
第numRows-1行：字符所在索引在k * (2 * numRows - 2)+ numRows - 1
内部的行i (0 < i < numRows-1):字符所在的索引在k * (2 * numRows - 2) + i 和 (k + 1)(2*numRows - 2) - i 两个位置。
//如示例一中，
第0行的索引为: 0 4 8 12
第1行的索引为: 1 3 5 7 9
第2行的索引为: 2 6 10
虽然使用了两个for循环，但整理的循环次数是n，所以时间复杂度依然是O(n),因为没有使用到数组，所以空间复杂度为O(n).
虽然看上去好像方法二更好些，但是在实际使用中由于swift操作字符串比较消耗性能，所以还是方法一消耗的时间短效率更高些。
三、代码实现
方法一：时间复杂度O(n),空间复杂度O(n)
class Solution {
func convert(_ s: String, _ numRows: Int) -> String {
if numRows <= 1 {
return s
}
var strs:[String] = []
for _ in 0..<numRows {
strs.append("")
}
var row = 0
var isAsc = true
for character in s {
strs[row].append(character)
row += isAsc ? 1 : -1
if row == numRows - 1 || row == 0 {
isAsc = !isAsc
}
}
return strs.joined()
}
}
方法二：时间复杂度O(n),空间复杂度O(1)
class Solution {
func convert(_ s: String, _ numRows: Int) -> String {
if numRows <= 1 {
return s
}
var ret = ""
let cycleLen = 2 * numRows - 2
let n = s.count
let strs = Array(s)
for i in 0..<numRows {
for j in stride(from: 0, to: n, by: cycleLen) where i + j < n{
ret.append(strs[j + i])
if i != 0 && i != numRows - 1 && j + cycleLen - i < n {
ret.append(strs[j + cycleLen - i])
}
}
}
return ret
}
}
Demo地址：github
