NO.6 Z字形变换
原题:
将字符串 "PAYPALISHIRING"
以Z字形排列成给定的行数:
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
除了第一行和最后一行没有中间形成之字型的数字外,其他都有,而首位两行中相邻两个元素的index之差跟行数是相关的,为 2*nRows - 2, 根据这个特点,我们可以按顺序找到所有的黑色元素在元字符串的位置,将他们按顺序加到新字符串里面。对于红色元素出现的位置也是有规律的,每个红色元素的位置为 j + 2*nRows-2 - 2*i, 其中,j为前一个黑色元素的列数,i为当前行数。 比如当n = 4中的那个红色5,它的位置为 1 + 2*4-2 - 2*1 = 5,为原字符串的正确位置。当我们知道所有黑色元素和红色元素位置的正确算法,我们就可以一次性的把它们按顺序都加到新的字符串里面。
def convert(self, s, numRows):
str_length = len(s)
# 两列之间的差
node_length = 2 * numRows - 2
result = ""
if str_length == 0 or numRows == 0
\ or numRows == 1:
return s
# 从第一行遍历到最后一行
for i in range(numRows):
for j in range(i, str_length, node_length):
# 第一行和最后一行
还有普通行的整列数字
result += s[j]
if i != 0 and i != numRows - 1 and \
j - 2 * i + node_length < str_length:
# 单列行的数字
result += s[j - 2 * i + node_length]
return result