??前面的話??
大家好！本篇文章將介紹力扣[118. 楊輝三角]與[119. 楊輝三角 II]題解，展示代碼語言暫時為：C語言，（后續會更新Java與C++代碼）
📒博客主頁：未見花聞的博客主頁
🎉歡迎關注🔎點贊👍收藏??留言📝
📌本文由未見花聞原創，CSDN首發！
📆首發時間：🌴2021年10月25日🌴
??堅持和努力一定能換來詩與遠方！
💭刷題推薦書籍：📚《劍指offer第1版》，📚《劍指offer第2版》
💬參考在線編程網站：🌐牛客網🌐力扣
🙏作者水平很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！
博主的碼云gitee，平常博主寫的程式代碼都在里面，
📌導航小助手📌
- ??LeetCode118. 楊輝三角??
- 🔐題目詳情
- 💡解題思路
- 🔑源代碼
- ??LeetCode119. 楊輝三角 II??
- 🔐題目詳情
- 💡解題思路
- 🔑源代碼
- 🌱總結
??LeetCode118. 楊輝三角??
🔐題目詳情
給定一個非負整數 numRows，生成「楊輝三角」的前 numRows 行，
在「楊輝三角」中，每個數是它左上方和右上方的數的和，
示例：
輸入: numRows = 5
輸出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
輸入: numRows = 1
輸出: [[1]]
提示：
1 <= numRows <= 30
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/pascals-triangle/
💡解題思路
楊輝三角的一些基本性質：
💡楊輝三角每行第一個數和最后一個數為1，
💡楊輝三角第n行數字的個數為n，
💡設一個楊輝三角有n行m列(0<n<21，0<m<21)，并將這個楊輝三角所有元素對應行列存入二維陣列tri[20][20]中，n>2時，則tri[n][m] = tri[n-1][m-1] +tri[n-1][m]，
所以我們可以以tri[n][m] = tri[n-1][m-1] +tri[n-1][m]為突破口，解決這道題，
這道題其實不難，難點在于二維陣列的記憶體申請，本文重點為題解，二維陣列記憶體申請不多贅述！
🔑源代碼
int** generate(int numRows, int* returnSize, int** returnColumnSizes){
int i = 0;
int j = 0;
int** arr = (int**)malloc(sizeof(int*) * numRows);//申請int* 型別的陣列，數量為行數，里面的int* 用來指向每行所對應的一維陣列
*returnColumnSizes = (int*)malloc(sizeof(int) * numRows);//回傳每行一維陣列元素的個數，題目需要回傳
for (i = 0; i < numRows; i++)
{
(*returnColumnSizes)[i] = i + 1;
arr[i] = (int*)malloc(sizeof(int) * (i + 1));//為每行的一維陣列申請空間
for (j = 0; j < i + 1; j++)
{
if (i < 2 || j == 0 || j == i)
{
arr[i][j] = 1;//前兩行與每行首末元素均為1
continue;
}
arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];//楊輝三角中間元素為上一行相鄰兩元素和
}
}
*returnSize = numRows;
return arr;
}
??LeetCode119. 楊輝三角 II??
🔐題目詳情
給定一個非負索引 rowIndex，回傳「楊輝三角」的第 rowIndex 行，
在「楊輝三角」中，每個數是它左上方和右上方的數的和，
💡解題思路
解法1：構造楊輝三角，找到第rowIndex行，并回傳結果，
基于解法1的基礎上，我們可以優化空間復雜度，使用滾動陣列解決，解法2出現了，
所謂滾動陣列，就是使用兩個陣列輪換求值，
解法2：由于每行的首末元素均為1，所以默認將需要相互輪替的兩個陣列首末元素賦值為1，進行滾動陣列時不必考慮首末兩位置，
🔑源代碼
int* getRow(int rowIndex, int* returnSize){
int row = rowIndex + 1;//總行數
int* arr = (int*)malloc(sizeof(int) * row);//陣列1，
int* pre = (int*)malloc(sizeof(int) * row);//陣列2，相當于arr行前一行
int i = 0;
int j = 0;
arr[0] = 1;
pre[0] = 1;
arr[row - 1] = 1;
pre[row - 1] = 1;//首末元素賦值為1
for (i = 1; i < row - 1; i++ )
{
pre[i] = 1;//保證相對末位置值為1
for (j = 1; j <= i; j++)
{
arr[j] = pre[j] + pre[j - 1];//一行中間元素的值為上一行相鄰兩元素之和
}
int* tmp = pre;
pre = arr;
arr = tmp;//輪換陣列，重繪pre陣列，如果此時回圈結束，pre為目標行陣列
}
*returnSize = row;
return pre;//輪換后，最新陣列為pre
}
🌱總結
解決楊輝三角的關鍵是每行首末位置元素為1，第三行開始每行中間的元素的值為前一行相同列與前一列所對應的兩元素之和，即
tri[n][m] = tri[n-1][m-1] +tri[n-1][m]，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/337750.html
標籤：其他