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

力扣119杨辉三角 II:代码实现 + 方法总结(数学规律法 记忆法/备忘录)

文章目录

  • 第一部分:题目
  • 第二部分:解法①-数学规律法
    • 2.1 规律分析
    • 2.2 代码实现
    • 2.3 需要思考
  • 第三部分:解法②-记忆法(备忘录)
  • 第四部分:对比总结

第一部分:题目

🏠 链接:119. 杨辉三角 II - 力扣(LeetCode)

⭐ 难度:简单

image-20230414144132090

第二部分:解法①-数学规律法

2.1 规律分析

2.2 代码实现

public static List<Integer> getRow(int rowIndex) {// 建立一个capacity=rowIndex+1的集合ArrayList<Integer> arrayList = new ArrayList<>(rowIndex + 1);// 设置第rowIndex行首位置的值long indexValue = 1;// 遍历第rowIndex行所有位置for (int i = 0;i <= rowIndex;i++){// long强转为int,将indexValue加入集合,发生了自动装包int->IntegerarrayList.add((int)indexValue);// 根据规律设置下一个好下一个位置的值indexValue = indexValue*(rowIndex-i)/(i+1);}return arrayList;
}
/*
这里有个细节:我们定义indexValue时类型为long,为什么不设置为int类型,这样便可以舍去加入集合时的强转过程这是因为如果将indexValue定义为int类型,那么在代码第六行计算indexValue*(rowIndex-i)时由于indexValue,rowIndex和i都为int,那么indexValue*(rowIndex-i)的结果也为int但是当rowIndex过大时,计算该行某些位置时indexValue*(rowIndex-i)的值会超过int的范围导致这个值为负数。因此,我们定义类型为long的话,由于long的精度比int高,而indexValue*(rowIndex-i)的结果自然为long类型,且没有超过long的取值范围,所以indexValue*(rowIndex-i)得到的便会是正常结果,而非因为数据溢出结果变为负数
*/

2.3 需要思考

我们定义indexValue时类型为long,为什么不设置为int类型,这样便可以舍去加入集合时的强转过程。

这是因为如果将indexValue定义为int类型,那么在代码第六行计算 indexValue * ( rowIndex - i ) 时由于 indexValue , rowIndex 和 i 都为int,那么 indexValue * ( rowIndex - i ) 的结果也为int。但是当rowIndex过大时,计算该行某些位置时indexValue*(rowIndex-i)的值会超过int的范围导致这个值为负数

因此,我们定义类型为long的话,由于long的精度比int高,而indexValue*(rowIndex-i)的结果自然为long类型,且没有超过long的取值范围,所以indexValue * ( rowIndex - i ) 得到的便会是正常结果,而非因为数据溢出结果变为负数。

第三部分:解法②-记忆法(备忘录)

Memoization 记忆法(也称备忘录)是一种优化技术,通过存储函数调用结果(通常比较昂贵),当再次出现相同的输入(子问题)时,就能实现加速效果

    public List<Integer> getRow(int rowIndex) {ArrayList<Integer> list = new ArrayList<>(rowIndex + 1);// 设置首元素的值为1list.add(1);// 从第二行(行索引为1)开始遍历for (int i = 1; i <= rowIndex; i++) {for (int j = i - 1; j > 0; j--) {// 规律: [i][j] 的取值应为 [i-1][j-1] + [i-1][j]list.set(j, list.get(j - 1) + list.get(j));}// 末尾元素的值为1list.add(1);}return list;}

第四部分:对比总结

我们来看下两种方法的执行效率:

1️⃣ 数学规律法

image-20230414150218699

2️⃣ 记忆法

image-20230414150144355

很明显,数学规律法花费的时间更少,这是因为 数学规律法 只需要我们逐一计算第 rowIndex 行每个元素的值即可,而 记忆法 需要我们从第0行开始,计算每一行每一个元素的值。

相关文章:

力扣119杨辉三角 II:代码实现 + 方法总结(数学规律法 记忆法/备忘录)

文章目录第一部分&#xff1a;题目第二部分&#xff1a;解法①-数学规律法2.1 规律分析2.2 代码实现2.3 需要思考第三部分&#xff1a;解法②-记忆法&#xff08;备忘录&#xff09;第四部分&#xff1a;对比总结第一部分&#xff1a;题目 &#x1f3e0; 链接&#xff1a;119.…...

安装pandas遇到No module named ‘_bz2’ 的解决方案

出现这个问题我们可以按照这篇博客去解决&#xff1a; https://blog.csdn.net/bf96163/article/details/128654915 如果解决不了&#xff0c;可以这样去做&#xff1a; 1.确保安装了 对应的库 // ubuntu安装命令 sudo apt-get install bzip2-devel // centos安装命令 sudo y…...

【数据治理-05】什么数据才是货真价实的数据资产,一起聊聊数据资产

在国家层面一些列文件、纲要、政策、办法等政府力量的推动下&#xff0c;数据资产这个词越来越频繁的出现在我们寻常工作当中&#xff0c;现在越来越觉得这个词被滥用&#xff0c;大有“一切数据皆是资产”的感觉&#xff0c;业务数据是资产、技术数据是资产&#xff0c;不能共…...

第三章 ARM处理器体系结构【嵌入式系统】

第三章 ARM处理器体系结构【嵌入式系统】前言推荐第三章 ARM处理器体系结构3.1 概述3.2 ARM处理器的结构3.7 ARM的异常中断处理最后前言 以下内容源自《【嵌入式系统】》 仅供学习交流使用 推荐 无 第三章 ARM处理器体系结构 留着占位 敬请期待 3.1 概述 3.2 ARM处理器的…...

最速下降法

首先&#xff0c;计算函数f的梯度向量&#xff1a;∇f(x1,x2)[2x150x2]\nabla f(x_1,x_2) \begin{bmatrix}2x_1\\50x_2\end{bmatrix}∇f(x1​,x2​)[2x1​50x2​​] 然后&#xff0c;选择一个初始点(x10,x20)(x_1^0,x_2^0)(x10​,x20​)&#xff0c;比如(0,0)(0,0)(0,0)。 接…...

R语言实践——ggplot2+ggrepel绘制散点+优化注释文本位置

简介 书接adjustText实践——调整matplotlib散点图标签&#xff0c;避免重复 上文中&#xff0c;matplotlibadjustText对于我的实例来说并没有起到很好的效果。所以&#xff0c;博主决定在R中利用gglot2ggrepel绘制&#xff0c;期待效果。 操作过程 博主不常使用R&#xff…...

[TIFS 2022] FLCert:可证明安全的联邦学习免受中毒攻击

FLCert: Provably Secure Federated Learning Against Poisoning Attacks | IEEE Journals & Magazine | IEEE Xplore 摘要 由于其分布式性质&#xff0c;联邦学习容易受到中毒攻击&#xff0c;其中恶意客户端通过操纵其本地训练数据和/或发送到云服务器的本地模型更新来毒…...

css3关键帧动画

CSS3关键帧动画是一种在网页设计中常用的技术&#xff0c;通过使用CSS3的关键帧动画功能&#xff0c;可以实现网页上各种形式的动画效果&#xff0c;例如淡入淡出、滑动、旋转、缩放等&#xff0c;这些动画效果可以让网页更加生动有趣&#xff0c;吸引用户的注意力&#xff0c;…...

在 macOS Mojave 之后的每一个版本中都隐藏着比特币白皮书(Bitcoin Whitepaper)

今天我在尝试解决打印机故障问题时&#xff0c;发现了自2018年Mojave版本以来&#xff0c;macOS都附带了一份Satoshi Nakamoto&#xff08;即中本聪&#xff09;的比特币白皮书PDF副本[1]。 我已经询问了十几位使用Mac的朋友&#xff0c;他们都确认macOS里面有这个文件。这个文…...

一文看懂SpringBoot操纵数据库

1.前言 很多同学进入公司就开始参与项目开发&#xff0c;大多数情况是对某个项目进行维护或者需求迭代&#xff0c;能够从0到1参与到项目中的机会很少&#xff0c;因此并没有多少机会了解某些技术的运行机制。换句话说&#xff0c;有的面试官在面试的时候就会探讨深层的技术问题…...

科普:java与C++的区别

Java与C是两种广泛使用的编程语言&#xff0c;它们在某些方面存在不同之处。本文将详细介绍Java与C的区别。 一、C与Java的历史 C语言是由Bjarne Stroustrup在20世纪80年代初期开发的一种面向对象编程语言&#xff0c;它是C语言的扩展。Java语言是由Sun Microsystems公司于20…...

突发!ChatGPT疯了!

‍数据智能产业创新服务媒体——聚焦数智 改变商业今天&#xff0c;笔者正常登录ChatGPT&#xff0c;试图调戏一下他。但是&#xff0c;突然震惊的发现&#xff0c;ChatGPT居然疯了。之所以说他是疯了&#xff0c;而不是崩溃了&#xff0c;是因为他还能回复我&#xff0c;但回…...

docker-compose容器编排使用详解+示例

文章目录一、docker-compose概述1、产生的背景2、核心概念3、使用的三个步骤4、常用命令二、下载安装1、官方文档2、下载3、卸载三、使用compose1、前置知识&#xff0c;将一个springboot项目打包为镜像2、编写docker-compose.yml文件3、启动docker-compose4、停止一、docker-c…...

可用的rtsp ,rtmp地址以及使用VLC和ffmpeg 播放视频流

可用的 rtmp地址: rtmp://ns8.indexforce.com/home/mystream 可用的 rtsp地址: rtsp://wowzaec2demo.streamlock.net/vod/mp4:BigBuckBunny_115k.mp4 可搭配VLC播放器使用&#xff0c;以及虚幻4 流媒体使用&#xff0c;实现直播效果 1.使用VLC 播放&#xff1a;https://www.vi…...

Python机器学习:朴素贝叶斯

前两天不知道把书放哪去了&#xff0c;就停更了一下&#xff0c;昨天晚上发现被我放在书包夹层里面了&#xff0c;所以今天继续开始学习。 首先明确一下啊&#xff0c;朴素贝叶斯是什么&#xff1a;朴素贝叶斯分类器是一种有监督的统计学过滤器&#xff0c;在垃圾邮件过滤、信…...

几个最基本软件的环境变量配置

在Windows中配置环境变量位置&#xff1a; 控制面板->系统和安全->系统。可以点击&#xff1a;“此电脑”->“属性”直接进入。 点击“高级系统设置”->【环境变量】。在这里可以看见用户变量和系统变量&#xff0c;如果你这台机器不是你一个人使用设置为用户变量…...

物业企业如何加快向现代服务业转型

近年来&#xff0c;随着人民生活水平的提高&#xff0c;人们对住宅质量提出更高的要求&#xff0c;在此前提下&#xff0c;全国各地涌现出了一些运用现代的计算机、控制与通信技术建设的智能化住宅小区。但是许多智能化住宅小区都存在建好了智能硬件环境却没有智能化的软件在上…...

java ssm人力资源系统Y3程序

1&#xff0e;系统登录&#xff1a;系统登录是员工访问系统的路口&#xff0c;设计了系统登录界面&#xff0c;包括员工名、密码和验证码&#xff0c;然后对登录进来的员工判断身份信息&#xff0c;判断是管理员还是普通员工。 2&#xff0e;系统员工管理&#xff1a;不管是超级…...

leetcode重点题目分类别记录(三)动态规划深入与素数理论

文章目录动态规划背包问题01背包抽象出求解目标尝试进程子问题拆分基本情况根据拆分过程定义dp数组与转移方程遍历顺序与状态压缩模板归纳题目应用变种提升组合问题多维01背包有特殊限制的01背包完全背包打家劫舍股票系列子序列类数位dp动态规划 背包问题 01背包 有C0-Cx件物…...

面试篇-学习Java多线程编程必备:深入理解volatile与synchronized

1. 概述 1.1 Volatile概述 Volatile是Java中的一种轻量级同步机制&#xff0c;用于保证变量的可见性和禁止指令重排。当一个变量被声明为Volatile类型时&#xff0c;任何修改该变量的操作都会立即被所有线程看到。也就是说&#xff0c;Volatile修饰的变量在每次修改时都会强制…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...