(leetcode)Z字形变换 -- 模拟算法

 个人主页：Lei宝啊 

愿所有美好如期而遇 

题目链接

. - 力扣（LeetCode）

输入描述

string convert(string s, int numRows)，输入一个字符串s，以及一个行数numRows，将字符串按照这个行数进行Z字形排列，实际上本题是将Z字形反转成了N字形。

输出描述

按照行将Z字形排列的字符打印出来。

算法分析

模拟算法，实际上就是根据题目要求做，优化就是找规律。

本道题，我们将通过画图来找规律，以示例二为例画图：

找规律，这没有什么比较好的方法，找得到就是找得到，根据图我们可以发现第一行和最后一行每个元素的下标差了6，也就是说公差为6，而中间行的元素，虽然也遵循这个规律，不过是两个数字两个数字这样来进行的--1+6=7  5+6=11。

那么如何计算公差，你说公差是6就是了吗？我们可以多画几个图来进行验证，最后我们可以得到的结论是公差d = 2 * 行数 - 2；

对于第一行和最后一行而言，我们可以直接使用公差进行计算，而对于中间行来说，需要两个数字一起向后走，那么我们怎样得到第二个数字呢？观察后我们可以发现，这两个数字的下标加起来正好是公差d，所以我们可以用公差 - 下标一 = 下标二，后面的下标我们通过公差就可以得到了。

我们也就可以按照这样的规律，让下标和字母进行对应，直接把字符尾插进我们创建的string s变量中。

解题源码 

class Solution {
public:
    string convert(string s, int numRows) 
    {
        if(numRows == 1) return s;

        string ret;
        int d = 2 * numRows - 2;
        int len = s.size();

        for(int i=0; i<len; i+=d) ret += s[i];
        for(int i=1; i<numRows-1; i++)
        {
            for(int j=i, k=d-i; 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;
    }
};