力扣6：N字形变化

代码：

class Solution { public: string convert(string s, int numRows) { int len=s.size(); if(numRows==1) { return s; } int d=2*numRows-2; int count=0; string ret; //第一行！ for(int i=0;i<len;i+=d) { ret+=s[i]; } //第k行！ for(int i=1;i<numRows-1;i++) { for(int j=i,k=d-j;j<len||k<len;j+=d,k+=d) { if(j<len) { ret+=s[j]; } if(k<len) { ret+=s[k]; } } } //最后一行！ for(int i=numRows-1;i<len;i+=d) { ret+=s[i]; } return ret; } };

算法思路：

本题可以通过暴力的解法进行求解！即定义一个numsRows行，len列的数组！然后依次根据规律进行将数组元素填置，此时的空间/时间复杂度为O（numsRows*len）；

那么是否可以进行优化呢？

答案是肯定的，我们可以通过上图发现一个规律，第i的第一个元素都是i,然后第一行和最后一行有着相同的规律，每隔一个固定的值，会出现一个元素！那么如何求出这个固定的值呢？通过将numsRows我们不难发现！只需要将2*numsRows-2即可求出这个固定的值，我们称之为公差！

为什么是这种求法呢？我们可以将其中间只有一个元素的统一移到第二列，第二列并没有填满，而是只缺少了第一行和最后一行，所以我们不难得到公差d=2*numsRows-2！

所以第一行和最后一行的规律如下：

i---->i+d----->i+2d---.......(直至值大于等于len结束！)

既然第一行和最后一行都发现了规律，那么中间行是否也有规律呢？通过仔细发现，中间行确实也有规律所循！即中间行的第一个元素都和所在行数相同，第二个元素是d-i，这是一组元素！然后每组元素都向后移动的距离仍然还是d！ 直接当下标小于原字符串的长度时候结束！

所以第k行的元素有着以下的规律：

（i,d-i)---->(i+d,d-i+d)---->(i+2d,d-1+2d)   直至值大于等于len结束！

还需要注意的边界问题有：当给定的numRows为1！需要直接返回原字符串！ 否则就会导致死循环的发生！