Java集合类ArrayList应用 | 二维数组的集合类表示与杨辉三角实现

简介: 这是一个关于LeetCode第118题“杨辉三角”的问题解答摘要。题目要求生成一个杨辉三角的前n行,其中每一行都是由前一行的元素按规则生成的。杨辉三角的规律是:每一行的第一个和最后一个数是1,其他数是其上方两数之和。

一、题干

🔗力扣:118. 杨辉三角



二、题解


1. 思路


我们知道杨辉三角的规律是:


  1. 每一行的第一列和它的最后一列上的数均为1.


  1. 除此之外,每个数是它的左上方与右上方的数之和。如果用 i 代表行, j 代表列,则有:

      [ i ][ j ] 等于 [ i-1 ][ j-1 ] + [ i-1 ][ j ]




本题的关键在于对ArrayList集合类的理解。在力扣上,该题的默认代码模板是这样的:


class Solution {
    public List<List<Integer>> generate(int numRows) {
        ...
    }
}


因此,要完成这道题,我们需要先理清该函数的返回值 List<List<Integer>> 代表什么含义。


  • 从外层的List可以看出,有一个List集合类容器,且容器中的每个元素的数据类型仍是List。本文中我们采用ArrayList集合类实现,因此有以下示意图:



  • 而里层List中的元素类型是Integer,则有如下示意图:



由此可以看出,List<List<Integer>> 所代表的正是一个二维数组。用 i 表示横坐标(行),j 表示纵坐标(列),我们可以通过ArrayList中的get()方法获取二维数组 [i][j] 位置处的元素值。我们将步骤分解,得到具体操作如下:


首先,我们需要创建出外层(即上图中左侧)的ArrayList,用ret表示:



List<List<Integer>> ret = new ArrayList<>();


ret中的每一个元素也是ArrayList类型。我们接下来要做的,就是依照规律逐行将杨辉三角中的数值放入“二维数组”中。第一行的1没有前一行或前一列,它是特殊的,需要单独先把1放进去:


1.//创建第一行
List<Integer> firstRow = new ArrayList<>();
//将第一行的元素1放入第一行的第一个
firstRow.add(1);
//将第一行作为ret的首元素加入ret中
ret.add(firstRow);



然后再插入剩下的数值。用for循环控制每行要完成的事,i 代表行数,由于第一行已经提前单独插入过数值,因此 i 从第二行开始,也就是下标为1处开始。


每一行,都创建一个ArrayList顺序表,用curRow表示。每一行的第一个元素和最后一个元素一定是1,直接通过curRow.add(1)插入即可。两个1中间部分的元素通过插入上方元素之和计算。可以新创建一个变量prevRow表示curRow的前一行:



List<Integer> prevRow = ret.get(i-1);
//获取元素并将结果插入curRow
curRow.add(prevRow.get(j-1) + prevRow.get(j));


也可以不用prevRow,直接插入:


curRow.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));


for循环的最后,还需要把当前行插入ret中。

ret.add(curRow);


示意图及合并代码如下:





        for (int i = 1; i < numRows; i++) {
            List<Integer> curRow = new ArrayList<>();
            curRow.add(1);
            for (int j = 1; j < i; j++) {
                curRow.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));
            }
            curRow.add(1);
            ret.add(curRow);
        }

2. 完整代码


class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        
        List<Integer> firstRow = new ArrayList<>();
        firstRow.add(1);
        ret.add(firstRow);
        for (int i = 1; i < numRows; i++) {
            List<Integer> curRow = new ArrayList<>();
            curRow.add(1);
            for (int j = 1; j < i; j++) {
                curRow.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));
            }
            curRow.add(1);
            ret.add(curRow);
        }
        return ret;
    }
}


三、总结


  1. 杨辉三角的数值规律。


  1. Link<Link<Integer>>可以看作是一个二维数组,且该“二维数组”中的每个元素类型是Integer。分解来看即是一个ArrayList中的每个元素类型仍是一个ArrayList,且后者中的元素类型是Integer。




  1.  通过集合类的get方法获取元素。ret.get(i)指获取ret中第i个元素(ret中的元素类型仍是ArrayList,所以也就是获取第i行),ret.get(i).get(j)指获取行中第j个的元素。


  1. 关键的插入方法是,每一行都创建新的ArrayList对象curRow,先add顺序表curRow中的内容,最后再将该行作为ret的一个元素add到顺序表ret中。通过:




curRow.add(...);

ret.add(curRow);

即可搞定向该“二维数组”中插入元素。


相关文章
|
1天前
|
Java
java中如何确保一个集合不能被修改? - 源码解读详细--JavaPub版本
java中如何确保一个集合不能被修改? - 源码解读详细--JavaPub版本
6 2
|
2天前
|
Java
Java动态获取某个接口下所有的实现类对象集合
Java动态获取某个接口下所有的实现类对象集合
8 1
|
2天前
|
存储 安全 算法
Java基础19-一文搞懂Java集合类框架,以及常见面试题(二)
Java基础19-一文搞懂Java集合类框架,以及常见面试题(二)
30 8
|
2天前
|
安全 Java 开发工具
Java基础19-一文搞懂Java集合类框架,以及常见面试题(一)
Java基础19-一文搞懂Java集合类框架,以及常见面试题(一)
24 6
|
2天前
|
Java
Java集合-----HashMap实例
Java集合-----HashMap实例
14 5
|
3天前
|
存储 Java 测试技术
滚雪球学Java(58):玩转Java中的ArrayList:常用操作技巧和方法总结
【6月更文挑战第12天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
4 0
滚雪球学Java(58):玩转Java中的ArrayList:常用操作技巧和方法总结
|
3天前
|
Prometheus 监控 Cloud Native
Java一分钟之-Micrometer:应用指标库
【6月更文挑战第11天】Micrometer是Java应用的度量库,提供统一API与多监控系统集成,如Prometheus、InfluxDB。它有标准化接口、广泛后端支持、自动配置和多种度量类型。常见问题包括度量命名不规范、数据过载和忽略维度。解决办法包括遵循命名规范、选择重要指标和使用标签。了解API、设计度量策略和选好监控系统是关键。通过正确使用Micrometer,可建立高效监控体系,保障应用稳定性和性能。
16 1
|
3天前
|
存储 安全 Java
Java集合详解:Set, Map, Vector, List的对比与联系
Java集合框架核心包括List、Set、Map和Vector。List允许重复元素,如ArrayList(适合读取)和LinkedList(适合插入删除)。Set不允许重复,有HashSet(无序)和TreeSet(排序)。Map存储键值对,HashMap(无序)和TreeMap(排序)。Vector是线程安全的ArrayList替代品,但在多线程环境下使用。选择集合类型应根据应用场景,如有序、无序、键值对需求及线程安全考虑。
|
3天前
|
NoSQL Java Serverless
Serverless 应用引擎产品使用合集之Java如何使用ScheduledExecutorService来实现定时触发
阿里云Serverless 应用引擎(SAE)提供了完整的微服务应用生命周期管理能力,包括应用部署、服务治理、开发运维、资源管理等功能,并通过扩展功能支持多环境管理、API Gateway、事件驱动等高级应用场景,帮助企业快速构建、部署、运维和扩展微服务架构,实现Serverless化的应用部署与运维模式。以下是对SAE产品使用合集的概述,包括应用管理、服务治理、开发运维、资源管理等方面。
|
4天前
|
Java Serverless PyTorch
Serverless 应用引擎产品使用合集之如何将本地的Java项目部署到FC当中
阿里云Serverless 应用引擎(SAE)提供了完整的微服务应用生命周期管理能力,包括应用部署、服务治理、开发运维、资源管理等功能,并通过扩展功能支持多环境管理、API Gateway、事件驱动等高级应用场景,帮助企业快速构建、部署、运维和扩展微服务架构,实现Serverless化的应用部署与运维模式。以下是对SAE产品使用合集的概述,包括应用管理、服务治理、开发运维、资源管理等方面。