一、題目描述

力扣原題

• 首先我們要來了解一下題目本身在說些什么，通過下方的動圖我們可以更加清楚地看到楊輝三角是怎樣一步步生成的。給到的示例中我們通過輸入楊輝三角的行數(shù)，然后通過計算得到這個楊輝三角的每一行是什么具體的數(shù)值

二、模型選擇

首先我們要做的第一件事就是去選擇正確的求解模型

• 首先第一點，我們要來對比一下使用C語言求解和C++求解有什么不同，以下是題目已經(jīng)給出的函數(shù)接口

• 如果讀者有學習過 C語言的指針 和 C++的引用 的話就可以知道，C++的祖師爺為什么要發(fā)明出引用這個東西，目的就是為了脫離C語言中非常繁雜的指針

我可以試著來分析一下如何使用C語言來進行求解，首先我們來看到的是這個 返回值int**

• 為什么要返回int**呢，原因就在于對于我們這個楊輝三角來說，雖然呈現(xiàn)的是一個三角形的樣子，但是呢其底層的實現(xiàn)其實還是一個二維數(shù)組，所以在函數(shù)內(nèi)部我們肯定要去開辟出一個二維數(shù)組，讀者可以通過下面這張圖再來回顧一下有關(guān)二級指針的知識點（忘記了可以去看看指針相關(guān)文章）

• 看完了返回值后，我們再來看看另外的兩個參數(shù)，第一個是這個returnSize，其代表的是整個二維矩陣的行數(shù)，而returnColumnSizes代表的則是每一行的列數(shù)。
• 但為何它們的類型一個是一級指針int*，另一個則是二級指針int**呢？如果你有看過 二叉樹練習題之二叉樹的遍歷 的話就可以知道它們都叫做輸出型參數(shù)

• 在講解 函數(shù)棧幀 的時候我們說到過這個函數(shù)的形參是實參的一份臨時拷貝，內(nèi)部形參的改動是不會影響實參的，所以我們在做二叉樹題目的時候如果對這個參數(shù)沒有做特殊處理的話在不同的遞歸層中就會出現(xiàn) 覆蓋問題
• 所以我們?nèi)羰窍胱屝螀?nèi)部的變化帶動外部一起修改的話，就需要外部傳遞變量的地址進來，那對于地址而言就需要使用 指針 來進行接收，一級指針的地址就需要二級指針來接收

所以就這么來看，我們?nèi)羰鞘褂肅語言來求解本題的話，就會變得很麻煩

• 那這個時候就可以使用我們心愛的C++了??

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        
    }
};

• 在C++中呢，我們一般不會使用指針來模擬二維數(shù)組，而是會采取vector<vector<int>>來進行表示

三、思路分析 + 代碼詳解

接下去我們就來分析一下這道題的思路??

• 還記得下面這個動圖嗎，仔細觀察我們可以發(fā)現(xiàn)每一行的第一個和最后一個數(shù)字都是1。而且中間空缺處的方塊都是其 左上方的數(shù)字 + 右上方的數(shù)字

• 具體地可以看以下的圖示

【思路簡述】：說一下我是如何去求解這道題的

• 首先的話我們肯定需要先去定義出一個有關(guān)vector的二維矩陣

vector<vector<int>> vv;

• 接下去呢便要為這個二維矩陣開辟出合適的大小來容納，這里便可以使用到我們在vector中所學習的【resize】接口，既改變了size，又改變了capacity

vv.resize(numRows);

• 因為矩陣中的每一行的第一個元素和最后一個元素都是1，所以我先去遍歷這個矩陣，將所有的值設置為0，接下去呢再固定地將每一行的第一個元素vv[i][0]和最后一個元素vv[i][i]都設置為1

for(size_t i = 0;i < vv.size(); ++i)
{
    // 首先將二維數(shù)組中的所有元素初始化為0
    vv[i].resize(i + 1, 0);
    // 然后將每一行的第一個和最后一個元素初始化為1
    vv[i][0] = vv[i][i] = 1;
}

• 接下去呢，就要去計算每一行的具體數(shù)值了，通過兩層for循環(huán)去遍歷這個二維矩陣，接下去呢我們只對數(shù)值為0的位置進行修改，因為每行的第一列和最后一列已經(jīng)為1了，所以我們?nèi)バ薷牡闹皇侵虚g的那一部分

for(size_t i = 0;i < vv.size(); ++i)
{
    for(size_t j = 0;j < vv[i].size(); ++j)
    {
        if(vv[i][j] == 0)
        {
            // 右上方：vv[i - 1][j]
            // 左上方：vv[i - 1][j - 1]
            vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
        }
    }
}

對于當前的這個值就等于其上方的那一個數(shù)和上方左側(cè)的那一個數(shù)之和

vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];

整體代碼展示：

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows);

        for(size_t i = 0;i < vv.size(); ++i)
        {
            // 首先將二維數(shù)組中的所有元素初始化為0
            vv[i].resize(i + 1, 0);
            // 然后將每一行的第一個和最后一個元素初始化為1
            vv[i][0] = vv[i][i] = 1;
        }

        for(size_t i = 0;i < vv.size(); ++i)
        {
            for(size_t j = 0;j < vv[i].size(); ++j)
            {
                if(vv[i][j] == 0)
                {
                    // 右上方：vv[i - 1][j]
                    // 左上方：vv[i - 1][j - 1]
                    vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
                }
            }
        }
        return vv;
    }
};

運行結(jié)果：

文章來源地址http://www.zghlxwxcb.cn/news/detail-624525.html

到了這里，關(guān)于【LeetCode】探索楊輝三角模型的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！