Day11 Pascal's Triangle II
LeetCode 119. Pascal's Triangle II
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?
题目很简单,求奥斯卡三角形的某一层,但是要求是要使用不超过O(K)的额外空间,这个题本身就是返回一个数组,其最后的大小就是O(K),也就是说,只能在一个数组里进行原地操作。
稍加思考会发现其实不难,每一层这个数组总是以1开头,1结尾的,中间的则等于当前位置的数与前一个数的和,唯一需要注意的是,每次操作完,当前位置的前一个数很有可能是之前已经操作过的数,这样算就不对了。所以需要一个变量来保存原来的值。