สมมติว่าเรามีดัชนีไม่เป็นลบ k โดยที่ k ≤ 33 เราต้องหาแถวดัชนีที่ k ของสามเหลี่ยมปาสกาล
ดังนั้น หากอินพุตเท่ากับ 3 เอาต์พุตจะเป็น [1,3,3,1]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดปาสกาลอาร์เรย์ของขนาด rowIndex + 1 และเติมด้วย 0
-
สำหรับการเริ่มต้น r :=0 เมื่อ r <=rowIndex อัปเดต (เพิ่ม r ขึ้น 1) ทำ -
-
ปาสกาล[r] :=1, ก่อนหน้า :=1
-
สำหรับการเริ่มต้น i :=1 เมื่อฉัน
-
cur :=ปาสกาล[i]
-
ปาสกาล[i] :=ปาสกาล[i] + ก่อนหน้า
-
ก่อนหน้า :=cur
-
-
-
ส่งคืนปาสกาล
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> pascal(rowIndex + 1, 0);
int prev, cur, r, i;
for (r = 0; r <= rowIndex; r++) {
pascal[r] = prev = 1;
for (i = 1; i < r; i++) {
cur = pascal[i];
pascal[i] += prev;
prev = cur;
}
}
return pascal;
}
};
main(){
Solution ob;
print_vector(ob.getRow(3));
} อินพุต
3
ผลลัพธ์
[1, 3, 3, 1, ]
