拿什么拯救你，我的offer！（从零打卡刷Leetcode——No.006）
拿什么拯救你，我的offer！（从零打卡刷Leetcode——No.006）
小詹此记录贴的读者越来越少了，也许是小詹总结的不够好欢迎留言区提出宝贵的意见！也欢迎和小詹一起定期刷leetcode，每周一和周五更新一题，每一题都吃透，欢迎一题多解，寻找最优解！这个记录帖哪怕只有一个读者，小詹也会坚持刷下去的！
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一下噢！
往期推荐
【记录帖】（No.001）从零打卡刷Leetcode
【记录帖】（No.002）从零打卡刷Leetcode
【记录帖】（No.003）从零打卡刷Leetcode
【记录帖】（No.004）从零打卡刷Leetcode
【记录帖】（No.005）从零打卡刷Leetcode