6. Z 字形变换【 力扣(LeetCode) 】

一、题目描述

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

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

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

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

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

string convert(string s, int numRows);
1

二、测试用例

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

三、解题思路

1. 基本思路：
     找规律，寻找每个字符串的最终位置，然后按顺序拼接。
2. 具体思路：每个字符的规律如下：
   
   • 按照每行每个元素的遍历顺序，依次把每个元素拼接到结果字符串中，具体做法如下：
     • ① 先找基准 t ，$t_j=j\ast (R-1)\ast 2$ ，基准要多找一个，防止漏掉元素。【就比如按照上面模板，元素就 5 个，如果基准不多找一个，确定到 $t_1$，则下标为 4 的元素无法遍历到】
     • ② 对于第 i 行来说，其元素下标就是基准加减行号，不过基准加减行号要合法。
     • ③ 对于第 1 行和最后一行要记得去重，因为第一行元素是同一个基准加减 0 ，最后一行元素是当前基准+行号和下一个基准-行号。【第一行去重可以丢弃基准+行号；最后一行去重，必须丢弃基准-行号，如果丢弃基准+行号，则最后一行第一个无法拼接到字符串，因为最后一行第一个元素基准-行号是非法的，基准+行号又被丢弃】

四、参考代码

时间复杂度：$\mathrm{O}(n)$
空间复杂度：$\mathrm{O}(1)$

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1)
            return s;
        int n = s.length();
        int pre, rear;
        string str = "";

        for (int i = 0; i < numRows; i++) {
            for (int j = 0, t = 0; t < n + numRows; j++) {
                t = j * (numRows - 1) * 2;
                pre = t - i;
                rear = t + i;
                if (i != numRows - 1 && 0 <= pre && pre < n) // 最后一行去重 和 基准-行号合法
                    str += s[pre];
                if (i != 0 && 0 <= rear && rear < n) // 第一行去重 和 基准+行号合法
                    str += s[rear];
            }
        }

        return str;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24