【算法挨揍日记】day33——1027. 最长等差数列、446. 等差数列划分 II - 子序列

1027. 最长等差数列 

1027. 最长等差数列

题目描述:

给你一个整数数组 nums,返回 nums 中最长等差子序列的长度

回想一下,nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ,且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]0 <= i < seq.length - 1) 的值都相同,那么序列 seq 是等差的。

 解题思路:

算法思路:
1. 状态表⽰:
对于线性 dp ,我们可以⽤「经验 + 题⽬要求」来定义状态表⽰:
i. 以某个位置为结尾,巴拉巴拉;
ii. 以某个位置为起点,巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式,以某个位置为结尾,结合题⽬要求,定义⼀个状态表⽰:
dp[i] 表⽰:以 i 位置元素为结尾的「所有⼦序列」中,最⻓的等差序列的⻓度。
但是这⾥有⼀个⾮常致命的问题,那就是我们⽆法确定 i 结尾的等差序列的样⼦。这样就会导致
我们⽆法推导状态转移⽅程,因此我们定义的状态表⽰需要能够确定⼀个等差序列。
根据等差序列的特性,我们仅需知道序列⾥⾯的最后两个元素,就可以确定这个序列的样⼦。因
此,我们修改我们的状态表⽰为:
dp[i][j] 表⽰:以 i 位置以及 j 位置的元素为结尾的所有的⼦序列中,最⻓的等差序列的
⻓度。规定⼀下 i < j
2. 状态转移⽅程:
nums[i] = b, nums[j] = c ,那么这个序列的前⼀个元素就是 a = 2 * b - c 。我们
根据 a 的情况讨论:
a. a 存在,下标为 k ,并且 a < b :此时我们需要以 k 位置以及 i 位置元素为结尾的最
⻓等差序列的⻓度,然后再加上 j 位置的元素即可。于是 dp[i][j] = dp[k][i] +
1 。这⾥因为会有许多个 k ,我们仅需离 i 最近的 k 即可。因此任何最⻓的都可以以 k
为结尾;
b. a 存在,但是 b < a < c :此时只能两个元素⾃⼰玩了, dp[i][j] = 2
c. a 不存在:此时依旧只能两个元素⾃⼰玩了, dp[i][j] = 2
综上,状态转移⽅程分情况讨论即可。
优化点:我们发现,在状态转移⽅程中,我们需要确定 a 元素的下标。因此我们可以将所有的元素 +
下标绑定在⼀起,放到哈希表中,这⾥有两种策略:
a. dp 之前,放⼊哈希表中。这是可以的,但是需要将下标形成⼀个数组放进哈希表中。这样
时间复杂度较⾼,我帮⼤家试过了,超时。
b. ⼀边 dp ,⼀边保存。这种⽅式,我们仅需保存最近的元素的下标,不⽤保存下标数组。但是
⽤这种⽅法的话,我们在遍历顺序那⾥,先固定倒数第⼆个数,再遍历倒数第⼀个数。这样就
可以在 i 使⽤完时候,将 nums[i] 扔到哈希表中。
3. 初始化:
根据实际情况,可以将所有位置初始化为 2
4. 填表顺序:
a. 先固定倒数第⼆个数;
b. 然后枚举倒数第⼀个数。
5. 返回值:
由于不知道最⻓的结尾在哪⾥,因此返回 dp 表中的最⼤值。

解题代码:

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>>dp(n,vector<int>(n,2));
        unordered_map<int,int>hash;
        int ret=2;
        hash[nums[0]]=0;
        for(int i=1;i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                int a=2*nums[i]-nums[j];
                // int k=hash.count(a);
                if(hash.count(a))
                {
                    dp[i][j]=dp[hash[a]][i]+1;
                }
                ret=max(ret,dp[i][j]);
            }
                hash[nums[i]]=i;
        }
        return ret;
    }
};

446. 等差数列划分 II - 子序列

题目描述:

给你一个整数数组 nums ,返回 nums 中所有 等差子序列 的数目。

如果一个序列中 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该序列为等差序列。

  • 例如,[1, 3, 5, 7, 9][7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
  • 再例如,[1, 1, 2, 5, 7] 不是等差序列。

数组中的子序列是从数组中删除一些元素(也可能不删除)得到的一个序列。

  • 例如,[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

题目数据保证答案是一个 32-bit 整数。

解题思路:

算法思路:
1. 状态表⽰:
对于线性 dp ,我们可以⽤「经验 + 题⽬要求」来定义状态表⽰:
i. 以某个位置为结尾,巴拉巴拉;
ii. 以某个位置为起点,巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式,以某个位置为结尾,结合题⽬要求,定义⼀个状态表⽰:
dp[i] 表⽰:以 i 位置元素为结尾的「所有⼦序列」中,等差⼦序列的个数。
但是这⾥有⼀个⾮常致命的问题,那就是我们⽆法确定 i 结尾的等差序列的样⼦。这样就会导致
我们⽆法推导状态转移⽅程,因此我们定义的状态表⽰需要能够确定⼀个等差序列。
根据等差序列的特性,我们仅需知道序列⾥⾯的最后两个元素,就可以确定这个序列的样⼦。因
此,我们修改我们的状态表⽰为:
dp[i][j] 表⽰:以 i 位置以及 j 位置的元素为结尾的所有的⼦序列中,等差⼦序列的个
数。规定⼀下 i < j
2. 状态转移⽅程:
nums[i] = b, nums[j] = c ,那么这个序列的前⼀个元素就是 a = 2 * b - c 。我们
根据 a 的情况讨论:
a. a 存在,下标为 k ,并且 a < b :此时我们知道以 k 元素以及 i 元素结尾的等差序列
的个数 dp[k][i] ,在这些⼦序列的后⾯加上 j 位置的元素依旧是等差序列。但是这⾥会多
出来⼀个以 k, i, j 位置的元素组成的新的等差序列,因此 dp[i][j] = dp[k][i]
+ 1
b. 因为 a 可能有很多个,我们需要全部累加起来。
综上, dp[i][j] += dp[k][i] + 1
优化点:我们发现,在状态转移⽅程中,我们需要确定 a 元素的下标。因此我们可以在 dp 之前,将
所有元素 + 下标数组绑定在⼀起,放到哈希表中。这⾥为何要保存下标数组,是因为我们要统计个
数,所有的下标都需要统计。
3. 初始化:
刚开始是没有等差数列的,因此初始化 dp 表为 0
4. 填表顺序:
a. 先固定倒数第⼀个数;
b. 然后枚举倒数第⼆个数。
5. 返回值:
我们要统计所有的等差⼦序列,因此返回 dp 表中所有元素的和。

 解题代码:

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>>dp(n,vector(n,0));
        unordered_map<long long,vector<int>>hash;
        hash[nums[0]].push_back(0);
        int sum=0;
        for(int i=1;i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                long long a=2*(long long)nums[i]-nums[j];
                if(hash.count(a))
                {
                    int length=hash[a].size();
                    for(int k=0;k<length;k++)
                    {
                        dp[i][j]+=dp[hash[a][k]][i]+1;
                    }
                }
                sum+=dp[i][j];
            }
            hash[nums[i]].push_back(i);
        }
        return sum;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/201601.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Go GORM简介

GORM&#xff08;Go Object-Relational Mapping&#xff09;是一个用于Go语言的ORM库&#xff0c;它提供了一种简单、优雅的方式来操作数据库。GORM支持多种数据库&#xff0c;包括MySQL、PostgreSQL、SQLite和SQL Server。以下是GORM的一些主要特性 全功能ORM&#xff1a;GORM…

MyBatis-plus-Generate 自动生成代码结构实践

一、新建一个springboot项目&#xff0c;并引入依赖 关注mybatis-plus-boot-starter <properties><java.version>1.8</java.version><project.build.sourceEncoding>UTF-8</project.build.sourceEncoding><project.reporting.outputEncoding…

PyQt基础_007_ 按钮类控件QCombox

import sys from PyQt5.QtCore import * from PyQt5.QtGui import * from PyQt5.QtWidgets import *class ComboxDemo(QWidget):def __init__(self, parentNone):super(ComboxDemo, self).__init__(parent)self.setWindowTitle("combox 例子") self.resize(300, 90) …

【测试开发】web自动化测试框架需求设计 !

1、实现目的 基于BS架构&#xff0c;模拟用户&#xff08;鼠标、键盘&#xff09;操作&#xff0c;达到快速、重复执行测试用例&#xff1b; 便于回归测试&#xff0c;快速覆盖主线用例或功能&#xff1b; 线上或线下巡检测试&#xff0c;结合持续集成&#xff0c;及时发现运…

一起学docker系列之十二什么是dockerfile

目录 1 基本概念2 语法规则3 Dockerfile构建步骤4 Dockerfile、Docker镜像和Docker容器的关系5 保留字介绍5.1 FROM5.2 MAINTAINER5.3 RUN5.4 EXPOSE5.5 WORKDIR5.6 USER5.7 ENV5.8 ADD5.9 COPY5.10 VOLUME5.11 CMD5.12 ENTRYPOINT 6 总结7 参考地址 1 基本概念 Dockerfile是一…

【接口技术】实验3:可编程并行接口8255

实验3 可编程并行接口8255实验 一、实验目的 1&#xff1a;了解8255芯片结构及编程方法。 2&#xff1a;了解8255输入/输出实验方法。 3&#xff1a;掌握8255控制键盘及显示电路的基本功能及编程方法。 4&#xff1a;掌握一般键盘和显示电路的工作原理。 二、实验内容 1&…

JAVA - 阻塞队列

一、什么是堵塞队列 堵塞队列&#xff08;Blocking Queue&#xff09;是一种特殊类型的队列&#xff0c;它具有一些特定的行为和限制。在堵塞队列中&#xff0c;当队列为空时&#xff0c;尝试从队列中取出元素的操作将会被阻塞&#xff0c;直到队列中有可用元素&#xff1b;当…

java el表达式解析

使用Java EL表达式解析 在Java开发中&#xff0c;我们经常需要对表达式进行解析和计算。EL&#xff08;Expression Language&#xff09;表达式是一种用于在Java应用程序中计算和输出动态值的简单语言。它可以用于实现动态的条件判断、数学计算、字符串合并等功能。本文将教你…

《第一行代码:Android》第三版-3.4.4体验Activity的生命周期

本文的代码是在主Activity中&#xff0c;重载了几个生命周期函数&#xff0c;在日志中打印出对应的日志信息&#xff0c;有两个按钮&#xff0c;负责启动另外的Activity&#xff0c;并回到主Activity 由此查看日志&#xff0c;来体会生命周期。 MainActivity.kt 文件如下 pac…

SAP_MM_ABAP_物料视图维护监控报表(自定义开发)

SAP ABAP 顾问&#xff08;开发工程师&#xff09;能力模型_Terry谈企业数字化的博客-CSDN博客文章浏览阅读458次。目标&#xff1a;基于对SAP abap 顾问能力模型的梳理&#xff0c;给一年左右经验的abaper 快速成长为三年经验提供超级燃料&#xff01;https://blog.csdn.net/j…

Java零基础——Nginx篇

1.【熟悉】服务器概述 1.1 目前常见的web服务器 1&#xff0c;Apache(http://httpd.apache.org) 它是世界上用的最多的web服务器&#xff0c;市场占有率达60%左右&#xff0c;模块非常丰富&#xff0c;系统非常稳定&#xff0c;可移植性好&#xff0c;但是比较消耗资源 2&…

Javaweb之Vue组件库Element案例的详细解析

4.4 案例 4.4.1 案例需求 参考 资料/页面原型/tlias智能学习辅助系统/首页.html 文件&#xff0c;浏览器打开&#xff0c;点击页面中的左侧栏的员工管理&#xff0c;如下所示&#xff1a; 需求说明&#xff1a; 制作类似格式的页面 即上面是标题&#xff0c;左侧栏是导航&…

E. Kolya and Movie Theatre

https://codeforces.com/contest/1862/problem/E 容易发现就是维护一个长度至多为m的序列和 减去 i*d&#xff08;i为最后选择看电影的是哪一天&#xff09; 一开始没有把第0天的p是0用上&#xff0c;没想出来 维护非负序列和这里可以用一个set&#xff0c;有点类似于滑动窗口&…

示波器高压探头的操作说明及使用注意事项

操作说明&#xff1a; 连接探头衰减端的地线(鳄鱼夹)到好的接地点或可靠的接地测试端。连接BNC头到示波器的BNC输入端口。选择示波器要求的量程范围。 注意&#xff1a;请务必在连接测试前把高压电源关闭。 注意事项&#xff1a; 请勿将测试设备的接地线从地面接线柱上移开。…

人工智能对人脑的探索研究!物理限制推动类脑人工智能的发展

原创 | 文 BFT机器人 在一项开创性的研究中&#xff0c;剑桥科学家采用了一种新颖的人工智能方法&#xff0c;展示了物理约束如何深刻影响了人工智能系统的发展。 这项研究会让人想起人脑的发育和能力限制&#xff0c;为复杂神经系统的进化提供了新的见解。通过整合这些限制&a…

90基于matlab的无迹卡尔曼滤波器参数估计的非线性最小二乘优化

基于matlab的无迹卡尔曼滤波器参数估计的非线性最小二乘优化&#xff0c;数据可更换自己的&#xff0c;程序已调通&#xff0c;可直接运行。 90matlab无迹卡尔曼滤波器参数估计 (xiaohongshu.com)

史上最全接单平台集锦,程序员不容错过!

非典型程序员不是每天都累成狗&#xff0c;天天”996"甚至”007“。可能&#xff0c;面临着上班摸鱼没事干&#xff0c;下班躺尸打游戏的无聊境况。那么&#xff0c;如果你也是这样的程序员&#xff0c;有没有什么安排可以打发时间&#xff1f; 闲着还不如挣钱~心情好的时…

幼教智能时代精英论坛北京举行

中国日报11月29日电 近日&#xff0c;智能时代赢之道—2023幼教智能时代精英论坛在北京泰山饭店成功举办&#xff0c;来自全国各地的近百位幼儿园园长、幼教老师集聚一堂&#xff0c;探索智能时代幼教的智慧化解决方案。 伴随“教育数字化战略行动”的深入开展&#xff0c;智慧…

创建Asp.net MVC项目实现视图页面数据传值显示

MVC中视图传值 ViewData ViewBag TempData 举例创建三中传值方式实现页面数据展示 MVC中视图传值 Asp.net MVC中Controller向View传值有多种方式,这里简单说一下其中3种方式 ViewData、ViewBag和TempData ViewData ViewData存储数据&#xff0c;ViewData的声明和赋值方…

Jenkins+Git+Appium 持续集成策略

持续集成 &#xff08;Continuous integration&#xff0c;简称 CI&#xff09; 持续集成是一种开发实践&#xff0c;它倡导团队成员需要频繁的集成他们的工作&#xff0c;每次集成都通过自动化构建&#xff08;包括编译、构建、自动化测试&#xff09;来验证&#xff0c;从而尽…