前言：为了后续的实习面试，开始疯狂刷题，非常欢迎志同道合的朋友一起交流。因为时间比较紧张，目前的规划是先过一遍，写出能想到的最优算法，第二遍再考虑最优或者较优的方法。如有错误欢迎指正。博主首发，mcf171专栏。
博客链接：mcf171的博客
——————————————————————————————
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".
第一个思路是直接按照Z格式先写了，然后用O（n^2）的办法得到结果。Your runtime beats 5.40% of java submissions
public class Solution { public String convert(String s, int numRows) { if(numRows == 1) return s; int numColumns = (s.length()/(numRows - 1 )) ; numColumns = numColumns == 0 ? 1 : numColumns; char[][] result = new char[numRows][numColumns]; boolean direction = true; int row = 0, column = 0; for(int i = 0 ; i < s.length(); i ++){ result[row][column] = s.charAt(i); if(direction == true){ row ++; if(row == (numRows - 1)) direction = false; }else{ row --; column ++; if(row == 0) direction = true; } } StringBuffer bf = new StringBuffer(""); for(int i = 0 ;i < numRows ; i ++) for(int j = 0 ; j < numColumns; j ++){ if('\0' != result[i][j]) bf.append(result[i][j]); } return bf.toString(); } }
第二个思路是采用跳着访问矩阵的方式输出结果。Your runtime beats 23.41% of java submissions.
public class Solution { public String convert(String s, int numRows) { if(numRows == 1) return s; int numColumns = (s.length()/(2*numRows - 2 ) + 1) * (1 + numRows -2); char[][] result = new char[numRows][numColumns]; boolean direction = true; int row = 0, column = 0; for(int i = 0 ; i < s.length(); i ++){ result[row][column] = s.charAt(i); if(direction == true){ row ++; if(row == (numRows - 1)) direction = false; }else{ row --; column ++; if(row == 0) direction = true; } } StringBuffer bf = new StringBuffer(""); for(int i = 0 ;i < numRows ; i ++) { boolean jump = true; for (int j = 0; j < numColumns;) { if ('\0' != result[i][j]) bf.append(result[i][j]); if( i == 0 || i == numRows -1) j = j + numRows - 1; else{ if(jump) { j = j + numRows - 1 - i; }else{ j = j + i; } jump = !jump; } } } return bf.toString(); } }
第三个思路，发现其实每个字符串跳跃是有规律的，都不用矩阵了，直接跳跃就好了，复杂度O(n)Your runtime beats 32.95% of java submissions.
public class Solution { public String convert(String s, int numRows) { if(numRows == 1) return s; StringBuffer bf = new StringBuffer(""); for(int i = 0 ;i < numRows ; i ++) { boolean jump = true; int index = i; for(;index < s.length();){ bf.append(s.charAt(index)); if( i == 0 || i == numRows -1) index += numRows * 2 -2 ; else{ if(jump) { index += numRows * 2 - 2 - ( i * 2); }else{ index += i* 2; } jump = !jump; } } } return bf.toString(); } }