leetcode-6. Z 字形變換，
將一個給定字串根據給定的行數，以從上往下、從左到右進行Z字形排列，
請實作這個將字串進行指定行數變換的函式：char *convert( char *s, int numRows );
示例 1:
輸入: s = "LEETCODEISHIRING", numRows = 3
輸出: "LCIRETOESIIGEDHN"
解釋:
L C I R
E T O E S I I G
E D H N
示例 2:
輸入: s = "LEETCODEISHIRING", numRows = 4
輸出: "LDREOEIIECIHNTSG"
解釋:
L D R
E O E I I
E C I H N
T S G
示例 3:
輸入: s = "PAYPALISHIRING", numRows = 4
輸出: "PINALSIGYAHRPI"
解釋:
P I N
A L S I G
Y A H R
P I
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/zigzag-conversion/
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
char *convert( char *s, int numRows ) {
char *tempA = NULL;
int i = 0, r = 0, c = 0, up = 0;
int col = strlen( s );
if( numRows < 2 || numRows == col ) {
return s;
}
tempA = calloc( sizeof(*tempA), numRows * col );
for( i = 0; s[i] != '\0'; ++i ) {
tempA[r * col + c] = s[i];
if( !up ) {
if( r == numRows - 1 ) {
// 從上往下走,到最后一個位置時.
r = numRows - 2;
++c;
up = 1;
} else {
++r;
}
} else {
if( r == 0 ) {
// 從下往上走,到最后一個位置.
r = 1;
up = 0;
} else {
--r;
++c;
}
}
}
for( i = r = 0; r < numRows; ++r ) {
for( c = 0; c < col; ++c ) {
if( tempA[r * col + c] != '\0' ) {
s[i++] = tempA[r * col + c];
}
}
}
free( tempA );
return s;
}
用上面的示例3進行解釋: 輸入: s = "PAYPALISHIRING", numRows = 4, 輸入: "PINALSIGYAHRPI".
根據示例3明顯得到: P、I、N 位于第1(下標0)行,
A、L、S 、I、G 位于第2(下標1)行,
Y、A、H、R 位于第3(下標2)行,
P、I 位于第4(下標3)行.
可以把每一行看做為獨立的容器，
當遍歷計算得到每個字符所位于的行，就將字符加入到對應的容器中，例如：將 P、I、N 加入到容器1中,將 P、I 加入到容器4中.
遍歷結束時得到: 容器1包含P、I、N, 容器1包含A、L、S、I、G, 容器1包含Y、A、H、R, 容器1包含P、I.
把每個容器依次拼接得到 "PINALSIGYAHRPI", 即是最終結果.
參考: https://leetcode-cn.com/problems/zigzag-conversion/solution/zzi-xing-bian-huan-by-jyd/
char *convert( char *s, int numRows ) {
char *tempA = NULL;
int *column = NULL;
int i = 0, r = 0, c = 0, up = 0, col = strlen( s );
if( numRows < 2 || numRows == col ) {
return s;
}
tempA = malloc( sizeof(*tempA) * numRows * col );
column = calloc( sizeof(*column), numRows );
for( i = 0; s[i] != '\0'; ++i ) {
tempA[r * col + column[r]++] = s[i];
if( !up && ++r == numRows ) {
r = numRows - 2;
up = 1;
} else if( up && --r < 0 ) {
r = 1;
up = 0;
}
}
for( r = 0; r < numRows; ++r ) {
tempA[r * col + column[r]] = '\0';
}
free( column );
s[0] = '\0';
for( r = 0; r < numRows; ++r ) {
strcat( s, &tempA[r * col] );
}
free( tempA );
return s;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/24374.html
標籤：C
下一篇：leetcode-7. 整數反轉