LeetCode

字符串

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

1
string convert(string s, int numRows);

示例 1：

1
2
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

1
2
3
4
5
6
7
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

1
2
输入：s = "A", numRows = 1
输出："A"

提示：

  • 1 <= s.length <= 1000
  • s 由英文字母（小写和大写）、',' 和 '.' 组成
  • 1 <= numRows <= 1000

模拟法

思路：

通过模拟过程来实现，使用一个flag来判断行号变化的方向（方向无非是递增或者递减）

  1. res[i] += c： 把每个字符 c 填入对应行
  2. i += flag： 更新当前字符 c 对应的行索引；
  3. flag = - flag： 在达到 ZZZ 字形转折点时，执行反向。
1
2
3
4
5
6
7
8
9
10
11
12
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 chr in s:
            res[i]+=chr
            if i==0 or i==numRows -1:
                flag=-flag
            i+=flag
        return "".join(res)

坐标映射法

思路：

假设4行 转成N就是0123210123210…[行索引] 循环的是012321 由于N字形左上和右下需要转弯 所以掐头0去尾3 0123-> 12 temp = [0,1,2,3,2,1]，把temp当尺子，一段一段量s，再映射到行数就可以了

1
2
3
4
5
6
7
8
9
10
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows< 2: 
            return s
        ruler = [i for i in range(numRows)]
        ruler += ruler[1:-1][::-1]
        res = [''] * numRows
        for i in range(len(s)):
            res[ruler[i%len(ruler)]] += s[i]
        return "".join(res)