[力扣_6] Z 字形变换

题目入口：点击进入

相关算法：

• 暴力破解——时间复杂度O((numRowssleng)²),空间复杂度O(numRowsleng)

• 按行迭代——时间复杂度O(numRowssleng),空间复杂度O(numRowsleng)

  • 以上只对C做分析

思路和算法：

这题有个明显的规律，字符串是以下列顺序存放在二维数组中：

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

从上我们可以发现，只有在达到顶端和末端的时候，列数才会进行改变

• 在行数为0的时候，列数不变，行递增
• 在行数为numRows-1的时候，行数递减，列数递增

这样我们可以开一个二维数组，遍历整个字符串，初始条件行列值都为0，做以判断，如果行数为0的时候，则行数不断增1.列数不变，如果行数为numRows-1的时候，行数不断减1。

同时，在行数不断减1的时候，列数要不断递增，这样去存储。

为了规避所有情况，我们将二维数组所有空间赋值空字符，最后遍历一遍二维数组一行一行的存储到一个新的字符里边即可

代码如下：

char * convert(char * s, int numRows){
    if(numRows==1)//判断特殊情况
    {
        return s;
    }
    int sleng=strlen(s);
    int TwoArray[numRows][sleng];//开二维数组
    for(int i=0;i<numRows;i++)
    {
        for(int j=0;j<sleng;j++)
        {
            TwoArray[i][j]='\0';//初始化二维数组
        }
    }
    int Colnum=0,Rownum=0,sign;//行列以及标记

    for(int i=0;i<sleng;i++)
    {
        TwoArray[Rownum][Colnum]=s[i];
        if(Rownum==0)
        {
            sign=1;
        }
        if(Rownum==numRows-1)
        {
            sign=-1;
        }
        if(sign==-1)
        {
            Colnum++;
        }
        Rownum+=sign;
    }
  
    char *ReturnArray=(char*)malloc(sizeof(char)*sleng+1);
    int p=0;
    for(int j=0;j<numRows;j++)
    {
        for(int k=0;k<sleng;k++)
        {
           if(TwoArray[j][k]!='\0')
           {
               ReturnArray[p]=TwoArray[j][k];
               p++;
           }
        }
    }
    ReturnArray[sleng]='\0';
    return ReturnArray;
}

我们可以看到，这样的话，虽然思路清晰，但是额外的空间以及时间就会多很多，那么我们从此优化就得出了解法二

按行迭代

通过暴力解法我们已经得知了字符串变化的存储规律，我们可以开一个字符串数字，通过numRows来确定开几个，然后通过行的变化来确定字符串附加到哪个数组中的那个字符串后边。

如同上述，当Rownum==0的时候，Rownum不断递增，当Rownum==numRows-1的时候，Rownum不断递减。

字母方向就是：

图解如下：

因为C语言，所以我们还需要实现append函数进行对每一个字符串后面附加字符的功能

同时在采用字符串数组的时候可以采用链式存储也可以采用顺序存储，为了方便操作，我这边使用的是顺序存储，代码如下：

void Append(char *s,char a)//附加字符
{
    int i=0;
    while(s[i]!='\0')
    {
        i++;
    }
    s[i]=a;
    s[i+1]='\0';
}
char * convert(char * s, int numRows){
    int sleng=strlen(s);
    if(numRows==1)//特殊情况
    {
        return s;
    }
    int sign,Rownum=0;
    char ZArray[numRows][sleng];
    for(int i=0;i<numRows;i++)
    {
        ZArray[i][0]='\0';//初始化
    }
    for(int i=0;i<sleng;i++)
    {
        Append(*(ZArray+Rownum),s[i]);
        if(Rownum==0)
        {
            sign=1;//标记向量
        }
        if(Rownum==numRows-1)
        {
            sign=-1;
        }
        Rownum+=sign;
    }
    char *ReturnArray=(char*)malloc(sizeof(char)*(sleng+1));
    int p=0;
    for(int i=0;i<numRows;i++)
    {
        int j=0;
        while(*(*(ZArray+i)+j)!='\0')
        {
           ReturnArray[p]=ZArray[i][j];
           p++;
           j++;
        }
    }
    ReturnArray[p]='\0';
    return ReturnArray;
}

本文链接：