Simple O(n) solution in C++ - Any optimisation?


  • 1
    S

    After banging my head against the wall to decipher the question, I have a O(n) solution
    If you cant understand the problem see here: https://leetcode.com/discuss/1212/expected-output-of-abcde-4
    I would still like to know if there is some optimization I can do to the algorithm.

    Im reading the string one char at a time and creating the strings, in the end I just concat the strSpace according to the number of rows which is the solution

    string convert(string s, int numRows){
    
    	std::string resultString = "";
    	std::string* strSpace = new std::string[numRows];
    
    	if(s.size() >= numRows && numRows > 1)
    	{
    		int index = 0;
    		int numDiagnols = 0;
    		for(std::string::iterator it = s.begin(); it != s.end(); ++it)
    		{
    			int iterIndex = it - s.begin();
    			if(index == numRows || numDiagnols > 0)
    			{
    				if(numDiagnols == 0)
    				{
    					numDiagnols = numRows - 2;
    					index = (numDiagnols > 0) ? 0 : 1;
    				}
    
    				strSpace[numDiagnols].push_back(s[iterIndex]);
    				--numDiagnols;
    			}
    			else
    			{
    				strSpace[index].push_back(s[iterIndex]);
    				numDiagnols = 0;
    				++index;
    			}
    		}
    
    		for(int i = 0; i < numRows; ++i)
    		{
    			resultString += strSpace[i];
    		}
    	}
    	else
    	{
    		resultString = s;
    	}
    
    	return resultString;
    }

  • 0
    Z
        class Solution {
        public:
            int minimumTotal(vector<vector<int>> &triangle) {
                if(triangle.size()==0)
                    return 0;
                 if(triangle.size()==1)
                    return triangle[0][0];
                vector<int> oldminpath;
                vector<int> newminpath;
                oldminpath.push_back(triangle[0][0]);
                for(int i=1;i<triangle.size();i++)
                {
                    newminpath.push_back(oldminpath[0]+triangle[i][0]);
                    for(int j=1;j<triangle[i].size()-1;j++)
                        newminpath.push_back(min(oldminpath[j-1]+triangle[i][j],oldminpath[j]+triangle[i][j]));
                    newminpath.push_back(oldminpath[i-1]+triangle[i][i]);
                    oldminpath=newminpath;
                    newminpath.clear();
                }
                int mymin=oldminpath[0];
                for(int i=0;i<oldminpath.size();i++)
                    if(mymin>oldminpath[i])
                        mymin=oldminpath[i];
                return mymin;
            }
        };
    
    
    This one is more compact.

  • 0
    S

    How many ms?


Log in to reply
 

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