6.Z字形变换

将字符串 "PAYPALISHIRING" 以Z字形排列成给定的行数：

P　　　A 　　 H 　　　N
A 　P　 L　 S　I　 I 　 G
Y 　　　I 　　　R

之后从左往右，逐行读取字符："PAHNAPLSIIGYIR"

示例1：
输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"

示例 2:
输入: s = "PAYPALISHIRING", numRows = 4
输出: "PINALSIGYAHRPI"

我自己感觉是V字形变换，就是找规律的题。

解法:按行访问
首先访问 行 0 中的所有字符，接着访问 行 1，然后 行 2，依此类推...

分析

• 时间复杂度： ,其中 n == len(s)。每个索引被访问一次。
• 空间复杂度： ,对于 C++ 实现，如果返回字符串不被视为额外空间，则复杂度为 。

c++ code:

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<sstream>
#include<assert.h>
using namespace std;


class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1)
            return s;
        string res;
        int len = s.size();
        int core = 2 * numRows - 2;
        for (int i = 0; i < numRows;i++)
        for (int j = 0; j + i < len; j += core)
        {
            res += s[j + i];
            //除了第一行和最后一行的规律
            if (i != 0 && i != numRows - 1 && j + core - i < len)
            {
                res += s[j + core - i];
            }

        }
        return res;
    }
};
 
int main() {
    string s; int numRows;
    cin >> s;
    cin >> numRows;
    string ret = Solution().convert(s,numRows);
    cout << ret;
    return 0;
}

参考1