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

力扣 最长递增子序列

news 来源：原创 2025/9/19 1:35:53

动态规划，二分查找。

题目

由题，从数组中找一个最长子序列，不难想到，当这个子序列递增子序列的数越接近时是越容易拉长的。从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数组大的直接追加，以此来更新最长递增子序列。

相关文章：

力扣 最长递增子序列

动态规划&#xff0c;二分查找。 题目 由题&#xff0c;从数组中找一个最长子序列&#xff0c;不难想到&#xff0c;当这个子序列递增子序列的数越接近时是越容易拉长的。从dp上看&#xff0c;当遍历到这个数&#xff0c;会从前面的dp选一个最大的数加上当前数&#xff0c;注意…...

编程日记 2025/9/19 1:35:53

在项目中调用本地Deepseek（接入本地Deepseek）

前言 之前发表的文章已经讲了如何本地部署Deepseek模型&#xff0c;并且如何给Deepseek模型投喂数据、搭建本地知识库&#xff0c;但大部分人不知道怎么应用&#xff0c;让自己的项目接入AI模型。 文末有彩蛋哦&#xff01;&#xff01;&#xff01; 要接入本地部署的deepsee…...

编程日记 2025/9/19 16:55:00

已解决IDEA无法输入中文问题（亲测有效）

前言 在使用IDEA的时候&#xff0c;比如我们想写个注释&#xff0c;可能不经意间&#xff0c;输入法就无法输入中文了&#xff0c;但是在其他地方打字&#xff0c;输入法仍然能够正常工作。这是什么原因呢&#xff0c;这篇文章带你解决这个问题&#xff01; 快捷键 如果你的I…...

编程日记 2025/9/20 0:08:53

Java 语法新特性（Records、Pattern Matching、Sealed Classes）深度解析（11/17/21）✨

一、Records&#xff08;Java 16&#xff09; &#x1f4dd; 核心价值&#xff1a;简化不可变数据载体的定义 // 传统POJO vs Record public record User(String name, int age) {} // 自动生成&#xff1a;构造方法/equals()/hashCode()/toString() User user new User(&qu…...

编程日记 2025/9/19 8:48:48

书评与笔记：《如何有效报告Bug》

文章目录 书评笔记核心原则1. 首要目标&#xff1a;让程序员亲眼看到问题2. 次要目标&#xff1a;详细描述问题3. 保持冷静&#xff0c;避免误操作4. 提供额外信息5. 清晰、准确地表达 实用建议不要自作聪明地诊断问题类比&#xff1a;看医生时的症状描述程序员的心理 总结 原文…...

编程日记 2025/9/20 0:11:05

Node.js 中的 fs 模块详解

fs&#xff08;File System&#xff09;模块是 Node.js 的核心模块之一&#xff0c;用于处理文件系统的操作&#xff0c;包括文件的读取、写入、删除、重命名等。它提供了同步和异步两种操作方式&#xff0c;适用于不同的场景。 1. 前置知识 1.1 文件系统 文件系统是操作系统…...

编程日记 2025/9/17 8:22:37

【深度学习】如何一步步实现SGD随机梯度下降算法

如何一步步实现SGD随机梯度下降算法 文章目录 如何一步步实现SGD随机梯度下降算法SGD随机梯度下降算法的作用MNIST_SAMPLE数据集SGD算法的七大步骤Step1. 初始化模型参数Step2. 计算预测值predictionsStep3. 计算损失lossStep4. 计算梯度gradientsStep5. 更新模型参数Step6. 重…...

编程日记 2025/9/19 0:08:08

Android Hal AIDL 简介 (一)

Android 接口定义语言 (AIDL) 是一款可供用户用来抽象化 IPC 的工具。 以在 .aidl 文件中指定的接口为例，各种构建系统都会使用 aidl 二进制文件构造 C++ 或 Java 绑定，以便跨进程使用该接口（无论其运行时环境或位数如何）。 AIDL 可以在 Android 中的任何进程之间使用：在…...

编程日记 2025/9/17 11:33:27

【数据分析】2.数据分析业务全流程

业务流程方法论&#xff1a;3阶段6步骤 一、课程核心内容结构 1. 方法论概述 目标&#xff1a;系统性地解决商业中的关键问题框架&#xff1a;分为三个阶段&#xff0c;每个阶段包含两个步骤适用场景&#xff1a;适用于数据分析师、业务经理等需要通过数据分析支持决策的从业…...

编程日记 2025/9/18 21:49:17

如何使用Spark SQL进行复杂的数据查询和分析

使用Spark SQL进行复杂的数据查询和分析是一个涉及多个步骤和技术的过程。以下是如何使用Spark SQL进行复杂数据查询和分析的详细指南&#xff1a; 一、准备阶段 环境搭建&#xff1a; 确保已经安装并配置好了Apache Spark环境。准备好数据源&#xff0c;可以是CSV文件、JSON…...

编程日记 2025/9/20 0:11:04

【Spring+MyBatis】_图书管理系统（下篇）

图书管理系统上篇、中篇如下&#xff1a; 【SpringMyBatis】_图书管理系统&#xff08;上篇&#xff09;-CSDN博客 【SpringMyBatis】_图书管理系统&#xff08;中篇&#xff09;-CSDN博客 目录 功能5&#xff1a;删除图书 6.1 约定前后端交互接口 6.2 后端接口 6.3 前端…...

编程日记 2025/9/19 3:17:21

goland无法debug项目

1、其实个原因是因为正在使用的Delve调试器版本太旧&#xff0c;无法兼容当前的Go语言版本1.2。Delve是Go语言的一个调试工具&#xff0c;用于提供源码级别的调试功能。Go语言每隔一段时间会发布新版本&#xff0c;而相应的调试器Delve也可能会更新以提供新的特性或修复已知问题…...

编程日记 2025/9/18 9:04:14

001-监控你的文件-FSWatch-C++开源库108杰

fswatch 原理与应用简介fswatch 安装fswatch 实践应用具体应用场景与细节补充 1. 简介 有些知识&#xff0c;你知道了不算厉害&#xff0c;但你要是不知道&#xff0c;就容易出乱。 很多时候&#xff0c;程序需要及时获取磁盘上某个文件对象&#xff08;文件夹、文件&#xff0…...

编程日记 2025/9/17 13:25:37

leetcode203.移除链表元素

目录 问题描述示例提示 具体思路思路一思路二 代码实现 问题描述 给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所有满足 Node.val val 的节点&#xff0c;并返回 新的头节点 。 题目链接&#xff1a;移除链表元素 示例 提示 列表中的节点数目在范围…...

编程日记 2025/9/19 3:58:45

代码随想录算法训练营第六天| 242.有效的字母异位词 、349. 两个数组的交集、202. 快乐数 、1. 两数之和

242.有效的字母异位词 题目链接&#xff1a;242.有效的字母异位词 文档讲解&#xff1a;代码随想录有效的字母异位词 视频讲解&#xff1a;LeetCode&#xff1a;有效的字母异位词 状态&#xff1a;学会了 思路&#xff1a; 数组其实是简单哈希表。 哈希表用来快速判断元素是否在…...

编程日记 2025/9/19 11:25:57

DL/CV领域常见指标术语(FLOPS/mIoU/混淆矩阵/F1-measure)------一篇入门

1. FLOPS、FLOPs和GFLOPs FLOPS: floating-point operations per second&#xff0c;每秒浮点运算次数&#xff0c;用来衡量硬件性能。 FLOPs&#xff1a;floating point of operations&#xff0c;是浮点运算次数&#xff0c;用来衡量算法、模型的复杂度。 GFLOPS&#xff…...

编程日记 2025/9/19 19:51:04

rknn 板端运行程序Invalid RKNN model version 6， Meet unsupported rknn target type

E RKNN: [09:15:53.053] 6, 1 E RKNN: [09:15:53.053] Invalid RKNN model version 6 E RKNN: [09:15:53.053] rknn_init, load model failed! [NN_ERROR] rknn_init fail! ret-1 或者报错&#xff1a; E RKNN: [08:35:30.804] Meet unsupported target type: 0x46495247 E…...

编程日记 2025/9/19 11:34:49

Linux 内核中的 container_of 宏：以 ipoib_rx_poll_rss 函数为例

在 Linux 内核编程中，container_of 是一个非常实用的宏，主要用于通过结构体的成员指针来获取包含该成员的整个结构体的指针。rx_ring = container_of(napi, struct ipoib_recv_ring, napi); 在代码中就是利用了这个宏，下面我们详细分析它的作用和工作原理。 背景知识 在内…...

编程日记 2025/9/19 19:42:20

【数据结构-红黑树】

文章目录 红黑树红黑树介绍红黑树的五个基本性质红黑树的平衡原理红黑树的操作红黑树的操作 代码实现节点实现插入和查询操作 红黑树 红黑树介绍 红黑树&#xff08;Red-Black Tree&#xff09;是一种自平衡的二叉查找树&#xff08;Binary Search Tree, BST&#xff09;&…...

编程日记 2025/9/18 20:47:22

一个简洁高效的Flask用户管理示例

Flask-Login 是 Flask 的用户管理扩展&#xff0c;提供 用户身份验证、会话管理、权限控制 等功能。 适用于&#xff1a; • 用户登录、登出 • 记住用户&#xff08;“记住我” 功能&#xff09; • 限制未登录用户访问某些页面 • 用户会话管理 1. 安装 Flask-Login pi…...

编程日记 2025/9/19 16:16:31

用Nginx打造防盗链护盾

用Nginx打造防盗链护盾 一、你的网站正在"为他人做嫁衣"&#xff1f; 想象一下这个场景&#xff1a; 你精心拍摄的摄影作品、录制的课程视频、设计的原创素材&#xff0c;被其他网站直接盗用链接。 更气人的是——当用户在他们网站查看这些资源时&#xff0c;消耗的…...

编程日记 2025/9/18 8:25:34

VS Code 如何搭建C/C++开发环境

目录 1.VS Code是什么 2. VS Code的下载和安装 2.1 下载和安装 2.2.1 下载 2.2.2 安装 2.2 环境的介绍 2.3 安装中文插件 3. VS Code配置C/C开发环境 3.1 下载和配置MinGW-w64编译器套件 3.1.1 下载 3.1.2 配置 3.2 安装C/C插件 3.3 重启VSCode 4. 在VSCode上编写…...

编程日记 2025/9/18 15:36:54

DeepSeek、微信、硅基流动、纳米搜索、秘塔搜索……十种不同方法实现DeepSeek使用自由

为了让大家实现 DeepSeek 使用自由&#xff0c;今天分享 10 个畅用 DeepSeek 的平台。 一、官方满血版&#xff1a;DeepSeek官网与APP 首推&#xff0c;肯定是 DeepSeek 的官网和 APP&#xff0c;可以使用满血版 R1 和 V3 模型&#xff0c;以及联网功能。 网址&#xff1a; htt…...

编程日记 2025/9/17 14:51:44

【Java】Enum类的常用方法、实现接口及其实际应用

Enum类的常用方法 package com.star.enum03;/** * author : Starshine */public class TestSeason { //这是一个main方法&#xff0c;是程序的入口&#xff1a; public static void main(String[] args) { //用enum关键字创建的Season枚举类上面的父类是&#xff…...

编程日记 2025/9/17 10:10:24

Linux | 进程控制（进程终止与进程等待）

文章目录 Linux | 进程控制 — 进程终止 & 进程等待1、进程终止进程常见退出方法1.1退出码基本概念获取退出码的方式常见退出码约定使用场景 1.2 strerror函数 & errno宏1.3 _exit函数1.4_exit和exit的区别1.4.1 所属头文件与函数原型1.4.2 执行过程差异**结合现象分析…...

编程日记 2025/9/19 16:04:39

三、tsp学习笔记——屏幕移植

泰山派-6寸猫屏转接板 - 立创开源硬件平台 泰山派樱猫的教程&#xff0c;屏资料链接: https://pan.baidu.com/s/1pNAKH33r7LtZG6EwHJ-HNA?pwdnsde 提取码: nsde &#xff08;不要浪费时间下载&#xff0c;没有用&#xff0c;下载gitee上的&#xff09; leefei/tspi-disp-6…...

编程日记 2025/9/18 22:54:13

python全栈-python进阶

python进阶 文章目录 python进阶异常except自定义异常类 文件操作序列化和反序列化CSV文件os模块os.path模块shutil模块 拷贝压缩 模块--modulefrom 模块 import 成员包package库LibraryPIP库 GUI编程-tkinter版使用类定义的GUI界面设置控件的属性方式Label标签的常用属性Butto…...

编程日记 2025/9/19 4:39:01

SpringBoot如何配置开发环境（JDK、Maven、IDEA等）

目录 1. 安装JDK 一、JDK介绍JRE&#xff08;Java Runtime Envirnment&#xff09;&#xff1a;Java运行环境 二、下载JDK官网地址&#xff1a;Java Downloads | Oracle 三、安装JDK点击下载下来的安装包进行安装 四、配置JDK进入到环境变量中&#xff08;下面介绍两种进入…...

编程日记 2025/9/16 12:09:31

图片粘贴上传实现

图片上传 html demo 直接粘贴本地运行查看效果即可&#xff0c;有看不懂的直接喂给 deepseek 会解释的很清晰 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport" content"…...

编程日记 2025/9/19 9:23:26

C++--STL库-List

目录 1.list 的基本使用 1.1 创建和初始化 1.2. 插入元素 1.3. 删除元素 1.4. 访问元素 1.5 遍历 1.6 总结 list是C标准库&#xff08;STL&#xff09;中的双向链表容器&#xff0c;属于<list>头文件。 它的特点是&#xff1a; 动态大小&#xff1a;可以随时插入…...

编程日记 2025/9/18 18:17:31

kubeadm拉起的k8s集群证书过期的做法集群已奔溃也可以解决

kubeadm拉起的k8s集群证书过期的做法 这个是很久之前遇到的了&#xff0c;今天有空&#xff08;心血来潮&#xff09;就都回忆回忆写在这里为爱发光&#xff0c;部分内容来自arch先生&#xff08;死党&#xff09;的帮助。有时候有很多部门提了建k8s的需求&#xff0c;有些是临…...

编程日记 2025/9/18 20:30:28

idea连接gitee(使用idea远程兼容gitee)

文章目录 先登录你的gitee拿到你的邮箱找到idea的设置选择密码方式登录填写你的邮箱和密码登录成功 先登录你的gitee拿到你的邮箱 具体位置在gitee–>设置–>邮箱管理 找到idea的设置 选择密码方式登录 填写你的邮箱和密码 登录成功...

编程日记 2025/9/16 15:04:53

Kafka 简介

Kafka 简介 Apache Kafka 是一个开源的分布式流处理平台&#xff0c;广泛应用于实时数据流处理、日志管理、消息传递等场景。Kafka 最初由 LinkedIn 开发&#xff0c;并于 2011 年捐献给 Apache 软件基金会。 Kafka 的设计目标是高吞吐量、低延迟和高可用性&#xff0c;它能够…...

编程日记 2025/9/18 13:54:50

Ubuntu22.04 Deepseek-R1本地容器化部署/内网穿透/OPENWEBUI，打造个人AI助手！

1. 前言 本地部署DeepSeek并实现内网穿透&#xff0c;为家庭成员提供强大的AI支持。通过使用Ollama、Docker、OpenWebUI和Nginx&#xff0c;内网穿透&#xff0c;我们可以轻松实现快速响应和实时搜索功能。 2.软硬件环境 系统&#xff1a;ubuntu22.04, cuda12GPU: RTX3080Ti …...

编程日记 2025/9/16 16:48:19

红蓝对抗之常见网络安全事件研判、了解网络安全设备、Webshell入侵检测

文章目录 ​​研判&#xff08;入侵检测&#xff09;​​ ​​设备​​ ​​经典网络​​​​云网络​​ ​​异常HTTP请求​​​​Webshell分析​​ ​​Webshell 的分类​​​​Webshell 的检测​​ ​​主机层面​​​​流量层面​​ ​​附录​​ ​​常见端口漏洞…...

编程日记 2025/9/19 1:55:21

Linux部署DeepSeek r1 模型训练

之前写过一篇windows下部署deepseekR1的文章&#xff0c;有小伙伴反馈提供一篇linux下部署DeepSeek r1 模型训练教程&#xff0c;在 Linux 环境下&#xff0c;我找了足够的相关资料&#xff0c;花费了一些时间&#xff0c;我成功部署了 DeepSeek R1 模型训练任务&#xff0c;结…...

编程日记 2025/9/19 7:57:30

【大模型】DeepSeek：AI浪潮中的破局者

【大模型】DeepSeek&#xff1a;AI浪潮中的破局者 引言&#xff1a;AI 新时代的弄潮儿DeepSeek&#xff1a;横空出世展锋芒&#xff08;一&#xff09;诞生背景与发展历程&#xff08;二&#xff09;全球影响力初显 探秘 DeepSeek 的技术内核&#xff08;一&#xff09;独特的模…...

编程日记 2025/9/18 15:49:35

寒假学习总结

整个寒假都走在数据结构与算法的路上&#xff0c;深入学习了其中多个板块&#xff0c;刷了一些与之对应的题目&#xff0c;下面来一期总结&#xff08;c&#xff09; &#xff08;emmm&#xff0c;主播在寒假试着去学习了几大语言的语法基础&#xff08;丢丢&#xff09; 如Ja…...

编程日记 2025/9/19 22:57:13

自愈网络的定义、其为用户带来的益处、具体的使用案例

在当今高度互联的世界中&#xff0c;网络稳定性和可靠性对于各种应用场景至关重要。无论是企业的日常运营、智能家居的便捷控制&#xff0c;还是工业网络的自动化管理&#xff0c;网络的任何中断都可能带来不可估量的损失和不便。正是基于这种需求&#xff0c;以太联—Intellin…...

编程日记 2025/9/19 2:55:32

NumPy的基本使用

在 Python 的数据科学与数值计算领域&#xff0c;NumPy 无疑是一颗耀眼的明星。作为 Python 中用于科学计算的基础库&#xff0c;NumPy 提供了高效的多维数组对象以及处理这些数组的各种工具。本文将带您深入了解 NumPy 的基本使用&#xff0c;感受它的强大魅力。 一、安装与导…...

编程日记 2025/9/17 22:05:07

HTTP 与 HTTPS：协议详解与对比

文章目录 概要 一. HTTP 协议 1.1 概述 1.2 工作原理 1.3 请求方法 1.4 状态码 二. HTTPS 协议 2.1 概述 2.2 工作原理 2.3 SSL/TLS 协议 2.4 证书 三. HTTP 与 HTTPS 的区别 四. 应用场景 4.1 HTTP 的应用场景 4.2 HTTPS 的应用场景 概要 HTTP&#xff08;Hy…...

编程日记 2025/9/19 22:37:02

从零开始构建一个语言模型中vocab_size（词汇表大小）的设定规则

从零开始构建一个语言模型就要设计一个模型框架，其中要配置很多参数。在自然语言处理任务中，vocab_size（词汇表大小） 的设定是模型设计的关键参数之一，它直接影响模型的输入输出结构、计算效率和内存消耗。 本文是在我前文的基础上讲解的：从零开始构建一个小型字符级语言…...

编程日记 2025/9/17 22:39:30

斐波那契数列模型：在动态规划的丝绸之路上追寻斐波那契的足迹（上）

文章目录 引言递归与动态规划的对比递归解法的初探动态规划的优雅与高效自顶向下的记忆化搜索自底向上的迭代法 性能分析与比较小结 引言 斐波那契数列&#xff0c;这一数列如同一条无形的丝线&#xff0c;穿越千年时光&#xff0c;悄然延续其魅力。其定义简单而优美&#xff…...

编程日记 2025/9/13 8:58:06

RT-Thread+STM32L475VET6——ADC采集电压

文章目录 前言一、板载资源二、具体步骤1.打开CubeMX进行配置1.1 使用外部高速时钟&#xff0c;并修改时钟树1.2 打开ADC1的通道3&#xff0c;并配置为连续采集模式(ADC根据自己需求调整&#xff09;1.3 打开串口1.4 生成工程 2. 配置ADC2.1 打开ADC驱动2.2 声明ADC2.3 剪切stm…...

编程日记 2025/9/15 15:42:32

基于Django快递物流管理可视化分析系统（完整系统源码+数据库+详细开发文档+万字详细论文+答辩PPT+详细部署教程等资料）

文章目录 基于Django快递物流管理可视化分析系统&#xff08;完整系统源码数据库详细开发文档万字详细论文答辩PPT详细部署教程等资料&#xff09;一、项目概述二、项目说明三、研究意义四、系统设计技术架构 五、功能实现六、完整系统源码数据库详细开发文档万字详细论文答辩P…...

编程日记 2025/9/13 8:57:57

【Pandas】pandas Series reindex_like

Pandas2.2 Series Computations descriptive stats 方法描述Series.align(other[, join, axis, level, …])用于将两个 Series 对齐&#xff0c;使其具有相同的索引Series.case_when(caselist)用于根据条件列表对 Series 中的元素进行条件判断并返回相应的值Series.drop([lab…...

编程日记 2025/9/18 13:45:52

Ollama安装和迁移，以及部署DeepSeek模型

什么是 Ollama Ollama 是大语言模型管理工具，它的主要作用是简化大语言模型的本地化部署和运行。如果你想调用本地模型，保护个人隐私，构建个人知识库，那你可以考虑使用 Ollama。 Ollama 的官网是 https://ollama.com/，正如官网所说，“Get up and running with large l…...

编程日记 2025/9/19 8:06:22

【数据挖掘】

数据挖掘 目录&#xff1a;1. 数据转换2. 属性选择3. 独立于方案的选择4. 探索空间5. 具体方案的选择6. 离散化数值属性无监督离散化基于熵的离散化其他离散化方法 k-means算法原理算法步骤优缺点优点缺点 代码示例&#xff08;使用Python和scikit-learn库&#xff09;代码解释…...

编程日记 2025/9/19 18:09:18

芝加哥学派（Chicago School）：金融与经济学的创新力量（中英双语）

芝加哥学派&#xff1a;金融与经济学的创新力量 在经济学和金融学的历史上&#xff0c;有一个学派的影响力不容忽视&#xff0c;那就是芝加哥学派&#xff08;Chicago School&#xff09;。芝加哥学派不仅在学术界广受推崇&#xff0c;也深刻影响了全球的经济政策和金融市场。…...

编程日记 2025/9/19 4:29:07

web入侵实战分析-常见web攻击类应急处置实验1

场景说明&#xff1a; 某天运维人员发现在/opt/tomcat8/webapps/test/目录下&#xff0c;多出了一个index_bak.jsp这个文件&#xff0c; 并告诉你如下信息 操作系统&#xff1a;ubuntu-16.04业务&#xff1a;测试站点中间件&#xff1a;tomcat开放端口&#xff1a;22&#x…...

编程日记 2025/9/19 22:17:20