力扣 最长递增子序列
动态规划,二分查找。
题目

由题,从数组中找一个最长子序列,不难想到,当这个子序列递增子序列的数越接近时是越容易拉长的。从dp上看,当遍历到这个数,会从前面的dp选一个最大的数加上当前数,注意这里的dp是每遍历到一个数都会加进去。而这里的dp数组同样是用来维护到某个数时的ans,nums数组是做了比较的,因此也有可能内循环时数组中的一些数是没有做更新的,因此最后一步肯定是加上当前的数后再进行一次与更新的dp比较进行选最大。
时间复杂度:O(n^2),空间复杂度:O(n)。
class Solution {public int lengthOfLIS(int[] nums) {int n = nums.length, ans = 0;int[] f = new int[n];for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {f[i] = Math.max(f[i], f[j]);}}f[i]++;ans = Math.max(ans, f[i]);}return ans;}
}
接着是更快的,用二分查找的方法,在用二分时用mid去找目标值。而这里每遍历到数组的一个数时,同样可以与tails的数去做比较,注意如果遍历到的数与dp的数做比较时mid在大的一边没有移动过,说明这个数就是大的可以追加到原数组的尾巴,即有位置可以插入。
时间复杂度:O(nlogn),空间复杂度:O(n)。
class Solution {public int lengthOfLIS(int[] nums) {int[] tails = new int[nums.length];int res = 0;for(int num : nums) {int i = 0, j = res-1;//标准二分,当左右指针重叠时再进行一次比较while(i <= j) {int m = (i + j) / 2;if(tails[m] < num) i = m + 1;else j = m - 1;}//这里的i就是目标值tails[i] = num;//更新这个位置的值if(res == i) res++;//说明可以进行扩充//注意每次找到时res肯定会比i多一,因为res从一开始的}return res;}
}
很典型的一道例题,可以用dp的状态维护,找到前面的状态,不过每到一个数都要dp两次。而二分查找目标值的方法,刚好让比目标值小的存到tails数组,比tails数组大的直接追加,以此来更新最长递增子序列。
相关文章:
力扣 最长递增子序列
动态规划,二分查找。 题目 由题,从数组中找一个最长子序列,不难想到,当这个子序列递增子序列的数越接近时是越容易拉长的。从dp上看,当遍历到这个数,会从前面的dp选一个最大的数加上当前数,注意…...
【linux】在 Linux 服务器上部署 DeepSeek-r1:70b 并通过 Windows 远程可视化使用
【linux】在 Linux 服务器上部署 DeepSeek-r1:70b 并通过 Windows 远程可视化使用 【承接商业广告,如需商业合作请+v17740568442】 文章目录 【linux】在 Linux 服务器上部署 DeepSeek-r1:70b 并通过 Windows 远程可视化使用个人配置详情一、安装ollama二、下载deepseek版本…...
visutal studio 2022使用qcustomplot基础教程
编译 下载,2.1.1版支持到Qt6.4 。 拷贝qcustomplot.h和qcustomplot.cpp到项目源目录(Qt project)。 在msvc中将它俩加入项目中。 使用Qt6.8,需要修改两处代码: L6779 # if QT_VERSION > QT_VERSION_CHECK(5, 2, …...
Linux:线程概念、理解、控制
目录 一、认识线程 1.认识线程V1 2.认识线程V2 3.认识线程V3 4.认识线程V4 5.认识线程V5 二、线程控制 1.前言 2.创建线程 3.线程等待 4.线程终止 5.线程分离 三、线程理解 一、认识线程 1.认识线程V1 借用大多数计算机教材的话,线程是进程的一个执行…...
Postman如何流畅使用DeepSeek
上次写了一篇文章是用chatBox调用api的方式使用DeepSeek,但是实际只能请求少数几次就不再能给回响应。这回我干脆用最原生的方法Postman调用接口请求好了。 1. 通过下载安装Postman软件 postman下载(https://pan.quark.cn/s/c8d1c7d526f3),包含7.0和10…...
K8S下载离线安装包所需文件
下载相关文件 官网下载地址集合https://kubernetes.io/zh-cn/releases/download/ 下载相关镜像 官网镜像描述 所有 Kubernetes 容器镜像都被部署到 registry.k8s.io 容器镜像仓库。 容器镜像支持架构registry.k8s.io/kube-apiserver:v1.32.0amd64, arm, arm64, ppc64le, …...
探索Hugging Face:开源AI社区的核心工具与应用实践
引言:AI民主化的先锋 在自然语言处理(NLP)领域,Hugging Face已成为开源社区的代名词。这个成立于2016年的平台,通过提供易用的工具和丰富的预训练模型库,彻底改变了开发者使用和部署AI模型的方式。截至202…...
【操作系统】深入理解Linux物理内存
物理内存的组织结构 我们平时所称的内存也叫随机访问存储器也叫 RAM 。RAM 分为两类: 一类是静态 RAM( SRAM ),这类 SRAM 用于 CPU 高速缓存 L1Cache,L2Cache,L3Cache。其特点是访问速度快,访…...
npm 私服使用介绍
一、导读 本文主要介绍 npm 私服的使用,至于 npm 私服搭建的过程,可以看本人之前的文章《Docker 部署 verdaccio 搭建 npm 私服》 二、前置条件 npm私服地址:http://xxx.xxx.xxx.xxx:port/ 三、本地 npm 源切换 使用nrm,可以方…...
安全筑基,智能赋能:BeeWorks IM引领企业协同新纪元
在数字经济高速发展的今天,企业通讯系统已从单纯的信息传递工具演变为支撑业务创新的核心平台。传统通讯工具在安全性、智能化、协同性等方面的不足,严重制约着企业的数字化转型进程。BeeWorks IM系统以其创新的技术架构和智能化功能,正在重新…...
水务+AI应用探索(一)| FastGPT+DeepSeek 本地部署
在当下的科技浪潮中,AI 无疑是最炙手可热的焦点之一,其强大的能力催生出了丰富多样的应用场景,广泛渗透到各个行业领域。对于水务行业而言,AI 的潜力同样不可估量。为了深入探究 AI 在水务领域的实际应用成效,切实掌握…...
[JVM篇]垃圾回收器
垃圾回收器 Serial Seral Old PartNew CMS(Concurrent Mark Sweep) Parallel Scavenge Parallel Old G1 ZGC...
SQL Server:查看当前连接数和最大连接数
目录标题 **1. 查看当前连接数****使用系统视图****使用动态管理视图** **2. 查看最大连接数****通过配置选项****通过服务器属性** **3. 查看连接数的实时变化****4. 设置最大连接数****5. 查看连接的详细信息****6. 使用 SQL Server Management Studio (SSMS)****7. 使用 SQL…...
DeepSeek应用——与PyCharm的配套使用
目录 一、配置方法 二、使用方法 三、注意事项 1、插件市场无continue插件 2、无结果返回,且在本地模型报错 记录自己学习应用DeepSeek的过程,使用的是自己电脑本地部署的私有化蒸馏模型...... (举一反三,这个不单单是可以用…...
【第15章:量子深度学习与未来趋势—15.3 量子深度学习在图像处理、自然语言处理等领域的应用潜力分析】
一、开篇:为什么我们需要关注这场"量子+AI"的世纪联姻? 各位技术爱好者们,今天我们要聊的这个话题,可能是未来十年最值得押注的技术革命——量子深度学习。这不是简单的"1+1=2"的物理叠加,而是一场可能彻底改写AI发展轨迹的范式转移。 想象这样一个…...
多模态基础模型训练笔记-第一篇InternVL-g
一、TL;DR 将之前所有训练过的大模型的过程都总结和回忆一下,遇到的坑别忘了 二、问题记录 还是注意镜像的选择,选择社区最火的镜像,然后下载好对应的数据,主要显卡的选择,这个时候4090已经带不动了&…...
MyBatis:动态SQL高级标签使用方法指南
一、引言 目前互联网大厂在搭建后端Java服务时,常使用Springboot搭配Mybatis/Mybatis-plus的框架。Mybatis/Mybatis-plus之所以能成为当前国内主流的持久层框架,与其本身的优点有关:支持定制动态 SQL、存储过程及高级映射,简化数…...
使用grafana v11 建立k线(蜡烛图)仪表板
先看实现的结果 沪铜主力合约 2025-02-12 的1分钟k线图 功能介绍: 左上角支持切换主力合约,日期,实现动态加载数据. 项目背景: 我想通过前端展示期货指定品种某1天的1分钟k线,类似tqsdk 的web_gui 生成图形化界面— TianQin Python SDK 3.7.8 文档 项目架构: 后端: fastap…...
ubuntu 安装 Redis
一、下载 Redis 压缩包,wget http://download.redis.io/releases/redis-5.0.14.tar.gz 也可以去官网下载别的版本 https://redis.io 二、解压文件,tar -zxvf redis-5.0.14.tar.gz 三、编译安装(使用压缩包的方式需要编译安装)&…...
利用docker-compose一键创建并启动所有容器
简介 在开发复杂的分布式应用时,通常需要同时运行多个服务(如数据库、缓存、Web 应用等)。Docker Compose 提供了一种简便的方式来定义和运行多容器 Docker 应用程序。通过一个 docker-compose.yml 文件,您可以配置应用程序的服务…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果,支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
VisualXML全新升级 | 新增数据库编辑功能
VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...
DiscuzX3.5发帖json api
参考文章:PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下,适配我自己的需求 有一个站点存在多个采集站,我想通过主站拿标题,采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...
