No.6 Z字型变换
原题：（有中文网站，就不去读英语啦哈哈）
将字符串
"PAYPALISHIRING"以Z字形排列成给定的行数，之后从左往右，逐行读取字符："PAHNAPLSIIGYIR"实现一个将字符串进行指定行数变换的函数:
例如:
输入: s = "PAYPALISHIRING", numRows = 4 输出: "PINALSIGYAHRPI" 解释: P I N A L S I G Y A H R P I
题目大意：首先"Z字型"要能够看出来其具体走向，为了便于小伙伴理解题意，将字符串改为顺序的字符，方便理解。如下排列后要按照逐行输出（如下则为AGBFHLCEIKDJ）
题目分析：看到这种题目，必须先找规律，就像本科c语言学习过程一样。小詹首先找到两列的规律，在纸上一顿乱画……然后发现：第一行比较具有代表性，其他行可以通过第一行加减得到，而第一行相邻两列之间相隔为2*numRows-2，下面就以numRows分别为3和4为例，画出来方便小伙伴理解（字丑人帅噢）
得到了这就可以往下继续思考了~我们可以依次打印出每一行，第一行简单，字符串的索引符合2*numRows-2的整数倍即可。之后只用依次加上行数或者减去行数即可，例如i表示第几行（为方便，从0开始，第0行、1行…i行…）。这里提供一种取模的方法（可以理解成余数）。这里得观察到首末两行比较简单，字符在字符串中对应索引除以2*numRows-2模为0或者numRows-1；中间若干行，要多出一种情况，取模为i（从上往下箭头方向）或者2*numRows-2-i（从下往上箭头方向）。
于是我们可以逐行输出，第一层循环为遍历所有行，第二层循环遍历所有符合对应行的字符。代码和注释如下：
class Solution: def convert(self, s, numRows): """ :type s: str :type numRows: int :rtype: str """ n = numRows #开始小詹是利用列表保存，然后得到结果 #再将其转换为字符串的，这里定义空的列表 res_list = [] l = len(s) #考虑到极端情况，其实这里小詹还是没有考虑全 #除了一行，还应该考虑到单字符串或者空字符串 if n == 1: return s #遍历0到n-1行 for i in range(n): #遍历所有字符，j表示索引 for j in range(l): #这是就是小詹介绍的取模判断是否在第i行输出 if j%(2*n-2) == i or j%(2*n-2) == 2*n-2-i: res_list.append(s[j]) #这里就是利用join将列表转换为字符串 res = "".join(res_list) return res
是不是觉得很简单？不，超时了你敢信，虽然执行出得到了正确结果，但是提交显示超时！分析下，做了哪些无用的计算呢？这里注意到for j in range(l):遍历了所有的索引，但是事实上是有规律可循的，并不需要暴力遍历所有。代码
class Solution(object): def convert(self, s, numRows): """ :type s: str :type numRows: int :rtype: str """ 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): #大的改进在这里！！！不再逐一遍历，而相当于j += node_length for j in range(i, str_length, node_length): # 第一行和最后一行 还有普通行的整列数字 result += s[j] #不是第一行和最后一行，且不说普通垂直的时，j-*i+node_length得到第i行斜着的那部分需输出的字符 if i != 0 and i != numRows-1 and j - 2*i + node_length < str_length: result += s[j-2*i+node_length] # 单列行的数字 return result
到这就得到了可以通过的正确解答了，写文章比做题还耗时……感兴趣的小伙伴可以提交try一下噢！
