6. ZigZag Conversion

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 NA P L S I I GY 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);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4Output: "PINALSIGYAHRPI"Explanation:P I NA L S I GY A H RP I

思路：

1、通过字符串在每一行出现的顺序，可以其分两个部分：第一行和最后一行，中间行。 2、对于第一行和最后一行，由上图可知，具有相同的对应关系。 3、对于中间行，前一个下标的值和后一个下标的值需要根据这个下标是该行中的奇数列还是偶数列来计算。 4、对已第一行和最后一行，通过规律发现，其对应关系为：start + 2 * 总行数 - 2 ，其中start为该行起始字符在数组的位置。例如第一行开始的start = 0，则后续对应位置为0 + 2 * 5 - 2 = 8，初始start为各行的起始值。同理，对于最后一行，当start = 4时，则后续对应位置为4+ 2 * 5 - 2 = 12，依此类推。 5、对于中间行，当列数为奇数时，其对应位置关系为：start + 2 * (总行数 - 当前行 - 1)；当列数为偶数时，其对应关系为：start + 2 * 当前行，其中当前列从0开始。例如，对于第三行的起始start = 3，其后续位置所在列为1，是奇数列，则后续位置为 3 + 2 * （5 - 3 -1）= 5 ，此时start = 5，则其后续位置所在列数为4，是偶数列，则后续位置为5 + 2 * 3= 11。

class Solution { public String convert(String s, int numRows) { if (numRows <= 0) return ""; if (numRows == 1 || numRows >= s.length()) return s; StringBuffer buffer = new StringBuffer(); int len = s.length(); for (int i = 0; i < len && i < numRows; ++i) { // 在字符串中的变化的位置 int start = i; buffer.append(s.charAt(start)); for (int j = 1; start < len; ++j) { // 第一行和最后一行 if (i == 0 || i == numRows - 1) { start = start + 2 * numRows - 2; } else { // 对于中间行，在字符串中位置为基数时 if (j % 2 == 1) { start = start + 2 * (numRows - i - 1); } else { // 位置为偶数时 start = start + 2 * i; } } // 边界判断 if (start < len) buffer.append(s.charAt(start)); } } return buffer.toString(); }}

Java2:

class Solution { public String convert(String s, int numRows) { if(numRows == 1 || numRows == 0) return s; StringBuilder ans = new StringBuilder(); int ind = numRows + numRows - 2; int length = s.length(); int nextInt = 0; for(int i = 0; i< numRows;i++){ nextInt = i; boolean odd = true; while(length > nextInt){ ans.append(s.charAt(nextInt)); if(i == 0 || i == numRows - 1) { nextInt = nextInt + ind; } else { if(odd) { nextInt = nextInt + (ind - 2 * i); odd = false; } else { nextInt = nextInt + 2 * i; odd = true; } } } } return ans.toString(); }}

class Solution { public String convert(String s, int numRows) { int rows = Math.min(numRows, s.length()); if (rows < 2) return s; StringBuilder[] sbArray = new StringBuilder[rows]; for (int i = 0; i < rows; i++) { sbArray[i] = new StringBuilder(); } char[] chars = s.toCharArray(); for (int i = 0; i < chars.length; i++) { sbArray[x(rows - 1, i)].append(chars[i]); } StringBuilder output = new StringBuilder(); for (StringBuilder stringBuilder : sbArray) { output.append(stringBuilder.toString()); } return output.toString(); } /* * Triangle wave function to select correct row (StringBuilder) to append to * Output oscillates between [0, n] */ private int x(int n, int i) { return n - Math.abs(i % (2 * n) - n); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。