題目要求
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)??
示例圖??convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR"
??題目翻譯：給定一個(gè)字符串监憎，按給定的行數(shù)自上而下排列之字型，如下圖茸俭。輸出結(jié)果是遍歷每一行把字符拼接成的字符串
題目分析
如下圖的猛，把之字型的串劃分為一系列子部分，每一個(gè)子部分具有相同的結(jié)構(gòu)：
結(jié)構(gòu)圖
- 長度為 2*(numLows-1)
- 首行和尾行只有一個(gè)字符氛雪，其它行均有兩個(gè)字符
- 假設(shè)某一個(gè)子部分的首元素在原字符串是S[m]房匆，則
?? 第一行的字符是 s.charAt(m)
?? 最后一行的字符是 s.charAt(m+numLows-1)
?? 第 i 行的兩個(gè)字符分別是s.charAt(m+i-1)和 s.charAt(m+2*numRows-i-1)
偽代碼
- 將每一個(gè)子部分的首元素下標(biāo)(如上圖畫紅框的點(diǎn))存入數(shù)組
- 從第一行開始到第numLows行循環(huán)：
??在每一行，循環(huán)取出每一個(gè)子部分报亩，取出該子部分該行的字符：
????在該行該子部分浴鸿，通過判斷首尾行及邊界，取出字符弦追，存入結(jié)果字符串
代碼實(shí)現(xiàn)
package com.linsiyue;
public class Solution {
public String convert(String s, int numRows) {
StringBuilder res = new StringBuilder("");
if (numRows==1) return s;
int numParts=s.length()/(2*numRows-2), y=s.length()%(2*numRows-2);
if (y!=0) numParts+=1;
int[] arr = new int[numParts];
// 存儲(chǔ)每一個(gè)子部分的首元素下標(biāo)
for (int i = 0; i < arr.length; i++) {
arr[i]=i*2*(numRows-1);
}
// 循環(huán)遍歷每一行
for (int i=1; i<=numRows; i++){
// 循環(huán)遍歷每一個(gè)子部分
for (int j = 0; j < arr.length; j++) {
int m = arr[j];
if (i==1) {
res.append(s.charAt(m));
} else if (i==numRows){
if (m+numRows-1<s.length())
res.append(s.charAt(m+numRows-1));
} else {
if (m+i-1<s.length())
res.append(s.charAt(m+i-1));
if (m+2*numRows-i-1<s.length())
res.append(s.charAt(m+2*numRows-i-1));
}
}
}
return res.toString();
}
}
