目录

• 题目
• • 题目分析

题目

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R 

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);

示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：
输入：s = "A", numRows = 1
输出："A"

提示：
1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000

题目分析

看到这种题我们首先就是找到它的规律，并且这种题的对应规律关系还比较简单。
我首先按照排序并同时标注下标得到规律图如下：

对于一行来说

1. 我们可以看见对齐的部分每次增加都是一样的
2. 比如当nowrows=3时：0，4，8，12都增加4；1，5，9也是增加4；
3. 当nowrows=4时，都增加6
4. 我们按照简单的线性关系得到f(x)=2*x-2;
5. 并对nowrows=5进行验证，发现符合我们的设定，那就说明是正确的

对于列来说

每次都增加1，这个没有什么疑问的

对于没有对齐的部分

1. 我们发现除了第一行和最后一行没有不对齐
2. 对齐差数与nowrows无关
3. 如图分析
4. 如果按照数组的设定，第一行元素的下标为0，那么就变成g(x)=2*x

有了这个信息我们就改写代码了

char* convert(char* s, int numRows) {
    if (numRows == 1)
        return s;
    int len = strlen(s);
    char* str = (char*)malloc((len+1) * sizeof(char));
    int k = 0;
    int i = 0, j = 0;
    for (i = 0; i < numRows; i++) {
        for (j = i; j < len||j-2*i<len; j += 2 * numRows - 2) {
            if (i > 0 && i < numRows - 1) {
                if (j > i) {
                    str[k++] = s[j - i * 2];
                }
            }
            if(j < len)
                str[k++] = s[j];

        }
    }
    str[k] = 0;
    return str;
}

1. i表示行，j表示元素小标
2. len表示字符串长度，题中所给长度为14
3. j<len&&j-2i<len，这是因为博主发现如果只用j<len会导致当nowrows=4时漏掉下标为10的元素；我们得到10的元素是靠14-22，但是我们我们的j<14是不能达到14的，如果当j<=14会造成越界访问所以加上一个条件并且加一些条件判断
   
   

可以看见速度和内存消耗都是比较不错的
如果原地对字符串数组进行操作可以很大程度降低内存消耗，但是博主现在还没有想到这样的算法，如果有更好的算法，欢迎讨论！