題目描述（?？途W(wǎng)）：

給出一個(gè)索引k，返回楊輝三角的第k行

例如，k=3，

返回[1,3,3,1].

備注：

你能將你的算法優(yōu)化到只使用O(k)的額外空間嗎?

Given an index k, return the k th 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?

在Pascal三角形中，每個(gè)數(shù)字都是其正上方兩個(gè)數(shù)字的和。

例：

Input: 3 Output: [1,3,3,1]

主要思想：

題意是指定行數(shù)，輸出楊輝三角形的某行的元素值。

由于下一層比上一層多一個(gè)數(shù)，只需將上層的List增加1，然后向前做更新、覆蓋即可，不用額外開辟新的存儲(chǔ)空間；共用一個(gè)List，空間復(fù)雜度為O(k)。

實(shí)現(xiàn)代碼：

import java.util.ArrayList;public class Solution {public ArrayList<Integer> getRow(int rowIndex) {ArrayList<Integer> list = new ArrayList<>();for (int i = 0; i <= rowIndex; i++) {list.add(1);for (int j = i - 1; j > 0; j--) {list.set(j, list.get(j - 1) + list.get(j));}}return list;} }

注意：只能第二重 for 只能向前做遍歷；如果先后遍歷做覆蓋的話，則會(huì)使得后面使用的數(shù)并非原來(lái)的數(shù)，而是更新后的數(shù)。

總結(jié)

以上是生活随笔為你收集整理的LeetCode_Pascal's Triangle II_杨辉三角形II（Java实现）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。