当前位置: 首页 > 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修饰的变量在每次修改时都会强制…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...

TJCTF 2025

还以为是天津的。这个比较容易&#xff0c;虽然绕了点弯&#xff0c;可还是把CP AK了&#xff0c;不过我会的别人也会&#xff0c;还是没啥名次。记录一下吧。 Crypto bacon-bits with open(flag.txt) as f: flag f.read().strip() with open(text.txt) as t: text t.read…...