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 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"
.
解题思路
这道题的难点在于通过题目描述很难理解zigzag的遍历顺序。为此笔者在网上找到一张比较形象的图,如下:
接下来这道题的难度是找规律,从图中可以看到,首行和尾行相邻两个元素之间的距离是2*(numRows - 1)
首行和尾行之间的其他行除了像首位两行一样有间隔距离2*(numRows - 1)
的元素,如,1,7和2,8,在它们之间还有一个元素,该元素到该行下一个元素的距离为2*i
,i
为所在行数,所以到上一个元素的距离为2*(numRows -1) - 2*i
。
注意事项
注意理解题目的意思,注意边界条件。
参考答案
public class Solution { public String convert(String s, int nRows) { int length = s.length(); if (length <= nRows || nRows == 1) return s; char[] chars = new char[length]; int step = 2 * (nRows - 1); int count = 0; for (int i = 0; i < nRows; i++){ int interval = step - 2 * i; for (int j = i; j < length; j += step){ chars[count] = s.charAt(j); count++; if (interval < step && interval > 0 && j + interval < length && count < length){ chars[count] = s.charAt(j + interval); count++; } } } return new String(chars); } }