C#LeetCode刷题之#118-杨辉三角（Pascal‘s Triangle）

问题

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

输入: 5

输出:

[

[1],

[1,1],

[1,2,1],

[1,3,3,1],

[1,4,6,4,1]

]

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Input: 5

Output:

[

[1],

[1,1],

[1,2,1],

[1,3,3,1],

[1,4,6,4,1]

]

示例

public class Program {

    public static void Main(string[] args) {

        var res = Generate(5);

        ShowArray(res);

        Console.ReadKey();

    }

    private static void ShowArray(IList<IList<int>> array) {

        foreach(var num in array) {

            foreach(var num2 in num) {

                Console.Write($"{num2} ");

            }

            Console.WriteLine();

        }

        Console.WriteLine();

    }

    private static IList<IList<int>> Generate(int numRows) {

        if(numRows == 0) {

            return new int[][] { };

        }

        int[][] res = new int[numRows][];

        for(int i = 0; i < res.Length; i++) {

            res[i] = new int[i + 1];

        }

        res[0][0] = 1;

        for(int i = 1; i < numRows; i++) {

            res[i][0] = 1;

            for(int j = 1; j < i + 1; j++) {

                if(j >= i) {

                    res[i][j] = res[i - 1][j - 1];

                } else {

                    res[i][j] = res[i - 1][j - 1] + res[i - 1][j];

                }

            }

        }

        return res;

    }

}

以上给出1种算法实现，以下是这个案例的输出结果：

分析：

显而易见，以上参考算法在最坏的情况下的时间复杂度为： $O(n^{2})$ ，空间复杂度也为： $O(n^{2})$ 。

巴特西

C#LeetCode刷题之#118-杨辉三角（Pascal‘s Triangle）

最新文章

热门文章