【自留】N字形变换——两个巧解

先看题：

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

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

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

解法很多，暴力一下也很好写，这里记录两个比较巧妙的解法。

一、通过直接构造，来计算答案每一行的的字母所对应的下标

观察可得，对于一个行数为numRows的输入，将每（numRows+numRows-2）个字符划为一个周期。在每个周期内，第一行和第numRows行只有一个字符，中间的行会有两个字符。这些字符所对应的下标都能通过行数和周期数计算出来（具体参数略），因此只需要遍历行数作为外循环，遍历周期数作为内循环即可。

需要注意的是要对最后一个不完整周期作额外判断，防止越界。

时间复杂度：O(n) ，虽然看上去是双重循环，但实际上输入串s的每个位置只被访问过一次，本质上是一个对输入串s的遍历。

空间复杂度：O(1)，无需额外变量。

二、模拟N字形构造过程

在这个解法中我们需要numRows个数组，用于记录每一行的结果。

根据题意，在numRows = 3 时，在把输入串s构造成这样N字型的时候，我们是遍历s，把每一个字符挨个顺着1、2、3行放入，再逆向回到2、1行，再逆向2、3行。

枚举一下就是s[0]在第一行，s[1]在第二行，s[2]在第三行，s[3]在第二行，s[4]在第一行，s[5]在第二行，s[6]在第三行……

因此我们只需要遍历一遍s，并用一个变量记录当前到第几行，把对应的字符放到对应的行的数组中储存即可。这个用于记录第几行的变量，在到达numRows行和第一行的时候翻转计数，即可。通常额外采用一个flag=1或者-1来表示是在向上走还是在向下走。

需要注意的是数组下标和对应变量的相统一。

时间复杂度：O(n) 

空间复杂度：O(n)

总结：方法1空间开销更小，但代码写起来略微复杂；方法2简单易懂，代码量少，通过flag来记录上下行的方法简单有效且巧妙，但对应需要空间开销。