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"
.A:
就是,用一个数组,来按照zigzag的方式,跑完,再逐行取出来就行。
public class Solution { public String convert(String s, int nRows) { if(nRows == 1) return s; List<StringBuilder> list = new LinkedList(); for(int i =0;i<nRows;i++) list.add(new StringBuilder()); while(!s.isEmpty()){ String str = s.substring(0,Math.min(s.length(),nRows*2-2)); s = s.substring(Math.min(s.length(),nRows*2-2)); for(int i =0;i<nRows;i++){ if(i>=str.length()) break; list.get(i).append(str.charAt(i)); } for(int i = 0;i<nRows-2;i++){ if(i+nRows>= str.length()) break; list.get(nRows-2-i).append(str.charAt(nRows+i)); } } StringBuilder buf = new StringBuilder(); for(StringBuilder tmp : list) buf.append(tmp.toString()); return buf.toString(); } }
Mistakes:
1: 当update index 出界的时候, 我们检查了出界的情况,并更正之, 这个时候,要记得把 k 退回去一个。
2: 哎,一直是column number计算地不对。 应该一下一上,半个zigzag,是nRow-1列
------------------- 第二遍-------------
1: 刚开始,列数计算的不对:
int nCols = (s.length() / (2 * nRows - 2) + 1) * (nRows-1);
2: 填充char数组的时候,j的update 也犯错了。 因为,在向上的时候, j++了。但是,在向下的时候,没有++. 导致, 二者不协调。
3: 又一次, 当减掉一个数的时候, 有可能就是0 啊,什么的, 要 小心对待。
因此,这里错在没有先检查 nRow -1 是否== 1 对于特例,要 特殊处理。
4: 当 nRows == 2的时候, 向上是没有列数的增加的, 因此,要小心哦。
Learned:
---------------第二遍代码----------------(不聪明的地方,就在于根据列数计算向上还是向下。 ,不如第一次,用个boolean表示向上,向下。 简单,易懂,不会犯错)
public class Solution { public String convert(String s, int nRows) { if (s == null || s.length() == 0) return ""; if(nRows == 1) return s; int nCols = (s.length() / (2 * nRows - 2) + 1) * (nRows-1); // assume char ch = 0 is not used in nRows char[][] A = new char[nRows][nCols]; for (int i = 0; i < nRows; i++) for (int j = 0; j < nCols; j++) A[i][j] = 0; int indexS = 0; for (int j = 0; j < nCols; ) { if (j % (nRows-1) == 0){ // going down for (int i = 0; i < nRows; i++){ if(indexS >= s.length()) break; A[i][j] = s.charAt(indexS++); } j++; } else{ // going up for (int i = nRows - 2; i >= 1; i--){ if(indexS >= s.length()) break; A[i][j++] = s.charAt(indexS++); } } if(indexS >= s.length()) break; } // read the matrix to get result StringBuffer buf = new StringBuffer(); for (int i = 0; i < nRows; i++) for (int j = 0; j < nCols; j++) if (A[i][j] != 0) buf.append(A[i][j]); return buf.toString(); } }根据上面的算法, 空间复杂度和时间复杂度都太高。
一个小小的技巧就是每次upward的时候,列数并不变。
这样,空间和时间都变成了O(n)
public class Solution { public String convert(String s, int numRows) { int start = 0; if(numRows == 1) return s; char[][] A = new char[numRows][s.length()/(2*numRows-2) *2 +2]; for(int i =0;i<numRows;i++) Arrays.fill(A[i],'@'); int t = 0, col = 0; while(t<s.length()){ for(int i = 0;i<numRows;i++){ if(t>=s.length()) break; A[i][col] = s.charAt(t++); } col++; for(int i = numRows-2;i>0;i--){ if(t>=s.length()) break; A[i][col]=s.charAt(t++); } col++; } StringBuffer buf = new StringBuffer(); for(int i =0;i<A.length;i++) for(int j =0;j<A[0].length;j++) if(A[i][j] != '@') buf.append(A[i][j]); return buf.toString(); } }
Mistakes:
1: 当有除法儿的时候, 一定要检测是否 divided by zero.
----------- 3 rd pass ----------- calculate the index directly --------
就是分成一上一下 一对pair,
public class Solution { public String convert(String s, int nRows) { if(nRows==1) return s; StringBuffer buf = new StringBuffer(); for(int i =0;i<nRows;i++){ for(int j =0;j<s.length()/(nRows*2-2)+1;j++){ int index1 = j*(nRows*2-2)+i; if(index1<s.length()) buf.append(s.charAt(index1)); int index2 = j*(nRows*2-2)+(nRows*2-2-i); if(i!=0 && i!= nRows-1 && index2<s.length()) buf.append(s.charAt(index2)); } } return buf.toString(); } }
Mistakes:
1: 当检测 第二个char的时候,应该是 既不是第一行,也不是第二行。 应该用&& ,结果写成了用 || . 这个比较SB
2: 又一次,除法的时候,没有检查是否divide by zero
No comments:
Post a Comment