แนวคิด
สมมติว่ามีดัชนี k ที่ไม่เป็นลบ โดย k <= 33 ให้หาแถวที่ k ของสามเหลี่ยมพาสคาล
เช่น ถ้าอินพุตคือ 3 ผลลัพธ์คือ [1,3,3,1]
วิธีแก้:
- กำหนดอาร์เรย์ pascal ขนาด rowIndex + 1 เติม 0
- วนลูป r := 0 ถึง rowIndex:
- pascal[r] := 1, prev := 1
- วนลูป i := 1 ถึง r - 1: cur := pascal[i], pascal[i] := pascal[i] + prev, prev := cur
- คืนค่า pascal
ตัวอย่าง
#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, ]
