Z 字形变换

LeetCode第六题

题目描述：
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);
示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L D R
E O E I I
E C I H N
T S G

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zigzag-conversion

思路：

首先解决掉特殊情况。当字符串为空时，返回空字符串。当行数为一时，返回原字符串。
然后看一般情况。此时字符串非空，且行数大于一。观察得出Z型字符串有周期性，求出周期间隔，然后针对首尾两行与其他行分别做处理即可。

源代码

char * convert(char * s, int numRows){
    int size = 0;
    int i = 0;
    int cnt = 0;
    while(s[i]){
        ++i;
    }
    size = i;                                           //求得s的长度
    char *result = malloc(sizeof(char) * (size + 1));   //申请空间存储转换后的字符串
    if(numRows == 1){                                   //只有一行，直接返回源字符串
        return s;
    }
    int cycle_distance = numRows * 2 - 2;               //周期间隔
    int cycles;                                         //总周期数
    if(size == 0){                                      //空字符串时，返回空字符串
        result[0] = 0;
        return result;
    }
    if((size / cycle_distance == 0) && (size >= cycle_distance)){       //当长度大于周期间隔且长度刚好为整数个周期间隔
        cycles = size/cycle_distance - 1;
    }
    else if((size / cycle_distance != 0) || (size < cycle_distance)){   //当长度小于周期间隔或长度不为整数个周期间隔
        cycles = size/cycle_distance;
    }
    int cycle = 0;                                       //周期遍历游标
    int small,large;
    for(i = 0;i < numRows;++i){
        for(cycle = 0;cycle <= cycles;++cycle){
            small = cycle_distance * cycle + i;
            large = cycle_distance * cycle + (cycle_distance - i);
            if((small % cycle_distance == 0) || (small % cycle_distance == (numRows - 1))){     //第一行和最后一行
                if(small < size){
                    result[cnt++] = s[small];
                }
                continue;
            }
            if(small < size){                             //其余行
                result[cnt++] = s[small];
            }
            if(large < size){
                result[cnt++] = s[large];
            }
        }
    }
    result[size] = 0;
    return result;
}

总结

时间复杂度为行数乘以周期数，近似于线性级别。
空间复杂度为O（n），n为原字符串长度。
虽然逻辑无大碍，但是代码写的比较乱，看起来不够通透。原因在于设置了特殊情况以及分支逻辑没有得到整合，还需多加练习。