算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 Z字形变换 ，这道题很有意思，我们先来看题面：
题意
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) https://leetcode.com/problems/zigzag-conversion/
翻译
给定一个字符串，将它变成蛇形输出。这个蛇形的概念比较抽象，我们需要结合样例才能理解。
样例
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I分析
这题的题意有点鬼畜，意思是说将给定的字符串先按照蛇形排列好，然后再按行依次读入，最后输出新的字符串。
虽然LeetCode上给这题的难度是Medium，但实际上它还是比较简单的。和上一题的曼切斯特算法比起来，算得上是很简单的了。
这题会告诉我们字符串以及蛇形扭曲的行数，将字符串排成蛇形。这种没有任何算法或者数据结构，仅仅是实现题意的问题称为模拟题。显然今天的这一题就是一道模拟题。模拟题唯一的难度就是编码，实现一些比较复杂的功能，考验的其实是工程能力。
这个蛇形的排列也很简单，因为我们只要输出最后的按行连接的结果。所以我们完全可以忽略列的位置信息，只用关注摆放的行就好了。因为行数是有限的，对于每一行，我们可以用一个字符串记录当前行目前为止摆放的字符串，最后按照行的顺序将所有行的结果连接到一起就好了。通过观察，我们很容易发现，摆放的行是有周期规律的。一个周期是2 * rowJum – 2，从0先递增到rowNum – 1，再递减到1。
发现规律之后，再写出code就不难了。
def convert(text, numRows):
# 记录每一行结果的dict
lines = {}
if numRows == 0:
return text
for i in range(len(text)):
# 计算应该放在哪一行
idx = i % (2 * numRows - 2)
# 判断是在递增区间还是递减区间
if idx >= numRows:
idx = 2 * numRows - 2 - idx
line = lines.get(idx, "")
lines[numRows] = line + text[i]
result = ""
# 拼接答案
for i in range(numRows):
result += lines[i]
return result上面的代码很简单，但是藏着一个可以优化的地方。
在于dict的使用，dict的查询需要开销。其实我们可以替换成数组，因为我们已经确定行数了，所以数组的长度是固定的。如此优化之后，时间效率会更高一点。但是差别不会很大，代码就不放了，我想大家应该都能想明白。
来源：https://cloud.tencent.com/developer/article/1775411
作者：程序IT圈
