蓝桥杯---N字形变换（leetcode第6题）题解

1.问题重述

这个题目可以是Z字形变换，也可以叫做N字形变换：

给定我们一串字符，我们需要把这串字符按照先往下写，再往右上方去写，再往下去写，再往右上方去写，这个书写的形状类似于字母N或者说是Z，我们最后再按照从第一行到最后一行的顺序读取一下即可；

给定的参数除了这个字符串，还有一个n，表示的就是我们的这个变换的深度，也就是我们的这个变换得到的这个结果的行数；

2.例子分析

其实这个过程很容易看明白，对于这个例子，我觉得也没有什么可以多说的，但是还是看一下这个官方给出来的两个案例：

• 第一个例子是n=3，也就是每一次写三行之后，就要转弯，这个矩阵的行数就是3（矩阵是我们后面用来模拟这个过程的重要工具）
• 第二个例子是n=4,也就是写四行之后就开始进行变换，我们这个时候构建的矩阵的行数就是4行；
• 第三个例子就更加简单了，是n=1的这个情况，这个意味着什么，意味着我们的这个字符串原封不动，因为n=1说明只有一行，这样进行变换之后的结果和我们原来的这个字符串没有任何区别，希望大家理解；

3.思路讲解

我们上面说了，这个过程是借助矩阵进行说明情况的：

下面的这个是按照字母顺序abcdefg进行演示说明思路的：

n=4的时候，第一行的是0和6（下标），我们可以发现有什么规律？这个6表示的是什么，是不是前面的这个数据的个数，就是从a~f的这个过程里面的字符的个数；

这个个数在这个里面我们称之为公差：d,这个d的求解就和我们的n相关，d=2n-2，下面我画了一个图说明这个d和n之间的关系是如何推导出来的；

我们把这个e,f往左边去挪动，把这个e,f挪动到一列这个时候发现这个2n就是这个红色的两列：因为这个里面有两个空格(两个红叉在的地方），所以这个个数就是2n-2(其他的这个n的情况大家可以去测试，也是2n-2);

接下来，我们总结一下这个规律，如下图所示：

我们分为了第一行的输出顺序，最后一行的输出顺序和中间行的输出顺序；

第一行就是0 0+d 0+2d这样的等差数列的顺序，这个d就是我们上面使用2n-2求解出来的公差；

最后一行第一个元素下标是n-1 第二个元素9就是n-1的基础上面加上d，以此类推；

中间行元素比较复杂，比如第二行的第一个元素是1，第二个是5，两个的关系就是1+5=6，所以我们加上第一列的元素就是k,则这一行的第二个元素就是d-k,然后分别以这两个数字作为基础，1+d=7,1+2d=13，然后是以5作为基础，5+d=11然后依次类推；

4.代码分析

第三行是特殊情况：d=2n-2，因此当这个n==1的时候，也就是这个数组元素原封不动，return就是这个给定的参数：字符串s；

ret是用来存储我们的最后的这个返回的结果的；

第12，17，26行的for循环，分别对应着我们的第一行的读取，中间行的读取，最后一行的读取方法；

第12行：i=0进行循环的时候，条件是i+=d，也就是每一步跳过的元素的个数就是我们的公差；

第26行：n-1是起始元素，也就是这个第一列的最后一个元素，他每一次跳过的元素就是d个；

第17行：k=1表示的从第二行开始的，k<n-1表示的循环终止条件是到达的倒数第二行结束，内层的这个for循环，实际上就是我们的k d-k k+d d-k+d这样的过程的表述，因为这个i,j都可能会越界，所以这个里面有if进行判断，如果没有越界，这个时候就把元素添加到我们的ret里面去；