Solution sharing C++ 23ms


  • 8
    M
        class Solution {
    public:
        string convert(string s, int nRows) {
        //Analysis: the problem is convert a serial string to a Zig-Zag pattern
        //[0,1,2,3,4,5,6,7,8,9,...,N] with row m;
        //0                 2m-2                4m-4
        //1            2m-3 2m-1           4m-3
        //...      ...      ...      ...
        //m-2   m           3m-4  3m-2
        //m-1               3m-3
        //so the algorithm is basically an algebra converting of the indexes.
        //[s.length/(2m-2)]
        //[0,2m-2,4m-4,...,1,2m-3,2m-1]
        string result;
        int i,j;
        int len=s.length();
        if (nRows==1) return s;
        for (i=0;i<nRows;i++){
            //for each row in the Zig-Zag graph
            //for the first and last row:
            //[0,2m-2,4m-4,6m-6.....,]
            //[m-1,3m-3,5m-5]
            //for the middle rows
            //[i,2m-2-i,2m-2+i,4m-4-i,4m-4+i....]
            j=0;
            while (j<len+i){
                if (i<nRows-1 && i>0 && j>i){
                    result+=s.at(j-i);
                }
                if ((i+j)<len){
                    result+=s.at(j+i);
                }
                j+=2*nRows-2;
            }
        }
        return result;
        }
    };

  • 0
    H

    Using std::string::at instead of std::string::operator[] is the key to improve a 27ms solution to a 23ms in this environment.


Log in to reply
 

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