首页 > 代码库 > Pascal's Triangle II

Pascal's Triangle II

本文是在学习中的总结,欢迎转载但请注明出处:http://blog.csdn.net/pistolove/article/details/41851069


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?


思路:

(1)这道算法题是Pascal‘s Triangle的改进版。如果知道Pascal‘s Triangle如何解答,那么这道题也就很简单了。

(2)不同的是,这道题的起始位置是从0开始,需要特别注意下。

(3)本文的思路和Pascal‘s Triangle思路基本一样(Pascal‘s Triangle请详见http://blog.csdn.net/pistolove/article/details/41827325),Pascal‘s Triangle结果是要给出每一行的数字,这道题仅仅给出num所在行的数字。本文是通过遍历2-num行(0行和1行特殊处理),每遍历一行就将该行的数字存到链表中,当遍历完该行的下一行时,将下一行的数字替换上一行的数字,遍历完所有行,最后得到链表中的数字就是结果。

(4)需要注意的是:本文的空间复杂度不是O(K),而是在O(K)和O(2K)之间,如果想要空间复杂度为O(K),则需申请一个K大小的数组,并在遍历的过程中依次替换每行中间的数字,其实也不难实现,感兴趣可以研究下,对自己也有提高。

(5)希望本文能对你有所帮助。有问题可留言,我会尽快回复。谢谢。


算法代码实现如下所示:

public static List<Integer> getSingle(int num){
	List<Integer> row = new LinkedList<Integer>();
	if(num==0){
		row.add(1);
		return row;
	}
	
	if(num==1){
		row.add(1);
		row.add(1);
		return row;
	}

	if(num>1){
		row.add(1);
		row.add(1);
		for (int i=2; i <= num; i++) {
			List<Integer> temp = new LinkedList<Integer>();
			for (int j = 0; j < i+1; j++) {
				if(j==0) 
					temp.add(1);
				if(j==i)
					temp.add(1);
				if(j!=0 && j!=i){
					temp.add(row.get(j-1)+row.get(j));
				}
			}
			row=temp;
		}
	}
	return row;
}


Pascal's Triangle II