My 8 lines java solution use ArrayList


  • 39
    G
    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<Integer>();
        for(int i = 0;i<rowIndex+1;i++) {
        		res.add(1);
        		for(int j=i-1;j>0;j--) {
        			res.set(j, res.get(j-1)+res.get(j));
        		}
        }
        return res;
    }

  • 1
    for(int j=i-1;j>0;j--)
    

    Cool! I never thought of using a backward order. That successfully avoid creating a new list. Thanks!


  • 0
    E

    Nice solution!

    I have a little modification though. If using LinkedList instead of ArrayList, starting from left will still be okay, because insertion in LinkedList only takes O(1) time. Here is my revised code.

    public List<Integer> getRow(int rowIndex) {
        List<Integer> ret = new LinkedList<Integer>();
        for (int row = 0; row <= rowIndex; row++) {
            ret.add(0, 1);
            for (int i = 1; i < row; i++)
                ret.set(i, ret.get(i) + ret.get(i + 1));
        }
        return ret;
    }
    

    Same amount of code. :)


  • 1
    V

    ret.get(i)是因为你的使用链表现在最坏情况下 O(n) 的时间


  • 0
    E

    Yes you are right... I missed that part. My apology.


  • 0
    Y

    Nice solution. Thanks for sharing. Can you or anybody else tell me the time complexity? Thanks.


  • 0
    G

    @ynys I think the time complexity may be O(n^3), because the time complexity may be similar to 1^2 + 2^2 + ... + n^2. Correct me if I am wrong.


  • 0
    N
    public class Solution {
        public List<Integer> getRow(int k) {
            
            List<Integer> a = new ArrayList<Integer>(k+1);
            a.add(1);
            
            for(int row=1; row <= k; row++){
                a.set(0,1);
                int curr = 1, prev = 1;
                int i=1;
                for(; i <= row-1; i++){
                    curr = a.get(i);
                    a.set(i, curr + prev);
                    prev = curr;
                }
                a.add(i,1);
            }
            
            return a;
            
        }
    }
    

Log in to reply
 

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