Solution in Java


  • 89
    C

    two loops, one go through the row, one go through the column

    database: pretty straight forward, ArrayList

    calculate element value: K(i)(j)=K(i-1)(j-1)+K(i-1)(j) except for the first and last element

    public class Solution {
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> triangle = new ArrayList<List<Integer>>();
            if (numRows <=0){
                return triangle;
            }
            for (int i=0; i<numRows; i++){
                List<Integer> row =  new ArrayList<Integer>();
                for (int j=0; j<i+1; j++){
                    if (j==0 || j==i){
                        row.add(1);
                    } else {
                        row.add(triangle.get(i-1).get(j-1)+triangle.get(i-1).get(j));
                    }
                }
                triangle.add(row);
            }
            return triangle;
        }
    }

  • 0
    D
    This post is deleted!

  • 0
    This post is deleted!

  • 2
    A

    The check of numRows <=0 is not necessary.


  • -1
    S

    public class Solution {
    public List<List<Integer>> generate(int numRows) {
    if(numRows < 1){
    return new ArrayList<List<Integer>>();
    }
    List<List<Integer>> result = new ArrayList<List<Integer>>(numRows);
    List<Integer> lastRow = new ArrayList<Integer>(1);
    lastRow.add(1);
    result.add(lastRow);
    for(int i=1; i<numRows; i++){
    ArrayList<Integer> curRow = new ArrayList<Integer>(i+1);
    curRow.add(1);
    int j=1;
    for(j=1; j<i; j++){
    lastRow = result.get(i-1);
    curRow.add(lastRow.get(j-1)+lastRow.get(j));
    }
    curRow.add(lastRow.get(j-1));
    result.add(curRow);
    }
    return result;
    }
    }


  • 1
    A

    @chennan What is the running time for this solution?


  • 0
    Y

    @acheiver said in Solution in Java:

    @chennan What is the running time for this solution?

    Thanks for sharing the nice solution.
    I have the same question. Could anybody please analyse it? Thanks.


  • 1
    S

    @acheiver It's clearly n^2...


  • 0
    S

    in fact, you can save previous row to save time.

    just like this:

    public class Solution {
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            ArrayList<Integer> pre = null;
            for (int i = 1; i <= numRows; i++) {
                ArrayList<Integer> save = new ArrayList<>();
                for (int j = 1; j <= i; j++)
                    if (j == 1 || j == i) save.add(1);
                    else save.add(pre.get(j-1) + pre.get(j-2));
                result.add(save);
                pre = save;
            }
            return result;
        }
    }
    

  • 0
    Y

    Very explicit solution!


Log in to reply
 

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