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. // LeetCode, ZigZag Conversion
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     string convert(string s, int nRows) {
  6.         if (nRows <= 1 || s.size() <= 1) return s;
  7.         string result;
  8.         for (int i = 0; i < nRows; i++) {
  9.             for (int j = 0, index = i; index < s.size();
  10.                     j++, index = (2 * nRows - 2) * j + i) {
  11.                 result.append(1, s[index]);  // 垂直元素
  12.                 if (i == 0 || i == nRows - 1) continue;   // 斜对角元素
  13.                 if (index + (nRows - i - 1) * 2 < s.size())
  14.                     result.append(1, s[index + (nRows - i - 1) * 2]);
  15.             }
  16.         }
  17.         return result;
  18.     }
  19. };

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