Article From:https://www.cnblogs.com/yaoyudadudu/p/9219416.html

Description of the problem:

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

 

The idea of solving the problem:

This problem is a bit troublesome to find a position directly from a string. We can store the zigzag pattern in a two-dimensional array and read the character from it and add it to a new string.

Look for a position directly: see Grandyang

 

Code:

#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;
    }
};

Find the position directly:

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;
    }
};

 

Link of this Article: 6. ZigZag Conversion

Leave a Reply

Your email address will not be published. Required fields are marked *