LeetCode 第六题 Z字形变换（C语言）

逃离我推掉我的手 2022-04-22 13:56 150阅读 0赞

将字符串 “PAYPALISHIRING” 以Z字形排列成给定的行数：

P   A   H   N  
A P L S I  I G  
Y   I    R  
之后从左往右，逐行读取字符：“PAHNAPLSIIGYIR”

实现一个将字符串进行指定行数变换的函数:ensp

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

输入: s = “PAYPALISHIRING”, numRows = 3  
输出: “PAHNAPLSIIGYIR”

--------------------

#### 解法一：运用二维数组 ####

这个方法比较容易想到，先定义一个二维数组，然后按照顺序放进去元素，没有的置为0  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70]

char* convert(char* s, int numRows) { 
    		if (numRows >= (int)strlen(s)) {  return s; }
    		if (numRows == 1) {  return s; }
    		int i = 0, j = 0, k = 0; //i表示行，j表示列
    		char arr[1001][1001] = {  0 };//放元素的二维数组
    		char *arr1 = (char *)malloc(sizeof(char) * 1001);//返回的一维数组
    		memset(arr1, 0, 1001);
    		while (s[k]) { 
    			while (i < numRows && s[k]) {  arr[i++][j] = s[k++]; }
    			i -= 2; //表示第n-1行
    			j++;
    			while (i && s[k]) {  arr[i--][j++] = s[k++]; }
    		}
    		int ret = 0;
    		for (int m = 0; m < numRows; m++) { 
    			for (int n = 0; n < j; n++) { 
    				if (arr[m][n]) { 
    					arr1[ret++] = arr[m][n];
    				}
    			}
    		}
    		return arr1;
    	}

但上述方法的时间复杂度比较大，并且在使用二维数组的时候浪费了很多空间。

#### 解法二：找规律 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 1]

然后只需按照行来打印即可

char* convert(char* s, int numRows)
    	{ 
    		if (numRows < 2) {  return s; }
    		int len = strlen(s);
    		char *arr = (char *)malloc(sizeof(char) * (len + 1));
    		int k = 0;
    		int pos = 0;
    		//i表示行
    		for (int i = 0; i < numRows; i++)
    		{ 
    			//j表示块
    			for (int j = 0; j < len / (2 * numRows - 2) + 2; j++)
    			{ 
    				//pos表示一列的下标
    				//pos1表示斜着的元素的下标
    				pos = j * (2 * numRows - 2) + i;
    				int pos1 = pos - 2 * i;
    				if (pos1 >= 0 && pos1 < len && i != 0 && i != numRows - 1)
    				{ 
    					arr[k++] = s[pos1];
    				}
    				if (pos < len)
    				{ 
    					arr[k++] = s[pos];
    				}	
    			}
    		}
    		arr[k] = 0;
    		return arr;
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70]: /images/20220422/11f2d36ec96846dfbf520614a009643f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 1]: /images/20220422/b8256e6e7fb94d2aacd880a7f838da31.png