题目
给出一个字符串s和要求的输出的行数numRow,求锯齿转换后按行读取的结果。
比如:
1 | 给出的字符串是 "PAYPALISHIRING" ,分3行 |
输出: “PINALSIGYAHRPI”
分析
第一直觉是要利用二维数据,每一行为一个子数组,根据锯齿的特性,依次往每个数组里填充元素,直至完成。
给每个行和列标注坐标以后:1
2
3
4
5 0 1 2 3 4 5 6
0 P I N
1 A L S I G
2 Y A H R
3 P I
得出如下的规律:
- 字符串的每个坐标位置index与列col和行row存在关系: 2col + row = index
- 当row增长到numRow大小时,开始递减,并递减至0时开始递增。
仅借用第2条规律即可解题
解题
1 | class Solution: |
该解法只遍历了一遍字符串,因此时间复杂度为O(n)。
跳坑总结
第一次写代码时,想构建一个二维数组,写成了[[]]* numRow. 运行时发现不正确,这里时一处坑。
代码的优化
leetcode的社区中看到了跟我思路相同的解法,但人家的代码更简洁,主要是利用了字符串的特性,减少了数组的拼接。
1 | class Solution(object): |