6. Z字形变换

题目描述

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

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

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

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

我的思路

可以把对应的数组序号排列出来

0   4   8     12
1 3 5 7 9  11 13
2   6   10 

不难发现，如果是同一行的序号，那么相邻的两列之间序号的和有种关系，例如：

0+4=4；4+8=12；8+12=20；

1+3=4；3+5=8；5+7=12…；

2+6=8；6+10=16

会发现和均为4的倍数。在尝试多个不同的numRows后会发现相邻的系数和一定是(2numRows-2)的倍数，那么根据这个式子将满足的相邻和放在一起即可。

string convert(string s, int numRows) {
        vector<string> num(numRows);//使用num字符串数组存储对应每行的字符串
        string ans;
        int i=0,j=1,temp=0;
        if(s.size()<=numRows||numRows==1)return s;//极端情况返回自己
        while(i<numRows){//i分不同行进行遍历
            num[i]+=s[i];
            temp=i;
            for(j=i+1;j<s.size();j++){
                if((temp+j)%(2*numRows-2)==0){
                num[i]+=s[j];
                temp=j;//temp存储上一个元素，以保证两个下标是相邻的
            }
            }
            i++;
        }
        for(i=0;i<numRows;i++){//把所有行的字符串求和
            ans+=num[i];
        }
        return ans;
    }

还有一个转换顺序的思路，这里不多讲解，可以参考这里