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)

  1. P   A   H   N
  2. A P L S I I G
  3. 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:

  1. string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

分析

要找到数学规律。真正面试中，不大可能出这种问题。

n=4:

  1. P     I     N
  2. A   L S   I G
  3. Y A   H R
  4. P     I

n=5:

  1. P       H
  2. A     S I
  3. Y   I   R
  4. P L     I  G
  5. A       N

所以，对于每一层垂直元素的坐标 (i,j)= (j+1 )n +i；对于每两层垂直元素之间的插入元素（斜对角元素），(i,j)= (j+1)n -i

代码

  1. // ZigZag Conversion
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. public class Solution {
  4.     public String convert(String s, int numRows) {
  5.         if (numRows <= 1 || s.length() <= 1) return s;
  6.         StringBuilder result = new StringBuilder();
  7.         for (int i = 0; i < numRows; i++) {
  8.             for (int j = 0, index = i; index < s.length();
  9.                  j++, index = (2 * numRows - 2) * j + i) {
  10.                 result.append(s.charAt(index));  // 垂直元素
  11.                 if (i == 0 || i == numRows - 1) continue;   // 斜对角元素
  12.                 if (index + (numRows - i - 1) * 2 < s.length())
  13.                     result.append(s.charAt(index + (numRows - i - 1) * 2));
  14.             }
  15.         }
  16.         return result.toString();
  17.     }
  18. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/simulation/zigzag-conversion.html