【LeetCode】修炼之路-0006-Zigzag Conversion （Z 字形变换）【python】
题目
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 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
Example 3:
Input: s = “A”, numRows = 1
Output: “A”
Constraints:
1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ‘,’ and ‘.’.
1 <= numRows <= 1000
Topics
Companies
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)
题目分析
我们一开始刷算法题的时候，会遇到读不懂题目的问题。别灰心，慢慢来。
这个Z字形变换，看似花里胡哨，又是竖着又是斜着，交替变化。
但是我们抓住主要矛盾，看一下输入和输出。
实际上是根据给定的行数，分成几列展示。
所以比如对于ABCDEFGHI这样的字符串，要求分成3行，我们可以把问题退化成2个问题，
1.先实现简单的列式排列
实现分3行显示，每列都是从上到下
A D G
B E H
C F I
2.再增加方向变化的逻辑
设置一个开关一样的变量，控制从上往下还是从下往上
A E I
B D F H
C G
初等代码
伪代码
- 初始化用于输出的字符串
- 循环字符串
- 增加方向变化的逻辑
1. 初始化用于输出的字符串
分成n行，那么我们肯定要有3个字符串的变量来存
基本操作-使用for循环初始化
# 方法1：使用循环初始化
rows = []
for i in range(numRows):
rows.append('')
进阶操作1-列表生成式
# 方法2：列表生成式
rows = ['' for _ in range(numRows)]
进阶操作2-序列乘法
# 方法3：序列乘法
# 语法：sequence * n
rows = [''] * numRows
2. 循环字符串
def convert_simple(s: str, numRows: int) -> str:
# 初始化行
rows = [''] * numRows
# 按列填充字符
for i, char in enumerate(s):
row_idx = i % numRows # 循环获取行索引
rows[row_idx] += char # 这里的行索引，实际上就是rows的下标
# 合并所有行
return '\n'.join(rows)
# 测试
s = "ABCDEFGHI"
result = convert_simple(s, 3)
print(result)
3. 增加方向变化的逻辑
一开始，step是1，因为是从上往下，在rows列表里也就是从左往右，从小到大递增索引值的。然后到了第三个值curr_row==2, rows的下标就要往左走了，这个时候，置step为-1。我们列表分析如下
| 字符 | i % 3 (看似能用 但实际无关) | curr_row (改变前) | 是否改变方向 | step | curr_row (改变后) | rows |
|---|---|---|---|---|---|---|
| A | 0 | 0 | 在顶部，向下 | 1 | 1 | [‘A’,‘’,‘’] |
| B | 1 | 1 | 继续向下 | 1 | 2 | [‘A’,‘B’,‘’] |
| C | 2 | 2 | 在底部，向上 | -1 | 1 | [‘A’,‘B’,‘C’] |
| D | 0 | 1 | 继续向上 | -1 | 0 | [‘A’,‘BD’,‘C’] |
| E | 1 | 0 | 在顶部，向下 | 1 | 1 | [‘AE’,‘BD’,‘C’] |
| F | 2 | 1 | 继续向下 | 1 | 2 | [‘AE’,‘BDF’,‘C’] |
| G | 0 | 2 | 在底部，向上 | -1 | 1 | [‘AE’,‘BDF’,‘CG’] |
| H | 1 | 1 | 继续向上 | -1 | 0 | [‘AE’,‘BDFH’,‘CG’] |
| I | 2 | 0 | 在顶部，向下 | 1 | 1 | [‘AEI’,‘BDFH’,‘CG’] |
通过这个表格可以清楚地看到：
- i % 3的值与实际的行为完全不对应
- 比如D和E，i % 3都是0，但一个在第1行继续向上，一个在第0行开始向下
- 实际的方向变化完全取决于curr_row的位置
- 真正起决定作用的是curr_row：
- 在0时向下
- 在2(底部)时向上
- 其他情况保持原方向
代码如下：
class Solution:
def convert(self, s: str, numRows: int) -> str:
rows = [''] * numRows
step = 1
curr_row = 0
for char in s:
rows[curr_row] += char
# 如果到达底部，改变方向向上
if curr_row == numRows - 1:
step = -1
# 如果到达顶部，改变方向向下
elif curr_row == 0:
step = 1
curr_row += step
return ''.join(rows)
非常优雅！点击运行也是可以的，
我们勇敢提交！阿勒？说好的accepted呢！
我们可以看到报错出现在行数为1的时候
让我们分析一下当 numRows = 1 时的执行过程：
| 字符 | numRows | curr_row (改变前) | step | curr_row (改变后) | 问题说明 |
|---|---|---|---|---|---|
| A | 1 | 0 | 1 | 1 | curr_row从0变成1 |
| B | 1 | 1 | -1 | 0 | curr_row=1已经越界! |
问题在于：
-
当 numRows = 1 时，只有一行（下标为0）
-
但我们的代码中：
- 初始 curr_row = 0
- 当 curr_row == 0 时，执行 step = 1
- curr_row += step 导致 curr_row 变成 1
- 此时 curr_row = 1 已经超出了 rows 的范围（因为rows只有一个元素）
好了，我们现在知道了问题，可是，为什么会出现这样的问题呢，为什么没有这样的直觉呢。哎，这就是编程经验的问题了，来看看我们这里的代码。
我们通过if-elif，希望代码进入不同的逻辑，但是因为有numRows变量的参与，使得我们被迷惑了，这里如果两个条件相等，就会让程序进入不可控的状态。所以对于numRows==1的情况，我们需要额外声明：
if numRows == 1:
return s
好了，我们打上补丁，重新运行一下：
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1:
return s
rows = [''] * numRows
step = 1
curr_row = 0
for char in s:
rows[curr_row] += char
# 如果到达底部，改变方向向上
if curr_row == numRows - 1:
step = -1
# 如果到达顶部，改变方向向下
elif curr_row == 0:
step = 1
curr_row += step
return ''.join(rows)
怎么memory那么低，一定是我打开的方式不对，再运行一次！
可以
知识点总结
列表生成式
列表生成式属于可以体现the zen of python的特性之一，理解好列表生成式，用好列表生成式，可以让你的代码更清晰，建议多看，多练习，掌握列表生成式的使用方法，可以让你的代码更紧凑，可读性更好，代码更优雅。
1. 基本语法
# 1.1 最基础形式
[x for x in range(5)] # [0, 1, 2, 3, 4]
# 1.2 带条件过滤
[x for x in range(10) if x % 2 == 0] # [0, 2, 4, 6, 8]
# 1.3 带转换操作
[str(x) for x in range(5)] # ['0', '1', '2', '3', '4']
# 1.4 多重循环
[(x, y) for x in range(2) for y in range(2)] # [(0,0), (0,1), (1,0), (1,1)]
2. 实用技巧
2.1 处理字符串
# 提取所有元音字母
text = "hello world"
vowels = [c for c in text if c in 'aeiou'] # ['e', 'o', 'o']
# 大写转换
[c.upper() for c in "hello"] # ['H', 'E', 'L', 'L', 'O']
# 去除空格
words = " python is awesome "
clean = [w for w in words.split() if w] # ['python', 'is', 'awesome']
2.2 数学运算
# 平方数
squares = [x**2 for x in range(10)] # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
# 欧几里得距离
points = [(1,1), (2,3), (3,5)]
distances = [((x**2 + y**2)**0.5) for x,y in points]
# 矩阵转置
matrix = [[1,2,3], [4,5,6]]
transposed = [[row[i] for row in matrix] for i in range(3)]
2.3 数据处理
# 字典处理
prices = {'apple': 0.5, 'banana': 0.25, 'orange': 0.75}
expensive = [(fruit, price) for fruit, price in prices.items() if price > 0.5]
# 数据清洗
data = [1, None, 3, '', False, 5]
cleaned = [x for x in data if x is not None and x != '']
# 扁平化列表
nested = [[1,2,3], [4,5,6], [7,8,9]]
flat = [num for sublist in nested for num in sublist]
3. 高级应用
3.1 条件表达式
# if-else在列表生成式中
[x if x > 0 else 0 for x in [-2, -1, 0, 1, 2]] # [0, 0, 0, 1, 2]
# 多条件
[
'high' if x > 7
else 'medium' if x > 3
else 'low'
for x in range(10)
]
3.2 集合和字典生成式
# 集合生成式
{x**2 for x in range(5)} # {0, 1, 4, 9, 16}
# 字典生成式
{x: x**2 for x in range(5)} # {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}
3.3 生成器表达式
# 使用()创建生成器表达式（节省内存）
squares = (x**2 for x in range(1000000))
序列乘法
序列乘法，在初始化的时候，比for循环效率好很多，建议初始化的时候，考虑用序列化乘法来进行一些初始化
# 字符串乘法
'a' * 3 # 'aaa'
'hello ' * 2 # 'hello hello '
# 列表乘法
[1] * 3 # [1, 1, 1]
['hi'] * 2 # ['hi', 'hi']
# 元组乘法
(1,) * 3 # (1, 1, 1)
('a', 'b') * 2 # ('a', 'b', 'a', 'b')
# 例如：创建交替模式
alternating = [0, 1] * 5 # [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
编程经验0006
- 写if-elif时要检查条件是否可能相等
- 特别是涉及变量计算的条件判断时（如 numRows-1）
- 要考虑边界情况下这些条件的值是否会产生冲突