【LeetCode题解-006】Zigzag Conversion
【LeetCode题解-006】Zigzag Conversion
今日金句
发表于苍穹盛夏
查看:13500回复:135
“如果你认为你的价值在于自己所知道的多少，你就大错特错了。要不了多少年，你今天的知识就没什么价值了。你的价值体现在你能学多少，以及你对这个职业常常带来的改变的适应程度。”
– Jose M. Aguilar
友情提醒：文章代码格式不佳的朋友们可以点击下方阅读原文
1题目
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 s, int numRows);Example 1:
Input: s = "PAYPALISHIRING", numRows = 3Output: "PAHNAPLSIIGYIR"Example 2:
Input: s = "PAYPALISHIRING", numRows = 4Output: "PINALSIGYAHRPI"Explanation:P I N
A L S I G
Y A H R
P IContributor
2翻译
把字符串上下上下走之字形状,然后按行输出,比如包含数字0~22的字符串, 给定行数为5
3解法一
这道题就是看坐标的变化，并且需要分块处理。
n=2时，字符串坐标变成zigzag的走法就是：
0 2 4 6
1 3 5 7
n=3时的走法是：
0 4 8
1 3 5 7 9
2 6 10
n=4时的走法是：
0 6 12
1 5 7 11 13
2 4 8 10 14
3 9 15
可以发现规律，画红色的长度永远是 2n-2 （想法是你试想把所有这些行压缩成两列，两边手挤一下，第二列永远的第一行和最后一行少字）。
利用这个规律，可以按行填字，第一行和最后一行，就是按照2n-2的顺序一点点加的。
其他行除了上面那个填字规则，就是还要处理斜着那条线的字，可以发现那条线的字的位置永远是当前列j+(2n-2)-2i(i是行的index）。
按照上面的规律就可以写出代码了。代码如下：
public static String convert(String s, int numRows) {
if(s == null || s.length()==0 || numRows <=0) {
return "";
}
if(numRows == 1) {
return s;
}
StringBuilder res = new StringBuilder();
int size = 2*numRows-2;
for(int i=0;i<numRows;i++){
for(int j=i;j<s.length();j+=size){
res.append(s.charAt(j));
if(i != 0 && i != numRows - 1){
int temp = j+size-2*i;
if(temp<s.length()) {
res.append(s.charAt(temp));
}
}
}
}
return res.toString();
}
4解法二
首先，题目中给出了几个比较关键的东西：
（1）给定了行数；
（2）Z形的这种字符串应该分两种情况处理；第一种是“垂直”部分，即题目例子中第一列“PAY”，第三列“ALT”这种；第二种就是”斜线“的，如”YPA“和”ISH“这种类型的。
根据以上思路，可以得到如下代码：
public String convert(String s, int numRows) {
char[] c = s.toCharArray();
int len = c.length;
StringBuffer[] sb = new StringBuffer[numRows];
for (int i = 0; i < sb.length; i++) sb[i] = new StringBuffer();
int i = 0;
while (i < len) {
for (int idx = 0; idx < numRows && i < len; idx++) // vertically down
sb[idx].append(c[i++]);
for (int idx = numRows-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]);
return sb[0].toString();
}
看一下while循环中的for循环，第一个for循环处理的是”垂直“部分，非常容易理解；第二个就稍微难一点，”斜线“部分的第一个和最后一个元素我们都是不需要在这里处理的，应该直接用”垂直“部分处理第一个元素和最后一个元素。那剩下的部分就是第二个元素和倒数第二个元素以及他们之中的部分，这个范围是什么？这个范围就是大于等于1小于等于行数减2（因为行数减1是最后一个元素）。
while循环结束，将分散的stringbuffer类型的数组整合成一个stringbuffer对象，然后直接使用toString转化成String类型返回即可。
以上代码会同步更新在本人的Github和CSDN上
Github地址：https://github.com/Bylant/LeetCode