zigzag 經典面試題

題目描述：

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H NA P L S I I GY I R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

這道題目的具體意思就是，給了一個string這個string的寫法十分怪異，具體的表現就是我們的字元串是從上到下寫，然後在第二列放下一個字母，然後以此類推，從上面的例子中可以看出來。

題目思路：

那麼現在題目的思路也就很清晰了，首先我們把手裡的字元串轉換成題目描述的例子字元串的樣子，具體的做法就是使用n個stringbuffer（n是題目中的要求一個參數），然後分兩個for loop分別從上和從下面開始去掃這三個stringbuffer，每次掃的時候就要把手裡的字元串給賦值進去，到了邊界之後再去第二列的賦值。以此類推，最後將三個是 tiring buffer合併起來從上到下的一個個將裡面的字元讀取出來。

Java代碼：

public String convert(String s, int nRows) { char[] c = s.toCharArray(); int len = c.length; StringBuffer[] sb = new StringBuffer[nRows]; ／／創建一個頭sb（例子中的） for (int i = 0; i < sb.length; i++) sb[i] = new StringBuffer();／／頭sb下面再掛上三個sb 想像一下掛窗帘 int i = 0; while (i < len) { for (int idx = 0; idx < nRows && i < len; idx++) // vertically down sb[idx].append(c[i++]); ／／第一列向下 for (int idx = nRows-2; idx >= 1 && i < len; idx--) // obliquely up sb[idx].append(c[i++]);／／第二列中間放一個 } for (int idx = 1; idx < sb.length; idx++) sb[0].append(sb[idx]);／／最後將三個sb中的char合併起來 return sb[0].toString();}

Time complexity：

O（N）

推薦閱讀：