C++實現(xiàn)LeetCode(119.楊輝三角之二)
[LeetCode] 119. Pascal's Triangle II 楊輝三角之二
Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.
Note that the row index starts from 0.
In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 3
Output: [1,3,3,1]
Follow up:
Could you optimize your algorithm to use only O(k) extra space?
楊輝三角想必大家并不陌生,應該最早出現(xiàn)在初高中的數(shù)學中,其實就是二項式系數(shù)的一種寫法。
1
1?。?br /> 1?。病。?br /> 1?。场。场。?br /> 1 4?。丁。础。?br /> 1?。怠?0 10 5?。?br /> 1 6 15 20 15?。丁。?br /> 1?。贰?1 35 35 21?。贰。?br /> 1?。浮?8 56 70 56 28 8?。?/p>
楊輝三角形第n層(頂層稱第0層,第1行,第n層即第 n+1 行,此處n為包含0在內的自然數(shù))正好對應于二項式 \left(a+b\right)^{n} 展開的系數(shù)。例如第二層 1 2 1 是冪指數(shù)為2的二項式\left(a+b\right)^{2} 展開形式a^{2}+2ab+b^{2} 的系數(shù)。
由于題目有額外限制條件,程序只能使用 O(k) 的額外空間,那么這樣就不能把每行都算出來,而是要用其他的方法, 我最先考慮用的是第三條性質,算出每個組合數(shù)來生成第n行系數(shù)。本地調試輸出前十行,沒啥問題,拿到 OJ 上測試,程序在第 18 行跪了,中間有個系數(shù)不正確。那么問題出在哪了呢,仔細找找,原來出在計算組合數(shù)那里,由于算組合數(shù)時需要算連乘,而整型數(shù) int 的數(shù)值范圍只有 -32768 到 32768 之間,那么一旦n值過大,連乘肯定無法計算。而喪心病狂的 OJ 肯定會測試到成百上千行,所以這個方法不行。那么我們再來考慮利用第五條性質,除了第一個和最后一個數(shù)字之外,其他的數(shù)字都是上一行左右兩個值之和。那么我們只需要兩個 for 循環(huán),除了第一個數(shù)為1之外,后面的數(shù)都是上一次循環(huán)的數(shù)值加上它前面位置的數(shù)值之和,不停地更新每一個位置的值,便可以得到第n行的數(shù)字,具體實現(xiàn)代碼如下:
class Solution { public: vector<int> getRow(int rowIndex) { vector<int> res(rowIndex + 1); res[0] = 1; for (int i = 1; i <= rowIndex; ++i) { for (int j = i; j >= 1; --j) { res[j] += res[j - 1]; } } return res; } };
Github 同步地址:
https://github.com/grandyang/leetcode/issues/119
類似題目:
參考資料:
https://leetcode.com/problems/pascals-triangle-ii/
https://leetcode.com/problems/pascals-triangle-ii/discuss/38420/Here-is-my-brief-O(k)-solution
到此這篇關于C++實現(xiàn)LeetCode(119.楊輝三角之二)的文章就介紹到這了,更多相關C++實現(xiàn)楊輝三角之二內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
VisualStudio2022提交git代碼的方法實現(xiàn)
本文主要介紹了VisualStudio2022提交git代碼的方法實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-07-07C++實現(xiàn)完整功能的通訊錄管理系統(tǒng)詳解
來了來了,通訊錄管理系統(tǒng)踏著七彩祥云飛來了,結合前面的結構體知識和分文件編寫方法,我總結并碼了一個帶菜單的通訊錄管理系統(tǒng),在這篇文章中將會提到C的清空屏幕函數(shù),嵌套結構體具體實現(xiàn),簡單且充實,跟著我的思路,可以很清晰的解決這個項目2022-05-05C語言中fgetgrent()函數(shù)和fgetpwent()函數(shù)的用法對比
這篇文章主要介紹了C語言中fgetgrent()函數(shù)和fgetpwent()函數(shù)的用法對比,分別用于讀取組格式函數(shù)和讀取密碼格式,需要的朋友可以參考下2015-08-08