[LeetCode 笔记] 118. Pascal's Triangle

前言

　　这题的大方向是要如何找到上一行的上一列的元素来做两两相加的运算，像是动态规划的逻辑思考，需要用到双迴圈的关係，时间複杂度达 O(n²)，这里有 JAVA 和 Python 的写法。

题目

Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

给定一个整数 numRows，回传一个相对应层数的帕斯卡三角形。
在帕斯卡三角形里遍历的每个数字，都是其上方两个数的合：

题目连结：https://leetcode.com/problems/pascals-triangle/

题目限制

1 <= numRows <= 30

範例

Input: numRows = 5Output:[     [1],    [1,1],   [1,2,1],  [1,3,3,1], [1,4,6,4,1]]

Input: numRows = 1Output: [[1]]

思路&笔记

这题的大方向是要如何找到上一行的上一列的元素来做两两相加的运算，像是动态规划的逻辑思考。

首先我们把帕斯卡三角形想像成一个大型的 List，再把这个大型的 List 里的每个元素放入个别 List 里来当作每一列。已经有了两个要件，接着用双迴圈去遍历大型的 List 里的每一列放我们要放的元素。可是不要忘了要判断每一列的头跟尾都要是 1 才能把对的元素放在对位置。解决头尾已经是 1 了，再把前一列的两值加起来后依依放进去。 (这边要注意，因我们用的是 ArrayList 类，需要用 .get() 方法来取得元素的位置)最后把每一列放入大型的 List 里。

JAVA 实现

class Solution {    public List<List<Integer>> generate(int numRows) {        // 创建二维列表        List<List<Integer>> nums = new ArrayList<List<Integer>>();        // 为了防止无效输入，直接回传一个空的列表        if (numRows <= 0){            return nums;        }                for (int i=0; i<numRows; i++){            // 每一列            List<Integer> row = new ArrayList<Integer>();            // 如果第一行要生成数字，j<i => 0<0 无法成立，i 应要 +1            for(int j=0; j<i+1; j++){                 // 判断 list 的头尾 (到了第5行要总生成5个数字，最后一个数字)                if (j==0 || j==i){                    row.add(1); // 是 0 的话插入 1                }else {                    // 因要从二维列表取值，从第 i-1 行中取得第 j-1 的元素                    row.add(nums.get(i-1).get(j-1) + nums.get(i-1).get(j)); // 把前一列的两值加起来                }            }            nums.add(row); // 把列表插入二维列表        }        return nums;    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def generate(self, numRows: int) -> List[List[int]]:        nums = [] # 大三角形        for i in range(numRows):            row = [] # 每行            for j in range(len(nums)+1):                if j==0 or j==i: # 判断头尾                    row.append(1)                else:                    row.append(nums[i-1][j-1] + nums[i-1][j]) # 把前一列的两值加起来            nums.append(row)        return nums

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/05/28/LeetCode-118-Pascal-s-Triangle-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论