LeetCode -- 6. ZigZag Conversion
題目描述
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 N
A P L S I I G
Y I RAnd 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".
題意解析
題目的大致意思是將給定的原字符串"PAYPALISHIRING"通過一個** 給定的行數(shù) 攜程如下這中 Z型模式： **
P A H N
A P L S I I G
Y I R
然后一行一行的讀取：“PAHNAPLSIIGYIR”
寫代碼讀入一個字符串并通過給定的行數(shù)進行這個轉(zhuǎn)換：
string convert(string text, int nRows);
調(diào)用convert("PAYPALISHIRING",3)费什，應該返回"PAHNAPLSIIGYIR"膊毁。
如果還沒偶明白題意耿戚，我們可以觀看下圖：
了解完題目的意思后疙描，我們現(xiàn)在就可以開始思考如何用程序?qū)崿F(xiàn)合陵。
第一種方法
我個人認為比起先說算法思想氮唯，不如先貼上算法思想對應的算法代碼轧简，這樣你看完之后膝舅，可能不需要看算法思想就立馬明白了怎么回事嗡载，即使不明白，帶著問題去看算法思路仍稀，也是比較好的一種學習方法洼滚。
算法實現(xiàn)
public static String convert_easy_understand(String s, int nRows) {
// 將字符串轉(zhuǎn)換成字符數(shù)組，便于取出制定位置字符
char c[] = s.toCharArray();
// 字符串長度
int len = c.length;
// 建立長度為nRows的字符串數(shù)組技潘，以nRows=4為例
StringBuffer sb[] = new StringBuffer[nRows];
// 按照ZigZag模式排列遥巴，總共有四行，可以看下圖享幽，
// 每一行用一個字符串存儲铲掐，最后四個字符串按照順序輸出既是答案
for (int i = 0; i < nRows; i++) {
sb[i] = new StringBuffer();
}
// 用變量 i 表示現(xiàn)在應該取出字符數(shù)組中的第幾個字符
int i = 0;
while (i < len) {
// 字符串索引j值從0開始，即從首行開始值桩，那么索引值每次加1
for (int j = 0; j < nRows && i < len; j++) {
sb[j].append(c[i++]);
}
// 字符串索引j值從nRows=n-2開始摆霉，即從倒數(shù)第二行開始，那么索引值每次減1
for (int j = nRows - 2; j >= 1 && i < len; j--) {
sb[j].append(c[i++]);
}
}
// 將四個字符串按照順序連接成一個字符串
for (int j = 1; j < sb.length; j++) {
sb[0].append(sb[j]);
}
return sb[0].toString();
}
算法思想
我們現(xiàn)將原字符串轉(zhuǎn)換成字符數(shù)組c[]={ 'P' ,'A' ,'Y' ,'P' ,'A' ,'L' ,'I' ,'S' ,'H' ,'I' ,'R' ,'I' ,'N' ,'G' };以nRows=4為例，那么按照** "ZigZag" **的排序規(guī)則斯入，如下圖：
如上圖砂碉，總共四行，那么我們可以先建一個長度為nRows=4的字符串數(shù)組：
// 建立長度為nRows的字符串數(shù)組刻两，以nRows=4為例
StringBuffer sb[] = new StringBuffer[nRows];
// 按照ZigZag模式排列增蹭，總共有四行，可以看下圖磅摹，
// 每一行用一個字符串存儲滋迈，最后四個字符串按照順序輸出既是答案
for (int i = 0; i < nRows; i++) {
sb[i] = new StringBuffer();
}
sb[0]存儲第一行字符，即sb[0] = { "P" ,"I" ,"N" }户誓；sb[1]存儲第二行字符饼灿，即sb[1] = { "A" ,"L" ,"S" ,"I" ,"G" }；sb[2]存儲第三行字符帝美，即sb[2] = { "Y" ,"A" ,"H" ,"R" }碍彭；sb[3]存儲第四行字符，即sb[3] = { "P" ,"I" }悼潭。
我們一共有四個字符串庇忌，sb[0] ,sb[1] ,sb[2] ,sb[3]，最終所有的字符會分別歸屬為上面四個字符串舰褪。那么我們按照上圖中箭頭的順序依次檢索原字符串中的字符皆疹，那么按照字符的歸屬字符串順序為：sb[0] ,sb[1] ,sb[2] ,sb[3] ,sb[2] ,sb[1] ,sb[0] ,sb[1] ,sb[2] ,sb[3] ....... 。
如果 nRows=n時占拍，即：sb[0] ,sb[1] , .... ,sb[n-1] ,sb[n-2] ,sb[n-3] , ..... ,sb[1] ,sb[0] ,sb[1] ......略就， 即字符串索引為首行時，每次循換字符串索引+1晃酒，當字符串索引到了最后一行時表牢，即索引值為nRows=n-1時，字符串索引每次循環(huán)再減1.
代碼實現(xiàn)為：
// 用變量 i 表示現(xiàn)在應該取出字符數(shù)組中的第幾個字符
int i = 0;
while (i < len) {
// 字符串索引j值從0開始掖疮，即從首行開始初茶，那么索引值每次加1
for (int j = 0; j < nRows && i < len; j++) {
sb[j].append(c[i++]);
}
// 字符串索引j值從nRows-2開始，即從倒數(shù)第一行開始浊闪，那么索引值每次減1
for (int j = nRows - 2; j >= 1 && i < len; j--) {
sb[j].append(c[i++]);
}
}
所以經(jīng)過以上算法恼布，字符串中的所有字符就分別在sb[0],sb[1],sb[2],sb[3]中了，下面我們只需將這個四個字符串按照順序連接成一個字符串搁宾，該字符串就是我們所求字符串折汞，程序如下：
// 將四個字符串按照順序連接成一個字符串
for (int j = 1; j < sb.length; j++) {
sb[0].append(sb[j]);
}
return sb[0].toString();
第二種方法
第二種方法與第一種方法算法思路一樣，只是實現(xiàn)起來有點不同盖腿，現(xiàn)在提供代碼爽待，自行參考损同。
算法實現(xiàn)
public static String convert_Three(String s, int numRows) {
if (numRows <= 1) return s;
StringBuilder[] sb = new StringBuilder[numRows];
for (int i = 0; i < sb.length; i++) {
sb[i] = new StringBuilder(""); //init every sb element **important step!!!!
}
int incre = 1;
int index = 0;
for (int i = 0; i < s.length(); i++) {
sb[index].append(s.charAt(i));
// 當為首行時，index應該是遞加鸟款，每次加1
if (index == 0) {
incre = 1;
}
// 當為最后一行時膏燃，index應該每次減1
if (index == numRows - 1) {
incre = -1;
}
index += incre;
}
String re = "";
for (int i = 0; i < sb.length; i++) {
re += sb[i];
}
return re.toString();
}
第三種方法
第三種方法我先把算法思路寫在前面是因為，相比較第一種方法何什，第三種方法看一遍后如果不自己動手演算组哩，無法明白為什么這樣實現(xiàn)，所以我先把算法思路寫在前面处渣，這樣看算法時會比較輕松伶贰。
算法思路
下面我們以nRows=4為例，當nRows=4時罐栈，原字符串“Z型模式”如下圖：
然后一行一行的讀仁蜓谩：“PAHNAPLSIIGYIR”，那么我們現(xiàn)在來探討每一行相鄰字符在原字符串中的位置關(guān)系：
- 第0行：0 6 12
- 第1行：1 5 7 11 13
- 第2行：2 4 8 10
- 第3行：3 9
第0行和第3行中每行相鄰字符的位置差為(4-1)2*
第1行相鄰字符位置差為(4-1-1)2荠诬、12琅翻、(4-1-1)2、12浅妆，即按照(4-1-1)2望迎、12**位置差規(guī)律進行排序障癌；
第2行相鄰字符位置差為(4-2-1)2凌外、22、(4-2-1)2涛浙、22康辑，即按照(4-2-1)2、22**位置差規(guī)律進行排序轿亮；
那么我們可以觀察出規(guī)律第0行和第3行每行相鄰字符位置差可以寫成(4-0-1)2疮薇、02、(4-0-1)2我注、02按咒，即按照(4-0-1)2、02**的位置差規(guī)律進行排序但骨，那我們可以總結(jié)出以下的規(guī)律：
<font color="red">以字母 i記為當前為第幾行励七，那么我們就可以總結(jié)出每行字符排列的規(guī)律：(nRows - i - 1) * 2、i * 2交叉排序</font>
所以設(shè)置兩個變量step1奔缠、step2分別用來表示(nRows - i - 1) * 2掠抬、i * 2，所以程序代碼如下：
int step1, step2;
int len = s.length();
// 字符串按照每行進行處理
for (int i = 0; i < nRows; ++i) {
step1 = (nRows - i - 1) * 2;
step2 = (i) * 2;
// pos用來表示每行字符位置
int pos = i;
// 處理每行第一個字符
if (pos < len)
result += c[pos];
// 處理每行除了第一個字符外的所有字符
while (true) {
pos += step1;
if (pos >= len)
break;
// 該條件是為了防止將同一個位置的字符添加兩次
if (step1 != 0)
result += c[pos];
pos += step2;
if (pos >= len)
break;
// 該條件是為了防止將同一個位置的字符添加兩次
if (step2 != 0)
result += c[pos];
}
}
return result;
如果還不是太懂校哎，自己可在紙上按照程序步驟親自動手演算一遍两波，這樣你就能很清楚的了解算法思路。
算法實現(xiàn)
public static String convert_Two(String s, int nRows) {
String result = "";
// 將字符串轉(zhuǎn)換成字符數(shù)組，便于取出制定位置字符
char c[] = s.toCharArray();
// 如果行數(shù)只為1礁遵，那么就是原字符串
if (nRows == 1)
return s;
int step1, step2;
int len = s.length();
// 字符串按照每行進行處理
for (int i = 0; i < nRows; ++i) {
step1 = (nRows - i - 1) * 2;
step2 = (i) * 2;
int pos = i;
// 處理每行第一個字符
if (pos < len)
result += c[pos];
// 處理每行除了第一個字符外的所有字符
while (true) {
pos += step1;
if (pos >= len)
break;
if (step1 != 0)
result += c[pos];
pos += step2;
if (pos >= len)
break;
if (step2 != 0)
result += c[pos];
}
}
return result;
}
總結(jié)
我盡量做完一道算法題阳谍，都將自己的實現(xiàn)的還有一些別人實現(xiàn)的，也是比較好的算法給記錄下來劣坊，對自己也算一種鍛煉馏臭，如果還能幫助別人那是再好不過了，如有錯誤讼稚，或者描述不當之處請諒解括儒，語言組織能力不太好，一些算法思想可能不能很好的描述出來锐想，如果有什么差錯的地方帮寻，歡迎大家指正！
