將一個(gè)給定字符串根據(jù)給定的行數(shù)，以從上往下、從左到右進(jìn)行 Z 字形排列。

比如輸入字符串為 "LEETCODEISHIRING" 行數(shù)為 3 時(shí)，排列如下：

L C I R
E T O E S I I G
E D H N
之后，你的輸出需要從左往右逐行讀取，產(chǎn)生出一個(gè)新的字符串，比如："LCIRETOESIIGEDHN"。

改題目主要是要發(fā)現(xiàn)對(duì)應(yīng)的規(guī)律

主要的規(guī)律如下
1.起始下標(biāo)都是行號(hào)
2.第0層和第numRows-1層的下標(biāo)間距總是step 。
3.中間層的下標(biāo)間距總是step-2行數(shù)，2行數(shù)交替。
4.下標(biāo)不能超過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;//來進(jìn)行第中間行的分離
            index+=(i==0||i==numRows-1)?step:add;//最后一行跟第一行的setp總是等于sep的
        }
    }
    return ret;
}
int main(){
    string s;
    int numRows;
    cout<<"請(qǐng)輸入字符串與對(duì)應(yīng)的行數(shù)"<<endl;
    clock_t start,finish;
    start=clock();
    cin>>s>>numRows;
    string result=convert(s,numRows);
    cout<<result<<endl;
    finish=clock();
    cout<<"程序運(yùn)行時(shí)間為"<<(double)finish-start/CLOCKS_PER_SEC<<endl;
}

第二種方法，感覺這種方法比第一種方法好想，但是時(shí)空復(fù)雜度比較高，代碼如下

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

        if (numRows == 1) return s;

        vector<string> rows(min(numRows, int(s.size()))); // 防止s的長(zhǎng)度小于行數(shù)
        int curRow = 0;
        bool goingDown = false;

        for (char c : s) {
            rows[curRow] += c;
            if (curRow == 0 || curRow == numRows - 1) {// 當(dāng)前行curRow為0或numRows -1時(shí)，箭頭發(fā)生反向轉(zhuǎn)折
                goingDown = !goingDown;
            }
            curRow += goingDown ? 1 : -1;
        }

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

        return ret;
    }
};