leetcode118：杨辉三角

题目链接

leetcode

题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

C++ 代码

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

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

    时间复杂度：O(n^2)
        假设行数为 n，需要计算 n(n+1)/2 个数字，计算每个数字的时间复杂度是 O(1)，
        所以总时间复杂度是 O(n^2)。
    空间复杂度：O(n^2)
*/
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> f;
        for (int i = 0; i < numRows; i ++) {
            vector<int> line(i + 1);
            line[0] = line[i] = 1;
            for (int j = 1; j < i; j ++) {
                line[j] = f[i - 1][j - 1] + f[i - 1][j];
            }
            f.push_back(line);
        }

        return f;
    }
};

/*
    思路同上
*/
class Solution_1 {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> f(numRows);
        for (int i = 0; i < numRows; i ++) {
            f[i].resize(i + 1);
            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;
    }
};

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

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

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   初始化结果数组：
       创建一个二维数组 result，其中 result[i] 表示第 i+1 行。
       每行的第一个和最后一个元素始终为 1。
   计算中间的值：
       对于每行的中间元素，使用公式 result[i][j] = result[i-1][j-1] + result[i-1][j] 计算。
   返回结果：
       遍历结束后，返回生成的杨辉三角。

   时间复杂度：O(n^2)
       遍历每一行并计算每个元素，时间复杂度为 O(n^2)，其中 n 是生成的行数。
   空间复杂度：O(n^2)
       使用了一个二维数组存储结果，空间复杂度为 O(n^2)。
*/
// generate 生成杨辉三角的前 numRows 行
func generate(numRows int) [][]int {
    if numRows <= 0 {
		return nil
	}

	// 初始化结果数组
	result := make([][]int, numRows)
	for i := 0; i < numRows; i ++ {
		result[i] = make([]int, i + 1)
		result[i][0] = 1
		result[i][i] = 1

		// 计算中间的值
		for j := 1; j < i; j ++ {
			result[i][j] = result[i-1][j-1] + result[i-1][j]
		}
	}

	return result
}

func main() {
	// 测试用例
	testCases := []struct {
		numRows  int
		expected [][]int
	}{
		{
			numRows: 5,
			expected: [][]int{
				{1},
				{1, 1},
				{1, 2, 1},
				{1, 3, 3, 1},
				{1, 4, 6, 4, 1},
			},
		},
		{
			numRows: 1,
			expected: [][]int{
				{1},
			},
		},
		{
			numRows: 0,
			expected: [][]int{},
		},
	}

	for i, tc := range testCases {
		result := generate(tc.numRows)
		fmt.Printf("Test Case %d, Input: numRows = %d\n", i+1, tc.numRows)
		if fmt.Sprint(result) == fmt.Sprint(tc.expected) {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}