My concise solution in Java


  • 121
    R
    public class Solution {
    public List<List<Integer>> generate(int numRows)
    {
    	List<List<Integer>> allrows = new ArrayList<List<Integer>>();
    	ArrayList<Integer> row = new ArrayList<Integer>();
    	for(int i=0;i<numRows;i++)
    	{
    		row.add(0, 1);
    		for(int j=1;j<row.size()-1;j++)
    			row.set(j, row.get(j)+row.get(j+1));
    		allrows.add(new ArrayList<Integer>(row));
    	}
    	return allrows;
    	
    }
    

    }


  • 0
    R

    May I ask how much time(ms) does you program take per OJ ?


  • 1
    R

    It takes 189ms.


  • 2
    X

    could you explain that row.set(j, row.get(j)+row.get(j+1)) mean ,thanx


  • 8
    H

    Anyone knows why we cannot use allrows.add(row); instead of allrows.add(new ArrayList<Integer>(row)); ???


  • 3
    E

    if you use allrows.add(row) then finally you will get a list that have numRows empty list.
    you should learn more about how java pass parameter.


  • 6
    E

    this solution is really smart , using row.add(0,1) and j<row.size()-1, you avoid boundary checking.


  • 1
    X

    why don't you just create the arraylist inside the first loop?
    Updated: oh... I got it. Nice solution.


  • 0
    P

    Could you explain more clearly? My result is not empty list but wrong answer.
    Thanks!


  • 4
    W

    I think this one https://leetcode.com/discuss/16178/solution-in-java is better.

    In your solution, actually there is two passes. one is calculation. Another is one is allrows.add(new ArrayList<Integer>(row));


  • 6
    H

    It's a technique to CLONE the row (make a copy of the row).
    Reason to do that is that the row is going to be modified when i is incremented.
    You don't want the row that is added to allrows to be modified too, you need to clone it.


  • 0
    S

    Obviously, on each row, the second half has the same number as the first half, but in a reverse order. I wonder why nobody solve this by reversely copying the first copy instead of recalculating everything. Will this potentially improve the performance if n is huge?


  • 0
    H

    In arraylist, the insertion in front costs O(n),


  • 0
    C

    java array set is very inefficient. it basically moves the entire array each time you set at certain index.


  • 6

    I don't exactly understand why we should use

    allrows.add(new ArrayList<Integer>(row));
    

    here, instead of

    allrows.add(row);
    

    I do see it is necessary to copy this row, then add to allrows. I tried and found that, if not, the result would be something like:
    [[1, 4, 6, 4, 1], [1, 4, 6, 4, 1], [1, 4, 6, 4, 1], [1, 4, 6, 4, 1], [1, 4, 6, 4, 1]]

    But could someone explain why update row in the loop would change the row we ALREADY/previously added to allrows???

    EDIT: The reason is that: row is an object. If we just do allrows.add(row); and this row object is changed in future operations, it will affect and changed what it is in our allrows. So we need to copy it, create a new object, and then save it to allrows.


  • 1
    Z

    allrows only save the address,not the data.So ,each time you save the same list into allrows. Hope this will help.


  • 0

    Use Python It only costs 40ms!

    class Solution(object):
    def factor(self, n):
    if(n <= 0):
    return 1
    factor = 1
    while(n > 0):
    factor *= n
    n -= 1
    return factor

    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        n = numRows
        N = self.factor(n)
        numList = []
        
        for i in range(0, n):
            List = [1] * (i + 1)
            numList.append(List)
            for j in range(0, i + 1):
                if(i == j):
                    List[j] = 1 
                elif(j == 0):
                    List[j] = 1
                elif(j == 1):
                    List[j] = i
                else:
                    List[j] = self.factor(i) // (self.factor(j) * self.factor(i - j))
        
        return numList
    

  • 0
    B

    In java, think this as some object. Without creating new object (new ArrayList<Integer>(row)), each iteration is trying to change the same object and then add (the address of the same object) to allrows. So they will be the same eventually. That's not what we want. For each row, should create a separate object, then add it to allrows.


  • 0
    D
    public class Solution {
        public List<List<Integer>> generate(int numRows) {
             List<List<Integer>> finalLs=null;
            finalLs= new ArrayList  <List<Integer>> ();
            if(numRows==0) return finalLs;
             
              List<Integer> ls;
            if(numRows>0) {
          ls = new ArrayList<Integer>();
            ls.add(1);
            finalLs.add(ls);
            }
            
            if(numRows>1) {
            ls= new ArrayList<Integer>();
            ls.add(1);
           ls.add(1);      
           finalLs.add(ls);
            }
             int j=2;
            if(numRows>2){
                 
                while(numRows>j) {   
                ls= new ArrayList<Integer>();
            ls.add(1);
                List <Integer> lsprev= finalLs.get(j-1);
                int i;
                 for(i=1;i<lsprev.size();i+=1)
                      ls.add(lsprev.get(i-1)+lsprev.get(i));
            ls.add(1);
                   finalLs.add(ls);
           j++;
                }
            }
            
            return finalLs;
        }
    }
    

    Not concise but it is 1ms solution.


  • 1
    E

    Brilliant solution! Learn a lot!


Log in to reply
 

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