Alibi

My Life is Getting Better

Leetcode[118, 119] Pascal's Triangle

08 Nov 2015

###Task1 Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5, Return

[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

###Python

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        ret = []
        for i in range(numRows):
            res = [1 for j in range(i + 1)]
            if i > 1:
                for k in range(1, i):
                    res[k] = ret[i - 1][k] + ret[i - 1][k - 1]
            ret.append(res)
        return ret

###Java

import java.util.*;

public class Solution {

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (numRows < 1) {
        	return res;
        }
        for (int i = 1; i <= numRows; i++) {
        	List<Integer> temp = new ArrayList<Integer>();
        	temp.add(1);
        	for (int j = 1; j < i; j++) {
        		int left = res.get(i - 2).get(j - 1);
        		int right = j <= (i - 2) ? res.get(i - 2).get(j) : 0;
        		temp.add(left + right);   
        	}
        	res.add(temp);
        }

        return res;
    }
}

###Points

算法时间复杂度应该是O(1+2+3+…+n)=O(n^2)，空间上只需要二维数组来存储结果，不需要额外空间

###Task2 Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3, Return [1,3,3,1].

Note: Could you optimize your algorithm to use only O(k) extra space?

###Python ####one way

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        if rowIndex == 0:
            return [1]
        ret = [1]
        for i in range(1, rowIndex + 1):
            for j in range(len(ret) - 2, -1, -1):
                ret[j + 1] += ret[j]
            ret.append(1)
        return ret

####another

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        ret = [1 for i in range(rowIndex + 1)]
        for i in range(rowIndex + 1):
            for j in range(i - 1, 0, -1):
                ret[j] += ret[j - 1]
        return ret

###Java

import java.util.*;

public class Solution {
    public List<Integer> getRow(int rowIndex) {
    	List<Integer> res = new ArrayList<Integer>();
        if (rowIndex < 0) {
        	return res;
        }
        res.add(1);
        for (int i = 1; i <= rowIndex; i++) {
        	for (int j = res.size() - 2; j >= 0; j--) {
        		res.set(j + 1, res.get(j) + res.get(j + 1));
        	}
        	res.add(1);
        }

        return res;
    }

    public static  void main(String[] args) {
    	Solution sol = new Solution();
    	System.out.println(sol.getRow(3));
    }
}

###Points

时间复杂度还是O(n^2)，而空间这里是O(k)来存储结果，仍然不需要额外空间

Related Posts