Zigzag Conversion

• Easy
• tag: String, Math
• similar: rotate graph, count ones

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".

思路

• 先搞明白这个zigzag什么意思: Ans: 就是根据row和string, 变成zigzag的形状. 例如row = 5的时候如下图:

  0        1        2        3
  0      0 1      1 2      2 3
  0    0   1    1   2    2   .
  0  0     1  1     2  2     .
  0        1        2
  

• 题目要求返回变为zigzag之后再按行打印出来. 一开始的想法是建立新的表, 然后一行行的打印. 那么一共有多少列呢? 怎么排列呢? 感觉挺麻烦的.

idea : discuss里面tju_xu的解法

• 还是和rotate graph一样, 这题很有规律. 看到这里有个循环, 即上图中所示的相同index的 V型. 可以很容易计算出这个循环体的长度: numRows+(numRows-2) = numRows * 2 - 2. 因为第一行/最后一行只有cycle中的1个元素, 其他行都有该cycle中的2个元素.

• 那么怎么找到在原本的string中的index呢?

  • 对于第i行:
  • 对于第一个元素: $$j = i + cycle * k ; k \in [0,1,2...]$$
    • 是个很好理解.
  • 该cycle中, 该行的第二个元素的index是: $$secondj = (j-i) + cycle + i$$.
    • 这里j-i即该cycle的起点, j-i+cycle即下一个cycle的起点, 于是第二个元素就从下一个cycle的起点向前推i个就是了.

• 公式有了就很容易写了, 但还是要注意怎么loop.

  • 这里是按照结果的顺序, 即按行loop. 从而按顺序加入结果string.

• 代码如下:

public String convert(String s, int numRows) {
    if (numRows <= 1)  return s;
    int cycle = numRows * 2 - 2;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < numRows; ++i) {
      // Suppose the current row is i, the index of the first element is j
      for (int j = i; j < s.length(); j += cycle) {
        sb.append(s.charAt(j));
        // (j-i) is the start of current period, (j-i) + cycle is the start of next periods
        int secondJ = (j-i) + cycle - i;
        if (i != 0 && i != numRows-1 && secondJ < s.length()) {
          sb.append(s.charAt(secondJ));
        }
      }
    }
    return sb.toString();
  }