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

由题,从数组中找一个最长子序列,不难想到,当这个子序列递增子序列的数越接近时是越容易拉长的。从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 文件,您可以配置应用程序的服务…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...
云原生周刊:k0s 成为 CNCF 沙箱项目
开源项目推荐 HAMi HAMi(原名 k8s‑vGPU‑scheduler)是一款 CNCF Sandbox 级别的开源 K8s 中间件,通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度,为容器提供统一接口,实现细粒度资源配额…...
jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...
