【LeetCode】446. 等差数列划分II -- 子序列
题目链接
文章目录
- 1. 思路讲解
- 1.1 dp表的创建
- 1.2 状态转移方程
- 1.3 使用哈希表找到k
- 1.4 初始化
- 1.5 返回值
- 1.6 该题坑爹的一点
- 2. 代码编写
1. 思路讲解
我们要知道以某个位置为结尾的子序列的数量,可以通过它的以上一位置的为结尾的子序列的数量得知,也就是说,这是一个dp问题。
1.1 dp表的创建
dp问题我们需要创建dp表,如果我们单纯使用dp[i]来表示以 i 位置为结尾的子序列的数量是完全不够的。因为我们不知道以 i-1 位置为结尾的等差数列是怎样的,它的公差是几我们是不知道的。也就是说,我们不确定 i 位置的元素是否能跟到以 i - 1 位置为结尾的数列的后面。
但是,如果知道了数列的后两个元素,也就是知道了 i - 1 位置以及数列中上一个位置的元素,就能知道数列的公差了,也就能知道 i 位置的元素是否能跟到后面了,所以我们需要用两个元素来表示每个dp位置。
创建二维dp表,dp[i][j]表示以 i 位置的元素为数列倒数第二个元素,以 j 位置的元素为数列倒数第一个元素,为结尾的数列数量有多少。(我们人为规定i < j)
1.2 状态转移方程
nums[j] - nums[i]可以得到公差,再由 num[i] - 公差 可以得到上一项的值,记为 a,我们需要知道这个 a 值在nums中是否存在且是否在 i 位置的前面,两个条件都满足才符合题意。
记 a 在nums中的下标为k(至于怎么找到这个k下面会说),我们要找到以 i 和 j 位置为结尾的等差数列的个数,其实找到所有 k 和 i 位置元素结尾的等差数列的个数相加即可(a元素在nums中的位置不只一个,那么k可能就不只一个)。并且也需额外加上一个数列,就是 k,i ,j,本身所构成的等差数列。
那么状态转移方程就为:dp[i][j] += dp[k][i] + 1
1.3 使用哈希表找到k
我们写代码的时候,遍历所有 i 和 j 的组合,时间复杂度就已经到达 N^2 了,如果此时再在数组中去寻找 k ,那么时间复杂度就 N^3了,这大概率是会超时的。
我们可以在dp之前,使用哈希表去将<所有元素,数组下标>绑定在一起,放在哈希表中,这样我们得到了 a 之后,就可以使用哈希表很快地查找到 k 了。
1.4 初始化
刚开始,以 i,j 位置为结尾,只有两个元素,不符合题目中的等差数列,可以记为 0 ,所以我们初始化的时候将dp表中所有的值初始化为 0 即可。又因为,vector会默认初始化为0,所以我们不用手动初始化了。
1.5 返回值
我们要求的是所有的等差数列,所以我们要将所有符合题意的dp[i][j]都加起来然后返回。
1.6 该题坑爹的一点
虽然题目已经说了,返回值以及各个元素的值都在int范围内,但是我们求a的时候,a的值可能会超出int的范围从而出错,所以我们将a的类型要设置为long long。然后用a查找k用的是hash,所以hash的第一个类型也要为long long。
2. 代码编写

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();// 创建哈希表,便于很快地找到k// 因为k不只一个,所以用vector来存储unordered_map<long long, vector<int>> hash;for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);// 创建二维dp表,第一维为数列的倒数第二个元素,第二维为数列的倒数第一个元素vector<vector<int>> dp(n, vector<int>(n));int ret = 0; // 所有数组的数量// i为nums第0个位置时,不管j为几,dp[0][j]都为0,因为只有两个元素// 所以从第1个位置开始填表即可,且i一定不为nums最后一个元素for (int i = 1; i < n - 1; ++i){// j从i+1开始,一直到最后一个位置,寻找符合题意的情况for (int j = i + 1; j < n; ++j){long long a = (long long)2*nums[i] - nums[j];if (hash.count(a)) // 看a是否存在于hash中{// 如果存在,遍历a对应的vectorfor (auto k : hash[a]){// k需要小于iif (k < i) dp[i][j] += dp[k][i] + 1;}} ret += dp[i][j];}}return ret;}
};
相关文章:
【LeetCode】446. 等差数列划分II -- 子序列
题目链接 文章目录 1. 思路讲解1.1 dp表的创建1.2 状态转移方程1.3 使用哈希表找到k1.4 初始化1.5 返回值1.6 该题坑爹的一点 2. 代码编写 1. 思路讲解 我们要知道以某个位置为结尾的子序列的数量,可以通过它的以上一位置的为结尾的子序列的数量得知,也…...
几个似非而是的注释问题
C 语言的注释可以出现在 C 语言代码的任何地方。这句话对不对?这是我当学生时我 老师问的一个问题。我当时回答是不对。好,那我们就看看下面的例子: A ), int/*...*/i; B ), char* s"…...
【设计模式|上】创建型模式
every blog every motto: You can do more than you think. https://blog.csdn.net/weixin_39190382?typeblog 0. 前言 设计模式(上): 简单工厂模式工厂模式抽象工厂模式建造者模式单例模式 1. 正文 1.1 创建型(Creational Patterns) …...
【JS】类 class
【JS】类 class 定义类类的方法类继承静态方法 类(class)是用于创建对象的模板。 我们使用 class 关键字来创建一个类,类体在一对大括号 {} 中,我们可以在大括号 {} 中定义类成员的位置,如方法或构造函数。 每个类中…...
Ubuntu安装harbor(http模式)并随便上传一个
Ubuntu安装harbor(http模式) docker和harbor的介绍就免了,都不知道啥东西,还安装搞毛 先安装docker环境 不要问,软件源之类的配置,挨个梭就行 sudo apt update sudo apt install apt-transport-https ca…...
《向量数据库指南》——腾讯云向量数据库Tencent Cloud Vector DB正式上线公测!提供10亿级向量检索能力
8月1日,腾讯云向量数据库(Tencent Cloud Vector DB)已正式上线公测。在腾讯云官网上搜索“向量数据库”,就可以正式体验该产品。 腾讯云向量数据库不仅能为大模型提供外部知识库,提高大模型回答的准确性,还可广泛应用于推荐系统、文本图像检索、自然语言处理等 AI 领域。…...
1分钟解决github push/pull报错443
1.打开https://www.ipaddress.com/ 2.复制如图IP地址 3.文件夹打开C:\Windows\System32\drivers\etc,复制hosts文件,粘贴到桌面 4.在桌面用记事本打开复制过来的hosts 5.在末尾加上一行,IP写刚才复制的 6.复制桌面的hosts,粘贴回C:\Window…...
vue3学习-ref引用
模板引用 使用特殊的 refattribute 允许再特定的Dom或组件被挂在后,获取他的直接引用。 import { ref } form vue const input ref(null) <input ref"input"/>注意:只可以在组件挂载后才能访问模板引用 #如果你需要侦听一个模板引用 r…...
Docker 容器转为镜像
# 容器转成镜像并指定镜像名称与版本号 # commit 时原有容器挂载的目录是不会被写入到新的镜像中去的,数据卷相关的都不会生效 # 但是 root 目录下新建的内容会写入到新的镜像中去 $ docker commit 容器ID 新镜像名称:版本号 $ docker commit -m"描述信息"…...
阿里云服务器免费试用及搭建WordPress网站
文章目录 前言一、免费试用1、选择使用产品2、进行产品配置3、远程连接阿里云服务器①、重置实例密码②、SecureCRT 远程链接③、Workbench 远程链接二、搭建 WordPress 网站1、开放搭建 WordPress 需要的端口2、搭建 LAMP 环境①、Linux 系统升级和更新源②、安装 Apache2③、…...
整流二极管型号汇总,超齐全
整流二极管是什么二极管?查看资料可知,整流二极管是一种将交流电能转变为直流电能的半导体器件,可见整流二极管的作用重在“整流”。整流二极管主要用于各种低频半波整流电路,如需达到全波整流需连成整流桥使用。近日,…...
MongoDB 操作命令
创建database 有就切换没有创建 useMydatabase 显示数据库:show dbs显示该database下的 bson对象 show collections 显示该bson下的具体内容**mydatabase.mycollection.find()**查询该bson对象内容**且查询****mydatabase.mycollection.find({a:,b:})****或查询****…...
markdown高级写作技巧汇总
文章目录 1 代码diff2 待办事项3 图片设置宽高4 折叠5 锚点链接实现方式① Markdown 原始写法 [名称](#id)② HTML 语法 名称 6 目录树7 换行 1 代码diff 如果你做过代码 Code Review,对下面这种效果肯定很熟悉 // 数组去重 const unique (arr)>{ - return A…...
SpringBoot自动配置原理入门级理解
简单理解 spring中,我们配置一个bean有两种方式,一种是xml标签的形式,一种是通过java类的形式。那么自动装配就是通过java类的形式来配置bean。 不同的是,springboot将这些我们需要的bean提前配置好了以java类的形式存放在META-I…...
2023 08.02 小记与展望
碎碎念系列更新 算是坚持的第一个月(每个月更新一次,上次是6.29) 主要对上月工作进行总结,并对后续学习内容进行规划。 一、关于工作 7月工作主要涉及以下方面: 1、公司自研APP维护(主要是接口更新和修改…...
MaxPatrol SIEM 增加了一套检测供应链攻击的专业技术
我们为 MaxPatrol SIEM 信息安全事件监控系统增加了一套新的专业技术。 该产品可帮助企业防范与供应链攻击相关的威胁。 此类攻击正成为攻击者的首要目标:它们以软件开发商和供应商为目标,网络犯罪分子通过他们的产品进入最终目标的基础设施。 因此&a…...
蓝桥杯上岸每日N题 第六期(求阶乘)!!!
蓝桥杯上岸每日N题第六期 ❗️ ❗️ ❗️ 同步收录 👇 蓝桥杯上岸必背!!!(持续更新中~) 大家好 我是寸铁💪 冲刺蓝桥杯省一模板大全来啦 🔥 蓝桥杯4月8号就要开始了 🙏 距离蓝桥杯省赛倒数…...
Codeforces Round 889 (Div. 2)(视频讲解A——D)
文章目录 A Dalton the TeacherB Longest Divisors IntervalC2 Dual (hard Version)D Earn or Unlock Codeforces Round 889 (Div. 2)(视频讲解A——D) A Dalton the Teacher #include<bits/stdc.h> #define endl \n #define INF 0x3f3f3f3f us…...
K8s安全配置:CIS基准与kube-bench工具
01、概述 K8s集群往往会因为配置不当导致存在入侵风险,如K8S组件的未授权访问、容器逃逸和横向攻击等。为了保护K8s集群的安全,我们必须仔细检查安全配置。 CIS Kubernetes基准提供了集群安全配置的最佳实践,主要聚焦在两个方面:主…...
linux安装python和部署Django项目
文章目录 1 python安装2 Django项目部署 1 python安装 官网地址:https://www.python.org/ 本次下载的python安装包地址:https://www.python.org/ftp/python/3.8.16/Python-3.8.16.tgz 解压下载的python压缩包 [rootlocalhost software]# tar -zxvf P…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...
