Python 版 LeetCode 刷题笔记 #6 Z 字形变换
Python 版 LeetCode 刷题笔记 #6 Z 字形变换
今天这题目中等难度，但属于那种理一理思路还挺清晰的那种。大清早上班路上看了题目有了思路，直到这一天快结束了才来写代码，应该也算“深思熟虑”了吧。
题目
中文题目
第 6 题 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);示例：
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
输入: 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英文题目
Question 6 ZigZag Conversion Characters: 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)
P A H N
A P L S I I G
Y I RAnd 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:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I思路
这个 Z 形变换，如果把竖着那一列往左拉伸，也可以叫做 V 形变换吧。根据给定的行数和字符串，假设给定 3 行，那么从字符串逐个字符将会被放在第 0 1 2 1 0 1 2 1 … 行上，接下来就在逐行按顺序将放在该行的字符连成完整字符串即可。
因为之前的题目中对字典基于哈希查找有挺深印象，而且字典的 key 值又可以是数字，那这次我就打算用一个字典来做载体。第 0 行上的元素，我就用 dic[0] 来存储，形式可以是字符串也可以是列表；第 n 行上的字符就用 dic[n] 来存取。根据最终表现看看这种应用字典的算法的效果如何。
代码
class Solution:
def convert(self, s: str, numRows: int) -> str:
# 生成类似 0 1 2 1 0 1 2 1 ... 规律的针对行数的列表，以此判断字符去第几行
unit = [i for i in range(numRows)]+[i for i in range(numRows-2,0,-1)]
# dic 字典是我们计划使用的载体
dic={}
# 对输入的字符串遍历
l = len(s)
for i in range(l):
# dic.setdefault(key,[]) 初始化在 key 处的值为空列表
# 遍历过程中把根据 unit 确定第几行、并将该字符添加到 dic[该行] 中
dic.setdefault(unit[i%len(unit)],[]).append(s[i])
# result 列表用来逐行收取结果
result=[]
# 因为我们字典的 key 是行数，逐行读取即可
for j in range(numRows):
# dic.get(key,[]) 是读取 key 处值，没有的话默认返回空列表
# result.extend(lst) 是将 lst 添加到 result 列表之后，列表相加的写法之一
result.extend(dic.get(j,[]))
# 最终将列表转化成字符串
return "".join(result)提交答案
这次提交答案后，表现还可以：
中文区结果：
执行用时 :116 ms, 在所有 Python3 提交中击败了19.32%的用户 内存消耗 :13.9 MB, 在所有 Python3 提交中击败了5.00%的用户
英文版结果：
Runtime: 72 ms, faster than 31.33% of Python3 online submissions for ZigZag Conversion. Memory Usage: 13.8 MB, less than 10.00% of Python3 online submissions for ZigZag Conversion.
因为思路挺中规中矩的，所以这表现也算达到预期了。
优化
首先考虑到的优化思路是，我在字典中对每行存字符时采用的是列表，这个可能会拉低表现，于是写了一版直接用字符串存储的，但提交后性能提升不高。可见关键还在整个算法设计上。
代码微调
class Solution:
def convert(self, s: str, numRows: int) -> str:
unit = [i for i in range(numRows)]+[i for i in range(numRows-2,0,-1)]
l = len(s)
dic={}
for i in range(l):
index = unit[i%len(unit)]
temp = dic.get(index,"")+s[i]
# 调整在字典中存储的类型，不再是列表而是字符串
dic[index]=temp
result=""
for j in range(numRows):
# 最终直接拼接字符串返回即可
result+=dic.get(j,"")
return result表现结果：
Runtime: 68 ms, faster than 38.40% of Python3 online submissions for ZigZag Conversion. Memory Usage: 13.8 MB, less than 10.00% of Python3 online submissions for ZigZag Conversion.
提升并不明显，那让我们翻翻看推荐答案和讨论区，果然，总有让人眼前一亮的存在：
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows < 2:
return s
res = ["" for _ in range(numRows)]
i, flag = 0, -1
for c in s:
res[i] += c
if i == 0 or i == numRows - 1:
flag = -flag
i += flag
return "".join(res)
# 代码来源
#https://leetcode-cn.com/problems/zigzag-conversion/solution/zzi-xing-bian-huan-by-jyd/代码精简，运行表现更是亮眼：
Runtime: 40 ms, faster than 99.58% of Python3 online submissions for ZigZag Conversion. Memory Usage: 14 MB, less than 10.00% of Python3 online submissions for ZigZag Conversion.
同时，这代码中 res = ["" for _ in range(numRows)] 这一句用到了列表推导式，以及单下划线命名的变量。通常单个独立下划线用作一个名字时，表示该变量是临时的或无关紧要的。这一行代码就实现了为将每一行赋值为空字符串的效果，可见，这个解法也是用字符串来存结果的。
接下来看它如何分配字符到某行，很明显，是靠 flag =1 或 -1 来控制方向来逐行分配。只靠变量是否达到边界来做控制，且将该控制过程放到了遍历输入字符串的过程中，这么一来一套流程走下来就可以了，确实精妙。
结论
第六题，中等难度，按照预想的设计，练习了诸多字典的用法，比如 dict.setdefault(key, default_format)、dict.get(key, default_value) 等用法。同时也在参考答案中加深了列表推导式配合单下划线变量名的使用 [ value for _ in range(n) ]。说实话，这种单下划线变量名前两天在别的答案中也看到过，当时也没来得及去查，今天也算是了然于胸了。
今天切实体会到了借鉴别人代码的意义，除了算法，还有很多精妙的设计、更实用的方法在等着我们去发现和学习呢！