【算法】模拟：（leetcode）6.Z 字形变换(medium)

目录

 题目链接

题目介绍

 解法

1、模拟：

2、找矩阵中的规律：

公差

第一行和最后一行

中间行 

 代码

 题目链接

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

题目介绍

 解法

1、模拟：

采用模拟的思想，按照Z字形，把原先的字符串直接依次填充在矩阵中（numRows行，s.size()为大小的列数。字符串长度最大为1000，数据量也不是很大）

2、找矩阵中的规律：

仅仅依靠模拟，完成题目，任务量有点大。

所以我们把字符串对应的下标直接填入到二维矩阵中，观察下标的变化规律。

直接看图：

公差

 通过多次列举不同行数的Z字形的字符串，可以得到公差的规律：

2*numRows-2

第一行和最后一行

然后我们利用公差，对于每一行进行观察。

可以发现对于第一行和最后一行，他们的下标变化是类似的。因此我们直接只观察第一行。

观察第一行：

其中 i 是行数，d 是公差 

中间行 

观察其余行（除去第一行、最后一行）

在这里，以第二行为例：

可以看到，以上规律适用于Z字形全部被填满的情况下。

一旦出现以下的情况，就需要在考虑越界的情况。 

 代码

class Solution {
public:
    string convert(string s, int numRows) {

        //只有一行
        if (numRows == 1)
            return s;

        string ret;
        //规律：公差 = 2（n-1）
        int d = 2 * (numRows - 1);
        int n = s.size();

        //第一行
        //因为第一行的下标是，原字符串中的最后一个
        //所以范围是[0，n）
        for (int i = 0; i < n; i += d)
        {
            ret.push_back(s[i]);
        }

        //中间行
        //中间行是从第2行开始，下标为1，
        //截止到倒数第二行，下标为numsRows-1
        for (int i = 1; i < numRows - 1; i++)
        {
           
            for (int j = i, next = d - i; j < n || next < n; j += d, next += d)
            {
                //next用于求，处于对角线的数
                //因为有时只存在对角线，后面就没有数了，next会发生越界
                if (j < n) ret.push_back(s[j]);
                if (next < n) ret.push_back(s[next]);
            }

        }

        //最后一行
        for (int i = numRows - 1; i < n; i += d)
        {
            ret.push_back(s[i]);
        }

        return ret;
    }
};