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];
    }
};

/*
    滚动数组优化

    时间复杂度：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];
    }
};

class Solution_2 {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> f(rowIndex+1, 0); // 初始化为 0
        f[0] = 1; // 第一个元素始终是 1

        for (int i = 1; i <= rowIndex; i++) {
            // 从后向前更新，防止覆盖前面的数据
            for (int j = i; j >= 1; j--) {
                f[j] = f[j] + f[j-1];
            }
        }

        return f;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

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

    for (int i = 0; i < rows_cases.size(); i++) {
        int rows = rows_cases[i];
        vector<int> result = solution.getRow(rows);

        cout << "Input: rowIndex = " << rows << endl;
        cout << "Output: ";
        printArray(result);
        cout << endl;
    }

    return 0;
}