LeetCode-6.Z字变换-C

1.Z字型变换

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

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
1
2
3
P   A   H   N
A P L S I I G
Y   I   R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：
1
string convert(string s, int numRows);
示例 1：
1
2
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
1
2
3
4
5
6
7
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I
示例 3：
1
2
输入：s = "A", numRows = 1
输出："A"
提示：

1 <= s.length <= 1000

s 由英文字母（小写和大写）、',' 和 '.' 组成

1 <= numRows <= 1000

2.个人思路

根据提示给出的信息，他的排列很自然而然的想到使用二维数组。观测得到二维数组的行是numRows，列则是与长度和列存在着一定的关系。并且想到，可以分成一组一组来。首先就是要得到s的长度。

1	size_t len = strlen(s);

然后是组与长度的关系。

1	int group = len / (2 * numRows-2) + 1;

创建一个二维数组之后，可以看到他是往下排列的。所以可以调换i和j位置，类似于转置矩阵，这样避免填入内容顺序错乱的现象。所以首要目的就是处理排列，然后就是在相应位置填上内容。

char* convert(char* s, int numRows) {

    size_t len = strlen(s);
    int group = len / (2 * numRows-2) + 1;

    char buffer[len];


    strcpy(buffer, s);

    char *output = (char *)malloc(len + 1);

    char change[numRows][group * (numRows-1)];
    memset(change, 0, sizeof(change));

    printf("组数为:%d\n",group);

    //group = 1;

    int put_l = 0;
    for (int k = 0; k < group; ++k) {
        for (int  j= 0; j <= numRows -2 ; ++j) {   //按组处理  numRows = 4
            for (int i = 0; i <= numRows -1 ; ++i) { //  组内互换
                if( j == 0  || (i+j) == (numRows-1) )
                {
                    if(put_l == len)
                        break;
                    change[i][k * (numRows-1) + j] = buffer[put_l];
                    put_l ++;
                }
            }
        }
    }
    int lengg = 0;
    for (int i = 0; i < numRows; ++i) {
        for (int j = 0; j < group * (numRows - 1); ++j) {
            char ch = change[i][j];
            if (ch >= 32 && ch <= 126)  // ASCII 可打印字符范围
            {
                if(lengg == len)
                    break;
                printf("[%d,%d]%c ", i, j, ch);
                output[lengg] = ch;
                lengg ++;
            }
            else
                printf("[%d,%d]  ",i,j);  // 打两个空格保持对齐
        }
        printf("\n");
    }

    output[lengg] = '\0';
    //printf("%s",output);

    return output;
}

代码使用了三层for循环。提交代码的时候，发现A过不了，于是看到

1	int group = len / (2 * numRows - 2) + 1;

numRows为1的时候，就是无效的。所以就得提前处理特殊结果。然后还有出现

1	* buffer overflow detected *: terminated

错误意思是，缓冲区溢出。可以看到我代码里面都是在栈上声明，唯一一个output还是因为要输出地址，才malloc申请的。所以做了以下修改

size_t len = strlen(s);
   if (numRows <= 1 || len <= numRows) return strdup(s);
   int group = len / (2 * numRows - 2) + 1;

   char *buffer = (char *)malloc(len + 1);

   strcpy(buffer, s);

   char* output = (char*)malloc(len + 1);

加入提前退出和buffer申请在堆上。完美解决问题。

3.优化一下

可以看到使用了三个for循环，时间复杂度O(N)为造成了冗余，所以可以修改一下那个for循环

char* convert(char* s, int numRows) {
    size_t len = strlen(s);
    if (numRows <= 1 || len <= numRows) return strdup(s); // 特殊情况直接返回

    int group = len / (2 * numRows - 2) + 1; 
    int cols = group * (numRows - 1);      

    char buffer[len + 1];
    strcpy(buffer, s);

    char *output = (char *)malloc(len + 1);
    if (!output) return NULL;

    char change[numRows][cols];  
    memset(change, 0, sizeof(change));  

    int put_l = 0;
    for (int k = 0; k < group && put_l < len; ++k) {
        for (int i = 0; i < numRows && put_l < len; ++i) {
            change[i][k * (numRows - 1)] = buffer[put_l++];
        }
        for (int j = 1; j < numRows - 1 && put_l < len; ++j) {
            change[numRows - 1 - j][k * (numRows - 1) + j] = buffer[put_l++];
        }
    }
    int lengg = 0;
    for (int i = 0; i < numRows; ++i) {
        for (int j = 0; j < cols; ++j) {
            char ch = change[i][j];
            if (ch != 0) 
                output[lengg++] = ch; 
        }
    }

    output[lengg] = '\0'; // 添加字符串结束符
    return output;
}

至此，一道自己独立完成的题目完成。