字符串算法题Z字行变换

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

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

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

改题目主要是要发现对应的规律

主要的规律如下
1.起始下标都是行号
2.第0层和第numRows-1层的下标间距总是step 。
3.中间层的下标间距总是step-2行数，2行数交替。
4.下标不能超过len(s)-1

算法代码如下所示

#include<iostream>
#include<string>
#include<stdio.h>
#include<time.h>
using namespace std;
string convert(string s,int numRows){
    if(numRows==1)
        return s;
    int step=2*numRows-2;//间距
    int add=0;
    int len=s.length();
    string ret;
    for(int i=0;i<numRows;i++){
       int index=i;
        add=i*2;
        while(index<len){
            ret+=s[index];
            add=step-add;//来进行第中间行的分离
            index+=(i==0||i==numRows-1)?step:add;//最后一行跟第一行的setp总是等于sep的
        }
    }
    return ret;
}
int main(){
    string s;
    int numRows;
    cout<<"请输入字符串与对应的行数"<<endl;
    clock_t start,finish;
    start=clock();
    cin>>s>>numRows;
    string result=convert(s,numRows);
    cout<<result<<endl;
    finish=clock();
    cout<<"程序运行时间为"<<(double)finish-start/CLOCKS_PER_SEC<<endl;
}

第二种方法，感觉这种方法比第一种方法好想，但是时空复杂度比较高，代码如下

class Solution {
public:
    string convert(string s, int numRows) {

        if (numRows == 1) return s;

        vector<string> rows(min(numRows, int(s.size()))); // 防止s的长度小于行数
        int curRow = 0;
        bool goingDown = false;

        for (char c : s) {
            rows[curRow] += c;
            if (curRow == 0 || curRow == numRows - 1) {// 当前行curRow为0或numRows -1时，箭头发生反向转折
                goingDown = !goingDown;
            }
            curRow += goingDown ? 1 : -1;
        }

        string ret;
        for (string row : rows) {// 从上到下遍历行
            ret += row;
        }

        return ret;
    }
};