C语言解决 Z字形变换(力扣第6题)

Source

将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"

6. Z 字形变换 - 力扣(LeetCode) (leetcode-cn.com)

上面的图不容易观察画成下面这样的就明显多了:

 解决思路:

先用一个二维数组来接收原数组变形后的,题中给出了二维数组的行,要自己计算二维数组的列;最后开辟一个目标数组,从二维数组头依次向目标数组赋值;

解题步骤如下:

计算出给定字符串的长度(len),以便于计算开辟二维数组的列数,列数分为两种情况;如下:

int numLines;   //算列数
if((len-numRows)%(numRows-1)==0)//第一列全部都有字符,其它列总会有一个为空(或最上或最下)
{
    numLines = (len-numRows)/(numRows-1)+1;
}
else{
    numLines = (len-numRows)/(numRows-1)+2;
}

算好列,就建立一个二维数组,并将原数组按照格式摆放进二维数组;

    char chMap[numRows][numLines];
    memset(chMap,0,sizeof(chMap));//把二维数组初始化为0
    int i = 1;  //第一个字符直接赋值从第二个开始
    int row = 0,line = 0;
    while(line<numLines){
        if(line%2==0){  //偶数列从上到下
            row = 1;//从上往下最上面总是空,所以从第二个开始往下
            while(s[i] && row<numRows)//一边控制原字符串不到最后,一边控制行数
            { 
                chMap[row][line] =s[i];
                i++;
                row++;
            }
        }else{      //奇数列从下到上
            row = numRows-2;//从下往上最下面总是空,所以从倒数第二个开始往上
            while(row>=0 && s[i])//一边控制原字符串不到最后,一边控制行数
            {
                chMap[row][line] =s[i];
                i++;
                row--;
            }
        }
        line++;
    }

最后设置目标数组,把二维数组赋值给目标数组;首元素直接赋值,二维数组和目标数组都是从第二个开始,最后把目标数组最后赋值‘\0’(字符串结束标志)

源代码如下:

char * convert(char * s, int numRows)
{
    int len = strlen(s);
    if(len<=2||numRows<=1)
        return s;    //特殊情况

    int numLines;   //算列数
    if((len-numRows)%(numRows-1)==0)
    {
        numLines = (len-numRows)/(numRows-1)+1;
    }
    else
    {
        numLines = (len-numRows)/(numRows-1)+2;
    }

    char chMap[numRows][numLines];
    memset(chMap,0,sizeof(chMap));
    int i = 1;  //第一个字符直接赋值从第二个开始
    int row = 0,line = 0;
    while(line<numLines)
    {
        if(line%2==0)//偶数列从上到下
        {
            row = 1;
            while(s[i] && row<numRows)
            { 
                chMap[row][line] =s[i];
                i++;
                row++;
            }
        }
        else//奇数列从下到上
        { 
            row = numRows-2;
            while(row>=0 && s[i])
            {
                chMap[row][line] =s[i];
                i++;
                row--;
            }
        }
        line++;
    }

    char *a = (char *)malloc(len+1);
    a[0] = s[0];
    i = 1;
    for(row = 0;row<numRows;row++)//二维数组写入一维数组
    {
        for(line = 0;line<numLines;line++)
        {
            if(chMap[row][line])//不为0时,往下执行
            {
                a[i] = (char)chMap[row][line];
                i++;
            }  
        }
    }
    a[len] = '\0';
    return a;
}