Vấn đề
Cho chỉ số k không âm trong đó k ≤ 33, trả về hàng chỉ số thứ k của tam giác Pascal
Lưu ý rằng chỉ số hàng bắt đầu từ 0
Trong tam giác Pascal, mỗi số bằng tổng của hai số ngay phía trên nó
Ví dụ
Input: 3 Output: [1,3,3,1]Theo sát
Bạn có thể tối ưu hóa thuật toán của mình để chỉ sử dụng không gian thừa O(k) không?
Giải pháp 1
/** * @param {number} rowIndex * @return {number[]} */ var getRow = function(rowIndex) { var res = []; var i = 0; var j = 0; for (i = 0; i <= rowIndex; i++) { res.unshift(1); for (j = 1; j < i; j++) { res[j] += res[j + 1]; } } return res; };Giải thích
không
phức tạp
- Độ phức tạp về thời gian. O(n^2)
- Độ phức tạp của không gian. Trên)
Giải pháp 2
/** * @param {number} rowIndex * @return {number[]} */ var getRow = function(rowIndex) { var res = Array(rowIndex + 1); var i = 0; var j = 0; for (i = rowIndex; i >= 0; i--) { res[i] = 1; for (j = i + 1; j < rowIndex; j++) { res[j] += res[j + 1]; } } return res; };Giải thích
không
phức tạp
- Độ phức tạp về thời gian. O(n^2)
- Độ phức tạp của không gian. Trên)
Giải pháp 3
/** * @param {number} rowIndex * @return {number[]} */ var getRow = function(rowIndex) { var res = Array(rowIndex + 1); res[0] = 1; for (var i = 1; i <= rowIndex; i++) { res[i] = res[i - 1] * ((rowIndex - i + 1) / i); } return res; };Giải thích
在第 k 行，第 i 个元素，/** * @param {number} rowIndex * @return {number[]} */ var getRow = function(rowIndex) { var res = []; var i = 0; var j = 0; for (i = 0; i <= rowIndex; i++) { res.unshift(1); for (j = 1; j < i; j++) { res[j] += res[j + 1]; } } return res; }; 0。
phức tạp
- Độ phức tạp về thời gian. Trên)
- Độ phức tạp của không gian. Trên)
Trong bài giải Leetcode Pascal's Triangle II này, chúng ta có một số nguyên rowIndex, trả về hàng rowIndexth (0-indexed) của tam giác Pascal. Trong tam giác Pascal, mỗi số bằng tổng của hai số ngay phía trên nó
Giải pháp vấn đề trong Python
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
if rowIndex == 0:
return [1]
if rowIndex == 1:
return [1, 1]
if rowIndex == 2:
return [1, 2, 1]
ans = [1] * (rowIndex + 1)
prev = [1, 2, 1]
for i in range(3, rowIndex + 1):
for j in range(1, i):
ans[j] = prev[j] + prev[j - 1]
prev = ans[:]
return ans
Giải pháp vấn đề trong Java
public List<Integer> getRow(int rowIndex) {
List<Integer> result = new ArrayList<>();
result.add(1);
if(rowIndex==0) return result;
List<Integer> prev = getRow(rowIndex-1);
for(int i=0; i<prev.size()-1;i++){
result.add(prev.get(i)+prev.get(i+1));
}
result.add(1);
return result;
}
Giải pháp vấn đề trong C++
class Solution {
public:
vector<int> getRow(int rowIndex) {
++rowIndex;
std::vector<int> res(rowIndex, 1);
for(int i{1}; i < rowIndex; ++i) res[i] = (int64_t) res[i-1] * (rowIndex-i) / i;
return res;
}
};
Giải quyết vấn đề trong C
int* getRow(int rowIndex, int* returnSize) { int *result = malloc((rowIndex + 1) * sizeof(int)); int i, j, new, old = 1; *returnSize = rowIndex + 1; for (i = 0; i <= rowIndex; i++) { result[i] = 1; for (j = 1; j < i; j++) { new = result[j]; result[j] += old; old = new; } } return result; }