leetcode119：杨辉三角II

题目链接

leetcode

题目描述

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    从上到下依次计算每一行。
    对于每一行，先把 1 放在首尾两个位置，
    然后计算中间的数：f[i][j] = f[i-1][j-1] + f[i-1][j]

    时间复杂度：O(n^2)
    空间复杂度：O(n^2)
*/
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<vector<int>> f(rowIndex + 1, vector<int>(rowIndex + 1));
        for (int i = 0; i <= rowIndex; i ++) {
            f[i][0] = f[i][i] = 1;
            for (int j = 1; j < i; j ++) {
                f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
            }
        }

        return f[rowIndex];
    }
};

/*
    滚动数组优化：机械化套路（& 1）

    时间复杂度：O(n^2)
    空间复杂度：O(n)
*/
class Solution_1 {
public:
    vector<int> getRow(int rowIndex) {
        vector<vector<int>> f(2, vector<int>(rowIndex + 1));
        for (int i = 0; i <= rowIndex; i ++) {
            f[i & 1][0] = f[i & 1][i] = 1;
            for (int j = 1; j < i; j ++) {
                f[i & 1][j] = f[i - 1 & 1][j - 1] + f[i - 1 & 1][j];
            }
        }

        return f[rowIndex & 1];
    }
};

int main() {
    Solution solution;
    vector<int> test_cases = { 3, 0, 1 };

    for (auto& numRows : test_cases) {
        cout << "Input: " << numRows << endl;
        cout << "Output: ";
        vector<int> result = solution.getRow(numRows);
        for (const auto& num : result) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}