119. 杨辉三角 II

xiaoxiao2021-02-28  13

给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。

在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

输入: 3 输出: [1,3,3,1]

进阶:

你可以优化你的算法到 O(k) 空间复杂度吗?


解题思路:和杨辉三角一样的处理方式 class Solution { public: vector<int> getRow(int rowIndex) { vector<vector<int>>v(rowIndex); vector<int>t; if(rowIndex==0){ t.push_back(1); return t; } for(int i=0;i<rowIndex+1;i++){ if(i<rowIndex){ v[i].resize(i+1); v[i][0]=1; v[i][i]=1; for(int j=1;j<i;j++){ v[i][j]=v[i-1][j]+v[i-1][j-1]; } } if(i==rowIndex){ t.push_back(1); for(int j=1;j<i;j++){ t.push_back(v[i-1][j]+v[i-1][j-1]); } t.push_back(1); } } return t; } };
转载请注明原文地址: https://www.6miu.com/read-2450205.html

最新回复(0)