【leetcode】动态规划
31. 873. 最长的斐波那契子序列的长度
题目:
如果序列
X_1, X_2, ..., X_n满足下列条件,就说它是 斐波那契式 的:
n >= 3- 对于所有
i + 2 <= n,都有X_i + X_{i+1} = X_{i+2}给定一个严格递增的正整数数组形成序列 arr ,找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在,返回 0 。
(回想一下,子序列是从原序列 arr 中派生出来的,它从 arr 中删掉任意数量的元素(也可以不删),而不改变其余元素的顺序。例如,
[3, 5, 8]是[3, 4, 5, 6, 7, 8]的一个子序列)
题目链接
873. 最长的斐波那契子序列的长度 - 力扣(LeetCode)
画图分析
代码
class Solution { public:int lenLongestFibSubseq(vector<int>& arr) {int n = arr.size();vector<vector<int>>dp(n,vector<int>(n,0));map<int,int>hash;hash.insert({arr[0],0});int len = 0;for(int j = 2;j < n;j++){hash.insert({arr[j - 1],j - 1});for(int i = j - 1;i >= 1;i--){int x = arr[j] - arr[i];if(hash.count(x) && hash[x] < i){dp[i][j] = max(dp[i][j],dp[hash[x]][i] + 1);len = max(len,dp[i][j]);}}}if(len == 0){return 0;}return len + 2;} };
32. 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是等差的。
题目链接
1027. 最长等差数列 - 力扣(LeetCode)
文字分析
主要解题思路参考 873.最长的斐波那契子序列的长度
同样的我们可以通过两个元素,反推前面一个数
注意:
1. 这道题目没有规定一个数不能重复出现,所以判断前一个数是否存在,得到的下标有多个,要得到最大的子序列,下标应该最近的那个(实现这一点,hash表可以采取覆盖式的更新下标)
2. 这里的最长长度至少是2,任意两个数也构成定差子序列
代码
class Solution { public:int longestArithSeqLength(vector<int>& nums) {map<int,int> hash;hash[nums[0]] = 0;int n = nums.size();int Max = 2;vector<vector<int>> dp(n,vector<int>(n,2));for(int i = 1;i < n;i++){for(int j = i + 1;j < n;j++){int a = 2 * nums[i] - nums[j];if(hash.count(a)){dp[i][j] = dp[hash[a]][i] + 1;}Max = max(Max,dp[i][j]);}hash[nums[i]] = i; //更新下标}return Max;} };
33. 446. 等差数列划分2 -- 子序列
题目:
给你一个整数数组
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 整数。
题目链接
446. 等差数列划分 II - 子序列 - 力扣(LeetCode)
文字分析
这道题和 1027.最长等差数列 相似,唯一最大的不同是:
由题目的示例2可知,子序列可以重复多算
注意:
这道题算出来的一些数很可能会越界,得用 long long 存储
代码
class Solution { public:int numberOfArithmeticSlices(vector<int>& nums) {unordered_map<long long, vector<int>> hash;int n = nums.size();vector<vector<long long>>dp(n, vector<long long>(n, 0)); //模拟哈希桶int len = 0;hash[nums[0]].push_back(0);for (int j = 2; j < n; j++){for (int i = j - 1; i >= 1; i--){long long x = (long long)2 * nums[i] - nums[j]; //不做强转,数据会溢出if (hash.count(x)){for (int e : hash[x]){if (e < i){dp[i][j] += (dp[e][i] + 1);}}len += dp[i][j];}}hash[nums[j - 1]].push_back(j - 1);}return len; } };

相关文章:
【leetcode】动态规划
31. 873. 最长的斐波那契子序列的长度 题目: 如果序列 X_1, X_2, ..., X_n 满足下列条件,就说它是 斐波那契式 的: n > 3对于所有 i 2 < n,都有 X_i X_{i1} X_{i2} 给定一个严格递增的正整数数组形成序列 arr ࿰…...
介绍一下atoi(arr);(c基础)
hi , I am 36 适合对象c语言初学者 atoi(arr);是返回整数(int型),整数是arr数组中字符中数字 格式 #include<stdio.h> atoi(arr); 返回值arr数组中的数字 未改变arr数组 #include<stdlib.h>//atoi(arr); 返 <stdlib> int main(…...
docker入门学习笔记
docker的定义 docker是一个用于构建、运行、传送 应用程序的平台。 为什么要使用docker ? 在开发测试库环境中测试成功后,打包成集装箱,到生产环境也是能够成功的。而传统的安装方式不仅繁琐,并且在测试环境安装后,到…...
使用Python和Pybind11调用C++程序(CMake编译)
目录 一、前言二、安装 pybind11三、编写C示例代码四、结合Pybind11和CMake编译C工程五、Python调用动态库六、参考 一、前言 跨语言调用能对不同计算机语言进行互补,本博客主要介绍如何实现Python调用C语言编写的函数。 实验环境: Linux gnuPython3.10…...
tableau-制作30个图表
制作条形图 步骤: 1、横轴是数值,对应了某一个度量值,纵轴是一个标签 战区的成交额,条形图横轴是战区,纵轴是成交额 下钻条形图 1、增加业务架构-战区右键点击,分层结构,增加分层结构 调整业务架构,将战区,城市,小组移动到业务架构下方 此时的条形图上方有➕号展开后…...
2024APMCM亚太杯数学建模C题【宠物行业】原创论文分享
大家好呀,从发布赛题一直到现在,总算完成了2024 年APMCM亚太地区大学生数学建模竞赛C题的成品论文。 给大家看一下目录吧: 目录 摘 要: 10 一、问题重述 14 二.问题分析 15 2.1问题一 15 2.2问题二 15 2.3问题三…...
C语言解析命令行参数
原文地址:C语言解析命令行参数 – 无敌牛 欢迎参观我的个人博客:无敌牛 – 技术/著作/典籍/分享等 C语言有一个 getopt 函数,可以对命令行进行解析,下面给出一个示例,用的时候可以直接copy过去修改,很方便…...
推荐一款龙迅HDMI2.0转LVDS芯片 LT6211UX LT6211UXC
龙迅的HDMI2.0转LVDS芯片LT6211UX和LT6211UXC是两款高性能的转换器芯片,它们在功能和应用上有所差异,同时也存在一些共同点。以下是对这两款芯片的详细比较和分析: 一、LT6211UX 主要特性: HDMI2.0至LVDS和MIPI转换器。HDMI2.0输…...
libmodbus 源码学习笔记
1.核心函数_框架_数据结构 整个通信的过程 就是上面这个框架 下面就是具体过程 <1> 主设备 我们首先要初始化 我们要使用的串口 然后 设置我们要访问的哪一个设备 最后打开串口 <2>从机设备 也是我们要初始化我们的串口 然后随后立即设置我们的串口设备地址 最后…...
通用网络安全设备之【防火墙】
概念: 防火墙(Firewall),也称防护墙,它是一种位于内部网络与外部网络之间的网络安全防护系统,是一种隔离技术,允许或是限制传输的数据通过。 基于 TCP/IP 协议,主要分为主机型防火…...
Vue.js基础——贼简单易懂!!(响应式 ref 和 reactive、v-on、v-show 和 v-if、v-for、v-bind)
Vue.js是一个渐进式JavaScript框架,用于构建用户界面。它专门设计用于Web应用程序,并专注于视图层。Vue允许开发人员创建可重用的组件,并轻松管理状态和数据绑定。它还提供了一个虚拟DOM系统,用于高效地渲染和重新渲染组件。Vue以…...
Mybatis 执行存储过程,获取输出参数的值
数据库环境:SQL Server 2008 R2 存储过程 alter procedure proc_generateOuterApplyId acceptType varchar(4),acceptGroupId int,outerApplyId varchar(20) output as begin set nocount onset outerApplyId 24GD6688--select outerApplyId as …...
RAG架构类型
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
Oracle 数据库 IDENTITY 列的性能选项
在上一篇文章Oracle 数据库 IDENTITY 列中,我们介绍了Oracle IDENTITY列的基础知识。本文将介绍IDENTITY列的几个性能选项。由于IDENTITY列内部使用sequence机制,因此也等同于是sequence的性能选项。 由于sequence是递增的,在高并发时&#…...
计算(a+b)/c的值
计算(ab)/c的值 C语言代码C语言代码Java语言代码Python语言代码 💐The Begin💐点点关注,收藏不迷路💐 给定3个整数a、b、c,计算表达式(ab)/c的值,/是整除运算。 输入 输入仅一行&…...
OpenCV从入门到精通实战(八)——基于dlib的人脸关键点定位
本文使用Python库dlib和OpenCV来实现面部特征点的检测和标注。 下面是代码的主要步骤和相关的代码片段: 步骤一:导入必要的库和设置参数 首先,代码导入了必要的Python库,并通过argparse设置了输入图像和面部标记预测器的参数。…...
unity | 动画模块之卡片堆叠切换
一、预览动画 可以放很多图,可以自己往后加,可以调图片x轴和y轴间距,可以调图片飞出方向,可以调堆叠方向。 图1 图片堆叠动画预览 二、纯净代码 有粉丝问我这个效果,最近很忙,没有时间细写,先…...
前端开发工程师需要学什么?
前端开发工程师需要学习的主要内容包括HTML、CSS、JavaScript、前端框架、响应式设计、性能优化、版本控制等。 HTML/CSS/JavaScript HTML:是网页的骨架,负责网页的结构和内容。CSS:用于美化网页,设计样式和布局。…...
网络常见命令
一.添加ip地址 (1)先进入端口号 interface 端口号 (2)添加ip地址 IP address xxx.xxx.x.x 主机位 二、查看路由表(查看192.168.3.1) display ip routing-table 192.168.3.1 三、宣告(宣告完后…...
logminer挖掘日志归档查找问题
--根据发生问题时间点查找归档文件 select first_time,NAME from gv$archived_log where first_time>2016-03-15 17:00:00 and first_time<2016-03-15 21:00:00; 2016-03-15 17:23:55 ARCH/jxdb/archivelog/2016_03_15/thread_1_seq_41588.4060.906577337 2016-03-15 17:…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...




