题目概要

将字符串按照ZigZag的顺序重新排列，求排列之后的新字符串。

题目链接

ZigZag Conversion

题目解析

数学规律

寻找原先的字符在经过ZigZag变换后的位置，直接计算出最后的字符串：

0   4   8     12
1 3 5 7 9  11 13
2   6   10    14

上例中的数字代表的是对应的字符索引，设n为输入的参数numRows的值，则该例中为3，容易知道
第一行的字符索引序列为

索引序列
先考虑最后一行，容易发现该行的索引序列与第一行的对应差值为n-1
中间几行与前述两者差距较大，我们再看一个简单的实例：

0     6       12       18       24
1   5 7    11 13    17 19    23 25
2 4   8 10    14 16    20 22    26
3     9       15       21       27

看似毫无规律，但当我们将其分为两列分别观察时：

下标 - 1
下标 - 2

或者

下标 - 3
下标 - 4
上述两条，也容易通过判断是否为第奇数个字符的规则合并为一条规则。
具体细节参见代码部分。

手动模拟

按照题目的要求，分配多个字符数组，完成操作后，拼接在一起。

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)
注：上述的n为字符串的长度

代码

数学规律

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        int delta = numRows - 1;
        int sz = s.size();
        string rs;
        // row 0
        for (int i=0; i<sz; i+=2*delta)
            rs.push_back(s[i]);
        // row [1, numRows-1)
        for (int row=1; row<numRows-1; ++row) {
            int cur = 0; // 该行第几个字符
            int idx = row; // 对应原先字符串的第几个
            while (idx<sz) {
                if (cur%2 == 0) {
                    // row + 2*delta * (cur/2)
                    idx = row + delta * cur;
                }
                else {
                    // -row + 2*delta * ((cur+1)/2)
                    idx = -row + delta * (cur+1);
                }
                if (idx<sz)
                    rs.push_back(s[idx]);
                ++cur;
            }
        }
        // row numRows-1
        for (int i=numRows-1; i<sz; i+=2*delta)
            rs.push_back(s[i]);
        return rs;
    }
};

手动模拟

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        vector<string> v_str = vector<string>();
        for (int i=0;i<numRows;++i)
            v_str.push_back(string());
        int idx = 0; // 当前字符的索引
        int row = 0; // 将被填充的字符串索引
        int dir = 1; // 方向：1 => 往下 -1 => 往上
        int sz = s.size();
        while (idx<sz) {
            v_str[row].push_back(s[idx]);
            row += dir;
            if (row == 0)
                dir = 1;
            if (row == numRows-1)
                dir = -1;
            ++idx;
        }
        string rs;
        for (int i=0;i<numRows; ++i)
            rs += v_str[i];
        return rs;
    }
};

广告区域

本人和小伙伴们承接各种软件项目，有需求的可以联系我们。
QQ: 2992073083