Tuesday, October 28, 2014

Pascal's Triangle II Leetcode

Trivial solution without considering space
 public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>();
        if (rowIndex == 0) {
            result.add(1);
            return result;
        }
       
        List<Integer> currList = getRow(rowIndex - 1);
        List<Integer> newList = new ArrayList<Integer>();
        newList.add(1);
        for (int i = 0; i < currList.size() - 1; i++) {
            newList.add(currList.get(i) + currList.get(i+1));
        }
        newList.add(1);
        return newList;
    }

Consider about the space.
Collections.nCopies(n,0) is a smart way to initialize the arraylist as zero.

public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>(Collections.nCopies(rowIndex+1,0));
       
        result.set(0,1);
        for (int i=0; i<=rowIndex; i++) {
            result.set(i,1);
            for (int j=i-1; j>0; j--) {
                result.set(j, result.get(j)+result.get(j-1));
            }
        }
        return result;
    }

No comments:

Post a Comment