3ms solution (Can it be improved?)


  • 0
    K
    class Solution {
    public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int> > triangle;
        vector<int> previous;
    
        if (numRows > 0) {
    	    for (unsigned int i = 0; i < (unsigned int) numRows; i++) {
    		    vector<int> current;
    		    if (i == 0) {
    			    current.push_back(1);
    			    triangle.push_back(current);
    		    } else if (i == 1) {
    			    current.push_back(1);
    			    current.push_back(1);
    			    triangle.push_back(current);
    		    } else {
    			    previous = triangle[i - 1];
    			    for (unsigned int j = 0; j < i + 1; j++) {
    				    if (j == 0 || j == i)
    					    current.push_back(1);
    				    else{
    					    current.push_back(previous[j - 1] + previous[j]);
    				    }
    			    }
    			    triangle.push_back(current);
    		    }
    	    }
        }
        return triangle;
    }
    };

  • -1
    F

    It didn't make much difference to the runtime, but you can make the code slightly leaner on memory by not creating a temporary variable for previous, and instead using a pointer (or reference). You also don't really need to handle special cases in their own blocks, as they are dealt with in the loop:

    vector<vector<int> > generate(int numRows) {
            vector<vector<int>> triangle;
            vector<int> *previous;
            
            for (int i = 0; i < numRows; ++i) {
                vector<int> current;
                for (int j = 0; j < i+1; ++j) {
                    if (j == 0 || j == i) {
                        current.push_back(1);
                    }
                    else {
                        current.push_back(previous->at(j-1) + previous->at(j));
                    }
                }
                triangle.push_back(current);
                
                previous = &triangle[i];
            }
            
            return triangle;
        }

  • 0
    C

    哈哈,可以用中文说不呢?
    我觉得只要一层一层往下生长就行,这应该是最优的,


  • 0

    I got this idea because I somehow did the second part first.

       class Solution {
        public:
            vector<int> getRow(int rowIndex) 
            {
                vector<int> A(rowIndex+1, 0);
                A[0] = 1;
                for(int i=1; i<rowIndex+1; i++)
                    for(int j=i; j>=1; j--)
                        A[j] += A[j-1];
                return A;
            }
            vector<vector<int>> generate(int numRows) 
            {
    
               vector<vector<int>> b;
               for(int i=1;i<=numRows;i++)
               {
                   b.push_back(getRow(i-1));
               }
            return b;
            }
        
        };
    

  • 2
    Y
    vector<vector<int>> result;
    for (int i = 0; i < numRows; i++){
    	vector<int> t(i + 1, 1);
    	result.push_back(t);
    	if (i >= 2){
    		for (int j = 1; j < t.size() - 1; j++){
    			result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
    		}
    	}
    }
    return result;
    

    0 ms :)


  • 0
    K

    Nice solution! So simple.


  • 0
    C

    笑死了,你是我看到的第一个中文回复


  • 0
    S

    @chengzhoukun bu yao yong zhong wen hui fu


Log in to reply
 

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