About
LeetCode刷题第7天，经过这几天的预热，脑子活络起来了，做题速度有了很大的提升，今天这道题为一道中等难度的题，花费了我近1小时，虽然时间还是很长，但是相对刚接触LeetCode有了很大的提升，我会继续坚持。
字符串Z形变换
题目描述
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zigzag-conversion
解题思路
以前在牛客网上刷到一道顺时针打印二维数组的题，跟这个比较类似，我认为做这类题都是要找到它的周期以及周期的规律，这样我们就可以使用循环结构解题了~
-
拿到题后，我先自己画了画，找到其中一种周期如下图所示：
周期.jpeg - 找到周期后分析周期规律为：操作行数的顺序为2，1，0，1，2，3 。一个周期的操作次数为（numRows -1）*2。
- 将一个周期分为两部分，前半部分的规律是随着index增加行数减小，后半部分随着index增加行数增加。
- 在while循环中嵌套for循环，因为字符串的长度不一定能够整除numRows，所以for循环中可能会出现list out of range的错误，一旦出现该错误就说明字符串已经遍历完毕了。
- 字符串遍历完毕后，调用将二维列表转成字符串的方法返回结果。
代码如下（Python3）
class Solution:
def assemble(self, array):
result = ''
for item in array:
result += ''.join(i for i in item)
return result
def convert(self, s: str, numRows: int) -> str:
if numRows <= 0:
return False
elif numRows == 1:
return s
if len(s) <= numRows:
return s
s = list(s)
result = [ [s.pop(0)] for item in range(numRows)]
while len(s):
for i in range((numRows - 1) * 2):
for j in range(numRows - 1):
try:
result[numRows-2 - j].append(s.pop(0))
except BaseException:
return self.assemble(result)
for k in range(numRows - 1):
try:
result[k + 1].append(s.pop(0))
except BaseException:
return self.assemble(result)
return self.assemble(result)
解法2
上面那种解法只是该类题的一种通解，运用在这道题上明显太麻烦，如果我们用一个指针指向需要被操作的行数，我们会发现行数的变化规律为：行数从0开始自增到最大行数-1然后开始自减到0，依次循环，所以我们可以通过一个指针指向需要备操作的行数，然后往里面追加字符，代码如下：
#-*- coding:utf-8 -*-
#Author: Bing Xu
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows <= 0:
return False
elif numRows == 1:
return s
length = len(s)
if length <= numRows:
return s
temp = ['' for i in range(numRows)]
index = 0
i = 0
while index < length:
while index < length and i < numRows - 1 :
temp[i] += s[index]
index += 1
i += 1
while index < length and i > 0:
temp[i] += s[index]
index += 1
i -= 1
result = ''.join(str(item) for item in temp)
return result
运行结果
image.png
解法3
其实我们也可以根据字符串字符的index直接算出来它归属于哪一行，但是其实时间复杂度不会变，并且我们还是需要一个新的列表去记录，对内存的消耗也不会减少，所以我没有用代码实现这种算法，只是一种思维的拓宽吧。
结束语
看到博客的小伙伴给我点个赞吧，每日更新哦~
