6. 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)

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 s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

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

解题思路：

这道题直接从字符串找位置有点麻烦，我们可以用二维数组存储zigzag模式，然后从中读取字符并加入到新的字符串中。

直接找位置：参见Grandyang

代码：

#define UP 1
#define DOWN 0
class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1)
            return s;
        int idx = 0;
        int row = 0;
        int direction = 1;
        vector<vector<char>> zigzag(numRows);
        while(idx < s.size()){
            zigzag[row].push_back(s[idx++]);
            if(row == (numRows-1) || row == 0)
                direction ^= 1;
            if(direction == UP){
                row--;
            }else if(direction == DOWN){
                row++;
            }
        }
        string ret;
        for(int i = 0; i < numRows; i++){
            for(char c: zigzag[i]){
                ret.push_back(c);
            }
        }
        return ret;
    }
};

直接找位置：

class Solution {
public:
    string convert(string s, int nRows) {
        if (nRows <= 1) return s;
        string res = "";
        int size = 2 * nRows - 2;
        for (int i = 0; i < nRows; ++i) {
            for (int j = i; j < s.size(); j += size) {
                res += s[j];
                int tmp = j + size - 2 * i;
                if (i != 0 && i != nRows - 1 && tmp < s.size()) res += s[tmp];
            }
        }
        return res;
    }
};