(六) ZigZag Convert
摘要：
題目
將一個給定字串根據給定的行數，以從上往下、從左到右進行 Z 字形排列。
比如輸入字串為"LEETCODEISHIRING"
行數為 3 時，排列如下：
LCIR
E T O E S I I G
EDHN
...
題目
將一個給定字串根據給定的行數，以從上往下、從左到右進行 Z 字形排列。
比如輸入字串為"LEETCODEISHIRING"
行數為 3 時，排列如下：
LCIR E T O E S I I G EDHN
之後，你的輸出需要從左往右逐行讀取，產生出一個新的字串，比如："LCIRETOESIIGEDHN"
。
請你實現這個將字串進行指定行數變換的函式：
string convert(string s, int numRows);
示例 1:
輸入: s = "LEETCODEISHIRING", numRows = 3 輸出: "LCIRETOESIIGEDHN"
示例 2:
輸入: s = "LEETCODEISHIRING", numRows = 4 輸出: "LDREOEIIECIHNTSG" 解釋: LDR EO EI I E CI HN TSG
解答
ABCDEFGHIJKLMNOPQ 4 AHN BG IM O C FJ LP DKQ
首先將字元按照Z字型排列起來，之後按照第一行到最後一行在組成串:AHNBGIMOCFJLPDKQ。我們可以看到第一行和最後一行的字母的下標是呈現出一個等差數列,根據關係觀察很容易就可以發現這等差數列的差值是:
實際上我們發現除了第一行和最後一行，其它行之中依舊存在等差數列，如在第二行中(B,I,O)同樣其標也是呈現這樣的等差關係，那麼實際其實要解決這道題就只剩下最後一個問題了就是解決兩個等差數中間的那個數的座標（如BI之間G的座標)。我們很容易就可以發現它的左邊和其前一個數的間隔為
C語言
char* convert(char* s, int numRows) {
if(s== NULL || numRows < 1)
return s;
int len = strlen(s);
if(len == 0)
return s;
char *res = (char *)malloc(sizeof(char)*(len+1));
res[len] = '\0';
if(numRows == 1)
{
strcpy(res,s);
return res;
}
int m = 0;
int inter1 = 2 * numRows -2;
for(int i = 0;i < numRows;i++){
if(i == 0 || i== numRows-1){
for(int j = i;j < len;j += inter1)
res[m++] = s[j];
}else{
int inter2 = 2 * i;
for(int j = i;j < len;j+=inter2){
res[m++] = s[j];
inter2 = inter1-inter2;
}
}
}
return res;
}
Golang
func convert(s string, numRows int) string {
if len(s) <= 1 || numRows == 1 {
return s
}
res := make([]byte, len(s))
inter1 := 2*numRows - 2
m := 0
for i := 0; i < numRows; i++ {
inter2 := 2 * i
for j := i; j < len(s); j += inter2 {
res[m] = s[j]
m++
if i == 0 || i == numRows-1 {
inter2 = inter1
} else {
inter2 = inter1 - inter2
}
}
}
return string(res)
}