题目描述

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

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

L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”LCIRETOESIIGEDHN”。

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

样例

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

算法1

(找规律 + 模拟) $O(n)$

找一下规律，可以发现大致是这样的路线

0                                    2r - 2                                     4r - 4
1                           2r - 3   2r - 1                             4r - 5  4r - 3  
2                   2r - 4           2r                         4r - 6          .
.                   .                .                      .                   .
.               .                    .                  .                       .
.           .                        .               .                          .
r - 2   r                            3r - 4  3r - 2                             5r - 6
r - 1                                3r - 3                                     5r - 5

时间复杂度

只是写了个字符串长度的，所以是$O(n)$

参考文献

C++ 代码

class Solution {
public:
    string convert(string s, int r) {
        if (r <= 0) return "";
        if (r == 1) return s;
        string res;
        for (int i = 0; i < r; ++i){
            for (int j = i; j < s.size(); j += 2 * r - 2){
                if (i == 0 || i == r - 1) res += s[j];
                else {
                    res += s[j];
                    if (j + 2 * (r - i - 1) < s.size())
                        res += s[j + 2 * (r - i - 1)];
                }
            }
        }

        return res;
    }
};