题目：
将字符串 "PAYPALISHIRING" 以Z字形排列成给定的行数：
P A H NA P L S I I GY I R复制代码
之后从左往右，逐行读取字符："PAHNAPLSIIGYIR"
实现一个将字符串进行指定行数变换的函数:
string convert(string s, int numRows); 示例 1:
输入: s = "PAYPALISHIRING", numRows = 3 输出: "PAHNAPLSIIGYIR" 示例 2:
输入: s = "PAYPALISHIRING", numRows = 4 输出: "PINALSIGYAHRPI" 解释:
P I NA L S I GY A H RP I复制代码
思路1：按行排序
-
题目要求有两个，一个是字符是按Z字形排序，一个由上而下按行输出。
-
分析下Z字形的排序规律。z字形先是由上而下，到了底部再向上，每到底部或者顶部就会反弹，程序中使用bool变量lineUp记录方向。遍历字符的同时，使用一个二维数组int a[row][strlen(s)]来存储行与元素原始下标的关系。遍历完毕后，按行拼接字符串并输出。
-
元素的下标与输出后所在的行有这样的对应关系。
#row #数字对应元素下标。 0 0P 6I 12N 1 1A 5L 7S 11I 13G 2 2Y 4A 8H 10R 3 3P 9I 复制代码
-
代码
char* convert(char* s, int numRows) {if (numRows == 1) { return s;}bool lineUp = true;int len = strlen(s);//记录字符的二维数组。其实可以使用int的二维数组，因为字符能自动转成asscii对应的int数字。char **pArr = (char**)malloc(sizeof(char*) * numRows);//这个数组是为了记录当前行最大下标，用于后面遍历。其实可以不用，在记录字符串的时候末尾添加'\0'用于判断就行。int *indexArr = (int*)malloc(sizeof(int) * numRows);memset(indexArr, -1, sizeof(int) * numRows);for (int i = 0; i < numRows; i++ ) {//开始的时候设置长度为len 。在leetcode上执行报超出内存限制。分析后改为len /2 + 1,因为两行的时候最多为len / 2 + 1；超过三行字符被分散到其他行行，也不会超过len /2 + 1。修改后执行通过。 char *a = (char*)malloc(sizeof(char*) * (len / 2 + 1)); memset(a, '#', sizeof(char*) * (len / 2 + 1)); pArr[i] = a;}int j = 0;for (int i = 0; i < len; i ++) { int currentIndex = indexArr[j] + 1; indexArr[j] = currentIndex; pArr[j][currentIndex] = s[i]; if (lineUp) { if (j == numRows - 1) { j --; lineUp = false; } else { j ++; } } else { if (j == 0) { j ++; lineUp = true; } else { j --; } }}char *p = (char*)malloc(sizeof(char*) * len);memset(p, 0, sizeof(char*) * len);int jj = 0;for (int ii = 0; ii < numRows ; ii ++){ char *temp = pArr[ii]; for (int k = 0; k <= indexArr[ii]; k++) { p[jj++] = temp[k]; }}free(pArr);free(indexArr);return p;}复制代码 -
复杂度分析
- 时间复杂度 O(n), n = strlen(s);
- 空间复杂度 O(n)。
思路2：按行访问
-
这个是对字符输入的方式分析后得出的数学规律。首尾两行成等比关系，中间的行除了等比的位置填充元素外，另外还需要在等比距离倒退一定长度offset的位置填充，offset = currentRow。
-
代码
``` char* convert(char* s, int numRows) { int len = strlen(s); //特殊情况特殊处理 if (len == 0 || numRows == 0 || numRows == 1 || numRows == len) { return s; } char *p = (char*)malloc(sizeof(char) * len); //等比间隔 int cycleLen = 2 * numRows - 2; int pIndex = 0; for (int i = 0 ; i < numRows; i ++) { for (int j = 0; j + i < len ; j += cycleLen) { //获取等比位置的字符 p[pIndex ++] = s[i + j]; //获取中间行非等比位置的字符 if (i != 0 && i != numRows - 1 && j + cycleLen - i < len) { p[pIndex ++] = s[ j + cycleLen - i]; } } } return p; } ```复制代码 -
复杂度分析
- 时间复杂度 O(n), n = strlen(s);
- 空间复杂度 O(n)。如果返回字符不视为额外空间，那么空间复杂度为O(1)。
小结：
- 这道题开始也是用分析规律的方法去做，但举的例子少了点，写出来运行才发现规律是错的。后面也就没继续找数学规律。 为了避免下次犯错，找规律需要论证不少于3个例子。同时规律需要分情况讨论，例如该题的首尾两行作为一类，中间行作为一类。另外别想着用简单的规律就能处理全部问题，一般这类问题都是二级或者多级的，例如多种情况对应不同的规律，或者同一个规律要处理的多个问题。还有如果一类问题按，一般会存在规律。
- 注意的地方：二维数组初始化问题；meset的使用；字符串、ASCII码、int之间的关系等。
- 部分代码可以写的更简洁，但为了更好的描述过程，暂时还是保持这个风格，有利于学习和理解。
待完善L('ω')┘三└('ω')｣....