LeetCode - Zigzag Conversion

思路

• 将字符按 N 型镜像排列
  

• 不论奇偶, 可以发现, 重复部分的长度为 numRows + numRows - 2
  

  ​* *
  ***
  ​* *

  ​*  *
  ​* **
  ** *
  ​*  *

• 如果考虑压栈, 有几行, 就得有相应个数的栈
  

• 如果单栈处理, 会发现首尾两个栈压入一个元素时, 其他栈需要压入两个元素: 不好写循环
  

  ​*    *
  ​*   **
  ​*  * *
  ​* *  *
  **   *
  ​*    *

• 顺着字符进栈顺序, 恰好可以完成一组
  
  每 numRows + numRows - 2 个字符, 先每个栈压进去一个, 再倒着压入首尾之外的栈
  

特殊情况: 只有一行时, 直接返回字符串

解答

Copy 1class Solution {
 2public:
 3    string convert(string s, int numRows) {
 4        if (numRows == 1)
 5        {
 6            return s;
 7        }
 8
 9        auto n = s.length();
10        auto step = numRows + numRows - 2;
11
12        string stack[numRows];
13
14        for (auto start = 0; start < n; start += step)
15        {
16            auto cnt = start;
17            for (auto j = 0; j < numRows && cnt < n; ++j, ++cnt)
18            {
19                stack[j].push_back(s[cnt]);
20            }
21            for (auto j = numRows - 2; j > 0 && cnt < n; --j, ++cnt)
22            {
23                stack[j].push_back(s[cnt]);
24            }
25        }
26
27        string res = stack[0];
28        for (auto i = 1; i < numRows; ++i)
29        {
30            res += stack[i];
31        }
32        return res;
33    }
34};