题目：https://leetcode-cn.com/problems/zigzag-conversion/
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P A H N
A P L S I I G
Y I R

我的方法一：O(N)，O(1)

这个其实是有规律的，以示例为例，行数是3，我们看到每隔4（3x2 - 2）个字符会重新回到第一行，所以将Z形以4为间隔分为一个一个的小段，每个段会发现第一行和最后一行只有一个字符，其余行有2个字符。二每行每个字符是可以直接通过某个公式获得在原字符串中的位置的。
间隔interval = numRows * 2 -2
第一行在原字符的位置是interval0，interval1，interval2， interval3.....
第二行在原字符的位置是（interval0+1，interval0+interval - 1），（interval1+1，interval1+interval - 1），（interval2+1，interval2+interval - 1）
第N行在原字符的位置是（interval0+N，interval0+interval - N），（interval1+N，interval1+interval - N），（interval2+N，interval2+interval - N）
当N = interval - N时，表示最后一行，肯定会存在N = interval - N吗？是的，因为N = interval / 2，由于interval = numRows * 2 -2肯定是偶数，所以肯定存在N = interval - N。

初始条件

1. 偏移量计算好

边界条件

1. 当偏移量超出字符串长度时，停止遍历
2. 计算好首行和最后一行，因为这两行只有一个数

代码

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1){
            return s;
        }

        string ret;
        ret.reserve(s.size());
        int max_size = s.size();
        const char* s_str = s.c_str();
        int interval = numRows * 2 - 2;
        int offset1 = 0;
        int offset2 = 0;

        //时间O(N)，每个字符只被遍历一次
        //空间O(1)，没有使用额外的内存，ret是返回值，不计入
        for(int i = 0; i < numRows; i++) {
            offset1 = i;
            offset2 = interval - i;

            while(1) {
                if(offset1 < max_size){
                    ret.push_back(s_str[offset1]);
                }else{
                    break;
                }
                
                if(i != 0 && offset2 != offset1){
                    if(offset2 < max_size){
                        ret.push_back(s_str[offset2]);
                    }else{
                        break;
                    }
                }

                offset1 += interval;
                offset2 += interval;
            }
        }

        return ret;
    }
};