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

力扣1027. 最长等差数列

动态规划

  • 思路:
    • 可以参考力扣1218. 最长定差子序列
    • 目前不清楚公差,可以将序列最大最小值找到,公差的范围是 [-(max - min), (max - min)],按公差递增迭代遍历求出最长等差数列;
class Solution {
public:int longestArithSeqLength(vector<int>& nums) {auto [minit, maxit] = std::minmax_element(nums.begin(), nums.end());int diff = *maxit - *minit;int ans = 0;for (int d = -diff; d <= diff; ++d) {std::unordered_map<int, int> dp;for (int v : nums) {dp[v] = dp[v - d] + 1;ans = std::max(ans, dp[v]);}}return ans;}
};
  • 时间复杂度比较高,应该是哈希表频繁插入导致,将 dp 数据结构换成数组,数组下标最大值为元素最大值 + 1;
class Solution {
public:int longestArithSeqLength(vector<int>& nums) {auto [minit, maxit] = std::minmax_element(nums.begin(), nums.end());int diff = *maxit - *minit;int ans = 1;for (int d = -diff; d <= diff; ++d) {std::vector<int> dp(*maxit + 1, -1);for (int v : nums) {int prev = v - d;// ensure prev is in nums and has exist(or v is the first item)if (prev >= *minit && prev <= *maxit && dp[prev] != -1) {dp[v] = std::max(dp[v], dp[prev] + 1);ans = std::max(ans, dp[v]);}dp[v] = std::max(dp[v], 1);}}return ans;}
};

——————————————————————————————

相关文章:

力扣1027. 最长等差数列

动态规划 思路&#xff1a; 可以参考力扣1218. 最长定差子序列目前不清楚公差&#xff0c;可以将序列最大最小值找到&#xff0c;公差的范围是 [-(max - min), (max - min)]&#xff0c;按公差递增迭代遍历求出最长等差数列&#xff1b; class Solution { public:int longest…...

GraphicsMagick 的 OpenCL 开发记录(二十三)

文章目录 ImageMagick和GraphicsMagick函数及宏对照表 <2022-04-14 周四> ImageMagick和GraphicsMagick函数及宏对照表 在开发过程中收集了这两个项目中的一些相同或相似功能的函数或者宏定义&#xff0c;希望对大家有所帮助&#xff0c;如下&#xff1a; TypeImageMa…...

通过Android Logcat分析firebase崩溃

参考&#xff1a;UnityIL2CPP包Crash闪退利用Android Logcat还原符号表堆栈日志 - 简书 一、安装Android Logcat插件 1、新建空白unity工程&#xff0c;打开PackageManager窗口&#xff0c;菜单栏Window/PackageManager 2、PackageManager中安装Android Logcat日志工具 3、安…...

【AI大模型】WikiChat超越GPT-4:在模拟对话中事实准确率提升55%终极秘密

WikiChat&#xff0c;这个名字仿佛蕴含了无尽的智慧和奥秘。它不仅是一个基于人工智能和自然语言处理技术的聊天机器人&#xff0c;更是一个能够与用户进行深度交流的智能伙伴。它的五个突出特点&#xff1a;高度准确、减少幻觉、对话性强、适应性强和高效性能&#xff0c;使得…...

【C语言刷题系列】水仙花数的打印及进阶

1.水仙花数问题 水仙花数&#xff08;Narcissistic number&#xff09;也被称为超完全数字不变数&#xff08;pluperfect digital invariant, PPDI&#xff09;、自恋数、自幂数、阿姆斯壮数或阿姆斯特朗数&#xff08;Armstrong number&#xff09; 水仙花数是指一个 3 位数&a…...

ICSpector:一款功能强大的微软开源工业PLC安全取证框架

关于ICSpector ICSpector是一款功能强大的开源工业PLC安全取证框架&#xff0c;该工具由微软的研究人员负责开发和维护&#xff0c;可以帮助广大研究人员轻松分析工业PLC元数据和项目文件。 ICSpector提供了方便的方式来扫描PLC并识别ICS环境中的可疑痕迹&#xff0c;可以用于…...

HCIA——29HTTP、万维网、HTML、PPP、ICMP;万维网的工作过程;HTTP 的特点HTTP 的报文结构的选择、解答

学习目标&#xff1a; 计算机网络 1.掌握计算机网络的基本概念、基本原理和基本方法。 2.掌握计算机网络的体系结构和典型网络协议&#xff0c;了解典型网络设备的组成和特点&#xff0c;理解典型网络设备的工作原理。 3.能够运用计算机网络的基本概念、基本原理和基本方法进行…...

面试经典题---3.无重复字符的最长子串

3.无重复字符的最长子串 我的解法&#xff1a; 滑动窗口&#xff1a; 维护一个[left, right)的滑动窗口&#xff0c;其中[left, right - 1]都是不重复子串&#xff1b;每轮while循环都计算一个滑动窗口的无重复子串长度len&#xff0c;每轮也让right后移一步&#xff1b; 内部…...

使用Robot Framework实现多平台自动化测试

基于Robot Framework、Jenkins、Appium、Selenium、Requests、AutoIt等开源框架和技术&#xff0c;成功打造了通用自动化测试持续集成管理平台&#xff08;以下简称“平台”&#xff09;&#xff0c;显著提高了测试质量和测试用例的执行效率。 01、设计目标 平台通用且支持不…...

Java基础进阶02-xml

目录 一、XML&#xff08;可拓展标记语言&#xff09; 1.学习网站&#xff1a; 2.作用 3.XML标签 4.XML语法 5.解析XML &#xff08;1&#xff09;常见解析思想DOM 6.常见的解析工具 7.DOM4j的使用 8.文档约束 &#xff08;1&#xff09;概述 &#xff08;2&#xf…...

《开始使用PyQT》 第01章 PyQT入门 03 用户界面介绍

03 用户界面介绍 《开始使用PyQT》 第01章 PyQT入门 03 用户界面介绍 The user interface (UI) has become a key part of our everyday lives, becoming the intermediary between us and our ever-growing number of machines. A UI is designed to facilitate in human-co…...

HTML-列表

列表 abbr&#xff1a; li : list item ol : orderd list ul : unordered list dl : definition list dt : definition title dd : definition description 1.有序列表(order list) 概念&#xff1a;有顺序或侧重顺序的列表 <h2>要把大象放冰箱总共分几步</h2> &…...

OceanBase创建租户

租户是集群之上的递进概念&#xff0c;OceanBase 数据库采用了多租户架构。 集群偏部署层面的物理概念&#xff0c;是 Zone 和节点的集合&#xff0c;租户则偏向于资源层面的逻辑概念&#xff0c;是在物理节点上划分的资源单元&#xff0c;可以指定其资源规格&#xff0c;包括…...

Java中Integer(127)==Integer(127)为True,Integer(128)==Integer(128)却为False,这是为什么?

文章目录 1.前言2. 源码解析3.总结 1.前言 相信大家职业生涯中或多或少的碰到过Java比较变态的笔试题&#xff0c;下面这道题目大家应该不陌生&#xff1a; Integer i 127; Integer j 127;Integer m 128; Integer n 128;System.out.println(i j); // 输出为 true System.o…...

【Unity】粒子贴图异常白边问题

从PS制作的黑底&#xff0c;白光的贴图。放入Unity粒子中&#xff0c;拉远看会有很严重的白边&#xff0c;像马赛克一样。 材质使用&#xff1a;Mobile/Particles/Additive 经测试只使用一张黑色的图片&#xff0c;也会有白边。 解决方案&#xff1a; 关闭黑色底&#xf…...

bxCAN接收处理

接收处理 为了接收 CAN 消息&#xff0c;提供了构成 FIFO(First Input First Output) 的三个邮箱。为了节约 CPU 负载&#xff0c;简化软件并保证数据一致性&#xff0c;FIFO 完全由硬件进行管理。应用程序通过 FIFO 输出邮箱访问 FIFO 中所存储的消息。 有效消息 当消息依据…...

前端面试题-(浏览器内核,CSS选择器优先级,盒子模型,CSS硬件加速,CSS扩展)

前端面试题-(浏览器内核&#xff0c;CSS选择器优先级&#xff0c;盒子模型&#xff0c;CSS硬件加速&#xff0c;CSS扩展&#xff09; 常见的浏览器内核CSS选择器优先级盒子模型CSS硬件加速CSS扩展 常见的浏览器内核 内核描述Trident(IE内核)主要用在window系统中的IE浏览器中&…...

WEB前端标签的使用

图片标签 <!DOCTYPE html> <html><head><meta charset"utf-8"><title></title></head><body><!-- img标签就是用来将图片显示在页面上的标签 --><img src"图片路径"><!-- 可用路径&#…...

739. 每日温度

提示给定一个整数数组 temperatures &#xff0c;表示每天的温度&#xff0c;返回一个数组 answer &#xff0c;其中 answer[i] 是指对于第 i 天&#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升高&#xff0c;请在该位置用 0 来代替。 示例 1: 输入: tempe…...

stm32F103C8T6简介及标准库和HAL库的区别

什么是单片机 单片机是一种集成电路芯片&#xff0c;把具有数据处理能力的中央处理器CPU、随机存储器RAM、只读存储器ROM、多种I/O和中断系统、定时器/计数器等功能&#xff08;可能还包括显示驱动电路、脉宽调制电路、模拟多路转换电路、A\D转换器等电路&#xff09;集成到一…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...