当前位置: 首页 > news >正文

Leetcode:118. 杨辉三角——Java数学法求解

题目——Leetcode:118. 杨辉三角

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

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

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

 

题目分析:

把杨辉三角的每一排左对齐,通过观察我们可以发现:

  • 每一排的第一个数和最后一个数都是 1,即 nums[i][0]=nums[i][i]=1。
  • 其余数字,等于左上方的数,加上正上方的数,即 nums[i][j]=nums[i−1][j−1]+nums[i−1][j]。例如 4=1+3, 6=3+3 等。递推式如下:

图解如下:

 

解法:数学法 

new ArrayList<List<Integer>>();:这里是创建一个ArrayList的实例,但有一个重要的点需要注意。ArrayList的构造函数接受一个int类型的参数,这个参数指定了列表的初始容量(initial capacity),而不是列表的大小(size)。

public class Solution {// 方法用于生成杨辉三角public List<List<Integer>> generate(int numRows) {// 创建一个列表来存储杨辉三角的每一行List<List<Integer>> nums = new ArrayList<List<Integer>>();// 遍历每一行for (int i = 0; i < numRows; ++i) {// 为当前行创建一个新的ArrayListList<Integer> row = new ArrayList<Integer>();// 遍历当前行的每一个元素for (int j = 0; j <= i; ++j) {// 如果是当前行的第一个元素或最后一个元素,则值为1if (j == 0 || j == i) {row.add(1);} else {// 否则,值为上一行相邻两个元素之和// nums.get(i - 1) 获取上一行// .get(j - 1) 获取上一行第j-1个元素// .get(j) 获取上一行第j个元素row.add(nums.get(i - 1).get(j - 1) + nums.get(i - 1).get(j));}}// 将当前行添加到nums列表中nums.add(row);}// 返回生成的杨辉三角return nums;}
}

复杂度分析

  • 时间复杂度:O(numRows2)。

  • 空间复杂度:O(1)。不考虑返回值的空间占用。

相关文章:

Leetcode:118. 杨辉三角——Java数学法求解

题目——Leetcode:118. 杨辉三角 给定一个非负整数 numRows&#xff0c;生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中&#xff0c;每个数是它左上方和右上方的数的和。 示例 1: 输入: numRows 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2: 输入: numRow…...

SHELL脚本(Linux)

声明 学习视频来自 B 站UP主泷羽sec&#xff0c;如涉及侵权马上删除文章。 笔记的只是方便各位师傅学习知识&#xff0c;以下网站只涉及学习内容&#xff0c;其他的都与本人无关&#xff0c;切莫逾越法律红线&#xff0c;否则后果自负。 ✍&#x1f3fb;作者简介&#xff1a;致…...

单元测试、集成测试、系统测试、验收测试、压力测试、性能测试、安全性测试、兼容性测试、回归测试(超详细的分类介绍及教学)

目录 1.单元测试 实现单元测试的方法&#xff1a; 注意事项&#xff1a; 2.集成测试 需注意事项&#xff1a; 实现集成测试的方法&#xff1a; 如何实现高效且可靠的集成测试&#xff1a; 3.系统测试 实现系统测试的方法: 须知注意事项&#xff1a; 4.验收测试 实现验…...

低代码集成多方API的简单实现

在现代软件开发中&#xff0c;集成多个API服务提供商已成为常见需求。然而&#xff0c;不同的API认证机制和数据格式使得集成过程变得复杂且耗时。为了应对这些挑战&#xff0c;本文将介绍一种低代码解决方案&#xff0c;通过配置化管理和简化的代码逻辑&#xff0c;帮助开发者…...

【测试框架篇】单元测试框架pytest(1):环境安装和配置

一、pytest简介 Pytest是Python的一种单元测试框架&#xff0c;与Python自带的unittest测试框架类似&#xff0c;但是比 unittest框架使用起来更简洁&#xff0c;效率更高。 二、pytest特点 Pytest是一个非常成熟的Python测试框架,主要特点有以下几点&#xff1a; 非常容易…...

Python数据分析NumPy和pandas(二十九、其他Python可视化工具)

与其他开源工具一样&#xff0c;在 Python 中创建图形有很多选项&#xff08;太多了&#xff0c;无法一一列举&#xff09;。自 2010 年以来&#xff0c;主要开发工作集中在创建用于在 Web 上发布交互式图形上。例如&#xff1a; Altair、Bokeh 和 Plotly 等工具&#xff0c;可…...

Unity中HDRP设置抗锯齿

一、以前抗锯齿的设置方式 【Edit】——>【Project Settings】——>【Quality】——>【Anti-aliasing】 二、HDRP项目中抗锯齿的设置方式 在Hierarchy中——>找到Camera对象——>在Inspector面板上——>【Camera组件】——>【Rendering】——>【Pos…...

Spring Boot实现文件上传与OSS集成:从基础到应用

目录 前言1. 文件上传的基础实现1.1 前端文件上传请求1.2 后端文件接收与保存 2. 集成第三方OSS服务2.1 准备工作2.2 编写OSS集成代码2.3 修改Controller实现文件上传至OSS 3. 文件上传的扩展&#xff1a;多文件上传与权限控制结语 前言 随着互联网应用的快速发展&#xff0c;…...

Python学习26天

集合 # 定义集合 num {1, 2, 3, 4, 5} print(f"num&#xff1a;{num}\nnum数据类型为&#xff1a;{type(num)}") # 求集合中元素个数 print(f"num中元素个数为&#xff1a;{len(num)}") # 增加集合中的元素 num.add(6) print(num) # {1,2,3,4,5,6} # 删除…...

linux startup.sh shutdown.sh (kkFileView)

linux启动脚本和关闭脚本startup.sh shutdown.sh &#xff08;kkFileView&#xff09; startup.sh DIR_HOME("/opt/openoffice.org3" "/opt/libreoffice" "/opt/libreoffice6.1" "/opt/libreoffice7.0" "/opt/libreoffice7.1&q…...

[MySQL]隐式类型转换

安全等号 <> 如果有参数为NULL&#xff0c;则除了相等比较运算符()&#xff0c;比较的结果为null。对于 nullnull&#xff0c;结果为true。 在select语句中&#xff0c;使用 时&#xff0c;结果不会包含值为 null 的记录&#xff0c;但如果使用安全等号 <> 来…...

面经总结1

文章目录 如何保证批量请求失败&#xff0c;只弹出一个toast1使用计数器&#xff1a;2使用标志变量&#xff1a; 如何减少项目里的if-else1使用多态2使用策略模式3使用字典映射4使用状态模式 babel-runtime 作用是啥如何实现 PDF 预览和下载1浏览器内置PDF阅读器2使用PDF.js库3…...

Oracle19C AWR报告分析之Instance Efficiency Percentages (Target 100%)

Oracle19C AWR报告分析之Instance Efficiency Percentages 一、分析数据二、详细分析2.1 Instance Efficiency Percentages (Target 100%)各项指标及其解释2.2 分析和总结 一、分析数据 二、详细分析 在 Oracle AWR (Automatic Workload Repository) 报告中&#xff0c;每个性能…...

数据结构--数组

一.线性和非线性 线性&#xff1a;除首尾外只有一个唯一的前驱和后继。eg&#xff1a;数组&#xff0c;链表等。 非线性&#xff1a;不是线性的就是非线性。 二.数组是什么&#xff1f; 数组是一个固定长度的存储相同数据类型的数据结构&#xff0c;数组中的元素被存储在一…...

nrm的安装及使用

nrm的安装及使用 NRM&#xff08;NPM Registry Manager&#xff09;是一个用于快速切换npm&#xff08;Node Package Manager&#xff09;源的工具。npm是Node.js的包管理工具&#xff0c;用于安装、发布、管理Node.js包。由于网络原因&#xff0c;直接使用npm官方源&#xff…...

【MatLab手记】 --从0到了解超超超详过程!!!

文章目录 MatLab笔记一、命令行窗口二、变量命名规则三、数据类型1. 数字2. 字符与字符串3. 矩阵3.1 矩阵创建3.2 矩阵的修改和删除3.3 矩阵的拼接与重构重排3.4 矩阵的运算方法3.5 矩阵的下标 4. 元胞数组&#xff08;类似数据容器&#xff09;5. 结构体 四、逻辑与流程控制五…...

从零创建vue+elementui+sass+three.js项目

初始化&#xff1a; vue init webpack projectnamecd projectnamenpm install支持sass: npm install sass --save-dev npm install sass-loader7.1.0 --save-dev npm install node-sass4.12.0 --save-devbuild/webpack.base.conf.js添加 rules: [...,{test: /\.scss$/,loade…...

Linux通过使用scp和sftp发送或拉取文件

在通过 telnet 登录到远程服务器之后&#xff0c;你无法直接使用 telnet 发送文件。telnet 是一个纯文本协议&#xff0c;不支持文件传输。要发送文件&#xff0c;你需要使用其他工具&#xff0c;如 scp 或 sftp。以下是使用这两种工具发送文件的方法&#xff1a; 使用 scp 发…...

Jtti:服务器总是自动重启怎么办?

服务器总是自动重启可能是由于多种原因引起的&#xff0c;包括硬件故障、软件问题、配置错误或环境因素。以下是一些常见原因和相应的解决方案&#xff1a; 1. 硬件问题 电源故障&#xff1a;电源供应不稳定或电源模块故障可能导致服务器重启。 解决方案&#xff1a;检查电源供…...

北京大学c++程序设计听课笔记101

基本概念 程序运行期间&#xff0c;每个函数都会占用一段连续的内存空间。而函数名就是该函数所占内存区域的起始地址&#xff08;也称“入口地址”&#xff09;。我们可以将函数的入口地址赋给一个指针变量&#xff0c;使该指针变量指向该函数。然后通过指针变量就可以调用这个…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...