【C++算法】40.模拟_N 字形变换

---

题目链接：

6. N 字形变换

---

题目描述：

---

解法

解法一：模拟

a,b,c,d,e,f,g......

n=4

弄个矩阵放进去，最后从左往右读取。

解法二：模拟优化-找规律

在n=4的时候，0和6之间相差了6个元素：0，1，2，3，4，5

我们把元素移动位置，可以得到在输出的第一个元素后面那个元素，是距离第一个元素2n-2个元素的。得到公差d=2n-2

第0行的规律就是：0->0+d->0+2d......->0+kd (kd<len)

第n-1行的规律就是：n-1->n-1+d->n-1+2d......->n-1+kd (n-1+kd<len)

这里的第1~n-2行都有两个元素是一组的。并且他们加起来刚好是公差。

第1~n-2行的规律是：(k,d-k)->(k+d,2d-k)......->(k+(k-1)d,kd-k) (k+(k-1)d<len),(kd-k<len)

不过如果就这么结束，那就错啦。

n=1的时候，运用上面的规律就会死循环，所以我们要单独讨论n=1的情况，直接输出字符串。

---

C++ 算法代码：

class Solution 
{public:string convert(string s, int numRows){// 处理边界情况if(numRows == 1) return s;string ret;int d = 2 * numRows - 2, n = s.size();// 1. 先处理第一行for(int i = 0; i < n; i += d)ret += s[i];// 2. 处理中间行for(int k = 1; k < numRows - 1; k++) // 枚举每一行{for(int i = k, j = d - k; i < n || j < n; i += d, j += d){if(i < n) ret += s[i];if(j < n) ret += s[j];}}// 3. 处理最后一行for(int i = numRows - 1; i < n; i += d)ret += s[i];return ret;}
};