免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

楊輝三角

題目描述

給定一個(gè)非負(fù)索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行。

在楊輝三角中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。

示例 1:

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

進(jìn)階:

你可以優(yōu)化你的算法到 O(k) 空間復(fù)雜度嗎？

思路1

初始化前兩層，后面層直接累加左上方和右上方的數(shù)的和

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

class Solution {public:    //思路：初始化前兩層，后面層直接累加左上方和右上方的數(shù)的和    vector<vector<int>> generate(int numRows) {        vector<vector<int>> result(numRows);        if(numRows == 0){ return result;}        else if(numRows == 1)        {            result[0].push_back(1);            return result;        }        else if(numRows == 2)        {            result[0].push_back(1);            result[1].push_back(1);            result[1].push_back(1);             return result;        }        else{            result[0].push_back(1);            result[1].push_back(1);            result[1].push_back(1);            for(int i = 2; i < numRows;   i)            {                for(int j = 0; j <= i;   j)                {                    if(j == 0){result[i].push_back(1);}                    else if(j == i){result[i].push_back(1);}                    else{                        //cout<<" "<<result[i-1][j-1]<<"  "<<result[i-1][j]<<endl;                        int tmp = result[i-1][j-1]   result[i-1][j];                        result[i].push_back(tmp);                    }                }            }        }        return result;    }};

思路2

進(jìn)階，空間復(fù)雜度O(K),因?yàn)橐褂肙(K)的空間復(fù)雜度，所以創(chuàng)建rowIndex 1個(gè)元素的數(shù)組，因?yàn)榈趓owIndex行有rowIndex 1個(gè)元素從第1行開(kāi)始計(jì)算直到rowIndex層，每一層計(jì)算該層具體數(shù)值，需要注意從后往前計(jì)算，避免了第i-1行計(jì)算結(jié)果被覆蓋丟失

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

class Solution {public:    //思路：因?yàn)橐褂肙(K)的空間復(fù)雜度，所以創(chuàng)建rowIndex   1個(gè)元素的數(shù)組，因?yàn)榈趓owIndex行有rowIndex   1個(gè)元素    //從第1行開(kāi)始計(jì)算直到rowIndex層，每一層計(jì)算該層具體數(shù)值，需要注意從后往前計(jì)算，避免了第i-1行計(jì)算結(jié)果被覆蓋丟失    vector<int> getRow(int rowIndex) {        vector<int> result(rowIndex   1,0);        result[0] = 1;        for(int i = 1; i <= rowIndex;   i){//表示第i行            for(int k = i; k > 0; --k){//k是第k個(gè)數(shù) 從i開(kāi)始，是因?yàn)榈趇行共有i 1個(gè)數(shù)字，從后往前計(jì)算，避免了第i-1行計(jì)算結(jié)果被覆蓋丟失                result[k] = result[k]   result[k-1];            }        }        return result;    }};