ZigZagConversion [source code]
public class ZigZagConversion {
static
/******************************************************************************/
class Solution {
public String convert(String s, int numRows) {
if (numRows <= 1)
return s;
StringBuilder[] rows = new StringBuilder[numRows];
for (int i = 0; i < rows.length; i++)
rows[i] = new StringBuilder ();
char[] chs = s.toCharArray ();
int i = 0, r = 0, delta_r = 1;
while (i < chs.length) {
rows[r].append (chs[i++]);
r += delta_r;
if (r == numRows - 1)
delta_r = -1;
else if (r == 0)
delta_r = 1;
}
StringBuilder res = new StringBuilder ();
for (StringBuilder sb : rows)
res.append (sb);
return res.toString ();
}
}
/******************************************************************************/
public static void main(String[] args) {
ZigZagConversion.Solution tester = new ZigZagConversion.Solution();
String[] inputs = {
"", "1", "",
"PAYPALISHIRING", "3", "PAHNAPLSIIGYIR",
"AB", "1", "AB",
};
for (int i = 0; i < inputs.length / 3; i++) {
String s = inputs[3 * i], ans = inputs[3 * i + 2];
int numRows = Integer.parseInt (inputs[3 * i + 1]);
System.out.println (Printer.separator ());
String output = tester.convert (s, numRows);
System.out.printf ("%s and %d -> %s, expected: %s\n",
s, numRows, Printer.wrapColor (output, output.equals (ans) ? "green" : "red"), ans
);
}
}
}
吓死我了我一开始还以为是splee tree的题目, 原来是string题目; 题目要求读完, 感觉是一个找规律, 然后一些数字计算的规律的问题; 这种肯定是要笔算看看的;
最后题目本身应该说还是比较简单的, 一个倒豆子的思路, 注意在pre leaf的位置控制increment的改变就行了, 速度是58ms (56%).
一个小坑, 在初始化一个array的时候, 我一开始写的是:
StringBuilder[] rows = new StringBuilder[numRows];
for (StringBuilder sb : rows)
sb = new StringBuilder ();
但是这个最后导致完全没有完成任何的初始化, 因为for each结构实际上iterate的是一个右值而不是左值, 所以你这个循环实际上是没有任何内容被执行;
另外, 提交的时候, 被一个length == 1的case给break掉了; 刚开始还想, 是不是得重新修理一下逻辑, 但是后来想了一下, 这种case, 直接当成special case来处理就行了, 不要过分追求generic;
这个题目我一开始的想法是认为, 不需要用这个一个一个倒豆子的思路, 而是直接可以确定index之间的数学关系, 用一个类似数学的思路去做, 不过最后也是没有想到这个思路;
没有editorial;
@dylan_yu said in Easy to understand Java solution:
Create nRows StringBuffers, and keep collecting characters from original string to corresponding StringBuffer. Just take care of your index to keep them in bound.
public String convert(String s, int nRows) {
char[] c = s.toCharArray();
int len = c.length;
StringBuffer[] sb = new StringBuffer[nRows];
for (int i = 0; i < sb.length; i++) sb[i] = new StringBuffer();
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]);
return sb[0].toString();
}
跟我的思路类似, 但是小有区别, 写的不如我的generic, 他是人工定义一个iteration就是一个上+下的组合, 这样来写的; 要这样写, 一个必要的处理就是把i的bound限制要加到这个上下循环的header里面去, 这样当i被走完的时候, 适时的夹断;
@scheung said in Easy to understand Java solution:
If n is the size of the string and m is the numRows, the solution is O(n+m). It takes O(m) to create the StringBuffer array and then traversing the String s takes O(n). Putting the solution together is O(m), so overall the runtime is O(n+m).
这个思路有点意思, 稍微有点接近数学解法的意思了: 不需要明确的定义出来一个一个的row然后往里面挨个倒豆子:
@HelloKenLee said in If you are confused with zigzag pattern,come and see!:
n=numRows Δ=2n-2 1 2n-1 4n-3 Δ= 2 2n-2 2n 4n-4 4n-2 Δ= 3 2n-3 2n+1 4n-5 . Δ= . . . . . Δ= . n+2 . 3n . Δ= n-1 n+1 3n-3 3n-1 5n-5 Δ=2n-2 n 3n-2 5n-4that's the zigzag pattern the question asked!
Be careful with nR=1 && nR=2my 16ms code in c++:
class Solution {
public:
string convert(string s, int numRows) {
string result="";
if(numRows==1)
return s;
int step1,step2;
int len=s.size();
for(int i=0;i<numRows;++i){
step1=(numRows-i-1)*2;
step2=(i)*2;
int pos=i;
if(pos<len)
result+=s.at(pos);
while(1){
pos+=step1;
if(pos>=len)
break;
if(step1)
result+=s.at(pos);
pos+=step2;
if(pos>=len)
break;
if(step2)
result+=s.at(pos);
}
}
return result;
}
};
这个算法一开始是没看懂的, 这个时候我们还是老办法, 找一个例子, 然后笔算; 不要担心这个例子不够general, 或者不够specific, 不能触发所有的边界检查处理; 只要你能跑完一个最正常最普通的例子, 一般对于理解算法的帮助就已经很大了;
最后还是看懂了, 感觉这个人总结规律的能力还是很强的, 两个step的定义, 以及在随后的while循环里面的处理, 都是恰到好处; 注意, while循环里面对两个step的判断, 是有必要的: 不过其实也可以通过对i的判断来解决, 因为这两个step等于0只会在最上面和最下面的两个row/i才会发生;
评论里提到了这个解法: https://segmentfault.com/a/1190000005751185 . 总体来说还是一个找规律的思路, 不过总结的还可以;
default example might not be the best one
另外, 这个题目, 思考例子的时候, 我感觉用PAYPALISHIRING和4更容易发现和观察规律, 而不是用默认的3; 这点变通的能力应该还是有的;
评论里面的一个改进版:
@snap_dragon said in If you are confused with zigzag pattern,come and see!:
public String convert(String str, int R) {
if (R == 1) return str;
char[] s = str.toCharArray();
char[] t = new char[s.length];
for (int i = 0, len = 0; i < R; i++) {
for (int j = 0, k = i; k < s.length; j++) {
t[len++] = s[k];
k += ((i == 0 || j % 2 == 0) && i != R - 1 ? 2 * (R - i - 1) : 2 * i);
}
}
return new String(t);
}
写的太紧凑, 很不好读, 我差点直接downvote了, 最后还是耐着性子尝试去理解, 还是用上面4row的例子:
i:(0), len:(0)
j:(0), k:(0)
j:(1), k:(6)
j:(2), k:(12)
i:(1), len:(3)
j:(0), k:(1)
j:(1), k:(5)
j:(2), k:(7)
j:(3), k:(11)
j:(4), k:(13)
i:(2), len:(8)
j:(0), k:(2)
j:(1), k:(4)
j:(2), k:(8)
j:(3), k:(10)
i:(3), len:(12)
j:(0), k:(3)
j:(1), k:(9)
这个trace打出来, 应该还是能看到大概的思路的, 跟OP原来的解法其实是一个思路, 不过写法精炼很多;
他这里这个j好像就是一个binary switch的作用, 在两个step之间进行切换; 三目最后的这个2 * (R - i - 1) : 2 * i就是OP原来的方法里面的两种step的定义;
另外一个改写, 类似的思路, 不过写法更加清晰:
@Avril_XueweiLi said in If you are confused with zigzag pattern,come and see!:
Share my Java solution with the same idea but maybe a little bit concise.
intervalstarts from2 * numRows - 2and decrease by 2. (As same as thestep1in @HelloKenLee solution).- In the
whileloop,iis 0 means we are in the first row andintervalis 0 means we reach the last row. In both cases, we just need to avoid appending repeated characters. Otherwise, we append 2 characters.
public String convert(String s, int numRows) {
if(numRows == 1) return s;
StringBuilder b = new StringBuilder();
int interval = 2 * numRows - 2;
int n = s.length();
for(int i = 0; i < numRows; i++){
int j = i;
while(j < n){
if(interval != 0)
b.append(s.charAt(j));
j += interval;
if(i != 0 && j < n)
b.append(s.charAt(j));
j += 2 * i;
}
interval -= 2;
}
return b.toString();
}
submission最优解: 49(86):
class Solution {
public String convert(String s, int numRows) {
if (s == null || numRows <= 1 || s.length() <= numRows) return s;
int len = s.length();
char[] source = s.toCharArray();
char[] dest = new char[len];
int step = 2 * numRows - 2;
int k = 0;
for (int i = 0; i < len; i += step) {
dest[k++] = source[i];
}
for (int i = 1; i < numRows - 1; ++i) {
int j = i;
int otherJ = j + step - 2 * i;
while (j < len && otherJ < len) {
dest[k++] = source[j];
dest[k++] = source[otherJ];
j += step;
otherJ += step;
}
if (j < len)
dest[k++] = source[j];
}
for (int i = numRows - 1; i < len; i += step) {
dest[k++] = source[i];
}
return String.valueOf(dest);
}
}
大概看了一下, 这个跟之前看的那个数学解法是类似的, 不过他单独把最上下的两行拿出来单独处理, 然后中间段1..n-2, 单独用一个循环来处理;
Problem Description
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 numRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
Difficulty:Medium
Total Accepted:190.6K
Total Submissions:702.2K
Contributor:LeetCode
Related Topics
string