力扣118杨辉三角：代码实现+注释详解+其它思考

今天药忘吃喽~ 2024-04-24 14:37 4阅读 0赞

#### 文章目录 ####

*  第一部分：题目
 *  第二部分：代码
 *  第三部分：题解
 *   *  3.1 generate()方法解析
     *  3.2 main方法调用
 *  第四部分：思考

## 第一部分：题目 ##

🏠 链接：[118. 杨辉三角 - 力扣（LeetCode）][118. _ - _LeetCode]

⭐ 难度：简单

![c2f42d28dccfa9fc5c452756bf8f6969.png][]

## 第二部分：代码 ##

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.Scanner;
    
    public class PascalTriangle {
        
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int numRows = scanner.nextInt();
            List<List<Integer>> lists = generate(numRows);
            System.out.println(lists);
            scanner.close();
        }
        public static List<List<Integer>> generate(int numRows) {
        
            List<List<Integer>> lists = new ArrayList<>();
            for (int i =0;i<numRows;i++){
        
                Integer[] array = new Integer[i + 1];
                array[0]=1;
                array[i]=1;
                for (int j = 1;j<=i/2;j++){
        
                    array[j]=lists.get(i-1).get(j)+lists.get(i-1).get(j-1);
                    array[i-j] = array[j];
                }
                lists.add(Arrays.asList(array));
            }
            return lists;
        }
    }

## 第三部分：题解 ##

### 3.1 generate()方法解析 ###

public static List<List<Integer>> generate(int numRows) {
        
        List<List<Integer>> lists = new ArrayList<>();//设置List<Integer>类型的List接口子类对象存储杨辉三角
        for (int i =0;i<numRows;i++){
        //对杨辉三角的第(i+1)层进行存储
            Integer[] array = new Integer[i + 1];//建立一个length=i+1的数组保存该层杨辉三角值
            array[0]=1;//该层第一个元素值设置为1
            array[i]=1;//该层最后一个元素值设置为1
            for (int j = 1;j<=i/2;j++){
        
                //从第2个元素开始设置索引在[1,i-1]的元素，但由于每一层的对称性，所以只需要遍历一半(i/2)即可
                array[j]=lists.get(i-1).get(j)+lists.get(i-1).get(j-1);//得到上一层的list并取到对应索引赋值
                array[i-j] = array[j];//由对称性进行赋值，对称的两个索引的和为i
            }
            lists.add(Arrays.asList(array));//将该层的元素值由array->list形式存储到lists集合
        }
        return lists;//返回杨辉三角
    }

### 3.2 main方法调用 ###

public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);//创建一个扫描器
        int numRows = scanner.nextInt();//键盘输入得到numRows
        List<List<Integer>> lists = generate(numRows);//得到杨辉三角
        System.out.println(lists);//隐式调用重写的toString方法显示杨辉三角
        scanner.close();//关闭扫描器，释放资源
    }

## 第四部分：思考 ##

Integer[] array = new Integer[i + 1];
    array[0]=1;
    array[i]=1;
    for (int j = 1;j<=i/2;j++){
        
        array[j]=lists.get(i-1).get(j)+lists.get(i-1).get(j-1);
        array[i-j] = array[j];
    }
    lists.add(Arrays.asList(array));

对于generate()方法的这一部分，最初的写法是如下

for (int i =0;i<numRows;i++){
        
        List<Integer> list = new ArrayList<>();
        list.set(0,1);//该处抛出异常
        list.set(i,1);
        for (int j = 1;j<=i/2;j++){
        
            list.set(j,lists.get(i-1).get(j)+lists.get(i-1).get(j-1));
            list.set(i-j,list.get(j));
        }
        lists.add(list);
    }

即是每层直接创建ArrayList对象，将元素值通过**set(Index,Element element)方法设置，但测试发现在刚开始的第三行就抛出了IndexOutOfBoundsException**,于是进行debug发现

![a3227ba2c216644ee13da934b2867194.png][]

![6eb9fd3acd794996b2d1deacb27b30e2.png][]

也就是说，set方法调用的前提条件是该索引位置已经设置过了元素值，否则是无法设置的，会抛出异常

你可能有疑惑为什么不用add方法代替set方法，是因为我用了对称的方法减少遍历次数，如果用add会很麻烦，你可以试试。当然，这种对称的方法效率可能比起全部遍历不会高，因为存在需要将array->list的过程，还是会把该层的全部元素遍历。

[118. _ - _LeetCode]: https://leetcode.cn/problems/pascals-triangle/comments/
[c2f42d28dccfa9fc5c452756bf8f6969.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/64a1b123e71e43deac2267aebae5d3f1.png
[a3227ba2c216644ee13da934b2867194.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/c617c0c6c30a42758f68dea54b02ab95.png
[6eb9fd3acd794996b2d1deacb27b30e2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/149c59766ca14beb992d49b81d98f226.png