C++ solution with expl. on Memory Limit Exceeded error many of you might come across


  • 5
    E

    The cycle is 2*nRow -2.
    Then from row to row, get the char with the cycle and also read the in-between char

    For example, ith row, the first value is s[i], the next should be s[i+cycle], then find the middle char, from the current index j, j-i returns to the 0th row, and j-i +cycle get the next point at the 0th row, this value minus i will give the middle index, so it is j+cycle -2*i

    Note: the memory limit exceeded error, is caused by the corner situation, where cycle=1. Pitch this out first.

     string convert(string s, int nRows) {
            
            int cycle=2*nRows -2;
            // pop the cycle=1 situation
            if(cycle<2)
            {
                return s;
            }
            string res;
            
            for(int i=0;i<nRows;++i)
            {
                for(int j=i;j<s.size();j+=cycle)
                {
                    res.push_back(s[j]);
                    
                    if(i>0 && i!=nRows-1 && (j+cycle-2*i <s.size()))
                    {
                        res.push_back(s[j+cycle-2*i]);
                    }
                }
                
            }
            
            return res;
            
        }

  • 0
    Z

    great! most elegant I've seen in C/C++。better than this:

    string convert(string s, int numRows) {
    size_t len = s.size();
    if (numRows <= 1 || numRows >= len)
    	return s;
    string str;
    str.resize(len);
    size_t idx = 0;
    
    size_t maxStep = 2 * (numRows - 1);
    for (size_t i = 0;i < numRows;++i)
    {
    	if (0 == i || numRows - 1 == i)
    	{
    		for (size_t j = i; j < len; j += maxStep)
    		{
    			str[idx++] = s[j];
    		}
    	}else{
    		size_t step = 2 * i;
    		for (size_t j = i; j < len; j += step)
    		{
    			str[idx++] = s[j];
    			step = maxStep - step;
    		}
    	}
    }
    return str;
    }

Log in to reply
 

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