【算法专题】模拟算法题

  模拟算法题往往不涉及复杂的数据结构或算法，而是侧重于对特定情景的代码实现，关键在于理解题目所描述的情境，并能够将其转化为代码逻辑。所以我们在处理这种类型的题目时，最好要现在演草纸上把情况理清楚，再动手编写代码

1. Z字形变换

6. Z 字形变换 - 力扣（LeetCode）

        对这道题，最容易想到的肯定是创建一个二维数组，像题目描述的那样，以Z字形填充数组，然后再遍历一遍数组，得到结果序列。然而这种做法比较复杂，而且时空复杂度都是比较高的，所以我们便来试着优化一下，找到更优秀的解法。一般而言，模拟题的优化往往都是根据找到的规律来编写代码，这道题也不例外。

        由于题目最后仅要求我们写出经过Z字形变换后得到的序列，所以我们其实是不需要真的创建数组的，只要能找到每一行的变换规律，编写代码，把每一行都加到要返回的字符串中就行了。

        为了方便画图，我们画的是要填入的字符串的下标，通过下图我们可以发现，图形中的第0行和最后一行填入的数规律是差不多的，假设公差为d，

则第0行：0，d，2d，……

最后一行：n-1，n-1+d，n-1+2d，……

        对于第一行和最后一行，用简单的数列知识就能得出d为2*n-2，至于中间的n-2行，看起来似乎有些复杂，但我们根本就没必要理会填入的元素在二维数组中的位置，只要知道它们的值就行了，所以注意观察数值规律，不难发现每一行的元素实际上可以被划分为两个数列的元素：

那么，现在我们已经可以找到了每一行的元素的规律，代码实现也就压根不需要二维数组了，希望大家看到这里，可以尝试根据算法原理，自行编写一下代码，然后再来看答案。

class Solution {
public:string convert(string s, int numRows) {if(numRows == 1) return s;int d = 2 * numRows - 2;int r0 = 0, rn = numRows - 1;string res;while(r0 < s.size()){res += s[r0];r0 += d;}for(int k = 1; k < numRows - 1; k++){for(int i = k, j = d - k; i < s.size() || j < s.size(); i += d, j += d){if(i < s.size()) res += s[i];if(j < s.size()) res += s[j];}}while(rn < s.size()){res += s[rn];rn += d;}return res;}
};