22ms one-pass O(n)-time C++ solution with explanation


  • 0
    L

    numRows=3
    |P. |...|....|....| A |....|....|....| H |... |...|....| N |...|
    |....|A |....| P |....| L |....| S |....| I .|...| I .|....|G |
    |....|...|.Y |....|....|....|. I |....|... | ...|R |....|....|....|
    | 0 |1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10|11|12|13| Column
    | 0 |1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | num = Column % (2 * numRows - 2)
    | 0 |1 | 2 | 1 | 0 | 1 | 2 | 1 | 0 | 1 | 2 | 1 | 0 | 1 | num < numRows ? num : (2 * numRows - 2) - num

    the problem as the same as
    |0|1|2|3|
    |0|1|2|1|

    class Solution {
    public:
    string convert(string s, int numRows) {
    if (numRows == 1)
    return s;
    string *ss = new string[numRows], rs;
    for (int i = 0; i < s.size(); i++){
    int num = i % (2 * numRows - 2);
    ss[num < numRows ? num : (2 * numRows - 2) - num].push_back(s[i]);
    }
    for (int i = 0; i < numRows; i++){
    rs += ss[i];
    }
    delete[] ss;
    return rs;
    }

    /*
    numRows=3
    |P| | | |A| | | |H| | | |N | |
    | |A| |P| |L| |S| |I| |I | |G |
    | | |Y| | | |I| | | |R | | | |
    |0|1|2|3|4|5|6|7|8|9|10|11|12|13|
    |0|1|2|3|0|1|2|3|0|1|2 |3 |0 |1 | Column % (2 * numRows - 2)
    |0|1|2|1|0|1|2|1|0|1|2 |1 |0 |1 |

    numRows=4
    |P| | | | | |I| | | | | |N | |
    | |A| | | |L| |S| | | |I | |G |
    | | |Y| |A| | | |H| |R | | | |
    | | | |P| | | | | |I| | | | |
    |0|1|2|3|4|5|6|7|8|9|10|11|12|13|
    |0|1|2|3|4|5|0|1|2|3|4 |5 |0 |1 | Column % (2 * numRows - 2)
    |0|1|2|3|2|1|0|1|2|3|2 |1 |0 |1 |
    the problem as the same as
    |0|1|2|3|
    |0|1|2|1|

    |0|1|2|3|4|5|
    |0|1|2|3|2|1|

    */
    };

    0_1487322469373_6_ZigZag Conversion .cpp


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.