71、最长上升子序列II
最长上升子序列II
题目描述
给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数N。
第二行包含N个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1 ≤ N ≤ 100000 , 1≤N≤100000, 1≤N≤100000,
− 1 0 9 ≤ 数列中的数 ≤ 1 0 9 −10^9≤数列中的数≤10^9 −109≤数列中的数≤109
输入样例:7
3 1 2 1 8 5 6输出样例:4
Solution
import java.util.*;class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int N = sc.nextInt();// N 为 100000, n 方的做法会 TLEint[] a = new int[N + 10];// res[i] 数组记录长度为 i 时,所有子序列中结尾最小的元素int[] q = new int[N + 10];// 初始化为 0int len = 0;for(int i = 1; i <= N; i++) {a[i] = sc.nextInt();// 二分查找优化时间复杂度 logn// 查找最后一个小于 a[i] 的值int idx = bsearch(q, len, a[i]);if(idx == len) {len++;q[len] = a[i];}else{if(q[idx + 1] > a[i]) q[idx + 1] = a[i];}}System.out.println(len);}public static int bsearch(int[] q, int n, int x){// 找最后一个小于 x 的位置// 如果都比 x 大的话返回 0// 从 1 到 n 开始二分int low = 1, high = n;while(low <= high){int mid = (low + high) / 2;if(q[mid] < x){if(mid == n || q[mid + 1] >= x) return mid;else low = mid + 1;}else high = mid - 1;}return 0;}
}
相关文章:
71、最长上升子序列II
最长上升子序列II 题目描述 给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。 输入格式 第一行包含整数N。 第二行包含N个整数,表示完整序列。 输出格式 输出一个整数,表示最大长度。 数据范围 1 ≤ N ≤ 100000…...

解决必剪电脑版导出视频缺斤少两的办法
背景 前几天将电脑重置了,今天想要剪辑一下视频,于是下载了必剪,将视频、音频都调整好,导出,结果15分钟的视频只能导出很短的时长,调整参数最多也只能导出10分钟,My God! 解决 首…...
新人学习笔记之(常量)
一、什么是常量 1.常量:在程序的执行过程中,其值不能发生改变的数据 二、常量的分类 常量类型说明举例整型常量整数、负数、0123 456实型常量所有带小数点的数字1.93 18.2字符常量单引号引起来的字母、数字、英文符号S B字符串常量双引号引起来的&…...

Lua解释器裁剪
本文目录 1、引言2、文件功能3、选择需要初始化的库4、结论 文章对应视频教程: 已更新。见下方 点击图片或链接访问我的B站主页~~~ Lua解释器裁剪,很简单~ 1、引言 在嵌入式中使用lua解释器,很多时候会面临资源紧张的情况。 同时,…...
web前端设计nav:深入探索导航栏设计的艺术与技术
web前端设计nav:深入探索导航栏设计的艺术与技术 在web前端设计中,导航栏(nav)扮演着至关重要的角色,它不仅是用户浏览网站的指引,更是网站整体设计的点睛之笔。本文将从四个方面、五个方面、六个方面和七…...
分析解读NCCL_SHM_Disable与NCCL_P2P_Disable
在NVIDIA的NCCL(NVIDIA Collective Communications Library)库中,NCCL_SHM_Disable 和 NCCL_P2P_Disable 是两个重要的环境变量,它们控制着NCCL在多GPU通信中的行为和使用的通信机制。下面是对这两个环境变量的详细解读࿱…...

使用 Python 进行测试(6)Fake it...
总结 如果我有: # my_life_work.py def transform(param):return param * 2def check(param):return "bad" not in paramdef calculate(param):return len(param)def main(param, option):if option:param transform(param)if not check(param):raise ValueError(…...
Flink Watermark详解
Flink Watermark详解 一、概述 Flink Watermark是Apache Flink框架中为了处理乱序和延迟事件时间数据而引入的一种机制。在流处理中,由于数据可能不是按照事件产生的时间顺序到达的,Watermark被用来告知系统在该时间戳之前的数据已经全部到达ÿ…...
LeetCode538.把二叉搜索树转换为累加树
class Solution { public:int sum 0; TreeNode* convertBST(TreeNode* root) { if (root){convertBST(root->right);sum root->val;root->val sum;convertBST(root->left);}return root;}};...
关于编程思想
面向过程思想 面向过程就是分析出解决问题所需要的步骤,然后用函数把这些步骤一步一步实现,使用的时候再一个一个的依次调用就可以了 JS就是典型的面向过程的编程语言 优点: 性能比面向对象编程高,适合跟硬件联系很紧密的东西…...

521. 最长特殊序列 Ⅰ(Rust单百解法-脑筋急转弯)
题目 给你两个字符串 a 和 b,请返回 这两个字符串中 最长的特殊序列 的长度。如果不存在,则返回 -1 。 「最长特殊序列」 定义如下:该序列为 某字符串独有的最长 子序列 (即不能是其他字符串的子序列) 。 字符串 s …...

【YashanDB知识库】PHP使用OCI接口使用数据库绑定参数功能异常
【问题分类】驱动使用 【关键字】OCI、驱动使用、PHP 【问题描述】 PHP使用OCI8连接yashan数据库,使用绑定参数获取数据时,出现报错 如果使用PDO_OCI接口连接数据库,未弹出异常,但是无法正确获取数据 【问题原因分析】 开启O…...

深入分析 Android BroadcastReceiver (三)
文章目录 深入分析 Android BroadcastReceiver (三)1. 广播消息的优缺点及使用场景1.1 优点1.2 缺点 2. 广播的使用场景及代码示例2.1. 系统广播示例:监听网络状态变化 2.2. 自定义广播示例:发送自定义广播 2.3. 有序广播示例:有序广播 2.4. …...
在java中使用Reactor 项目中的一个类Mono,用于表示异步单值操作
Mono 是 Reactor 项目中的一个类,用于表示异步单值操作。Reactor 是一个响应式编程库,广泛应用于 Java 中的异步编程和非阻塞 I/O 操作。Mono 可以类比为一个可能(或将来)包含零个或一个值的异步计算结果。与 Flux(另一…...

LabVIEW故障预测
在LabVIEW故障预测中,振动信号特征提取的关键技术主要包括以下几个方面: 时域特征提取:时域特征是直接从振动信号的时间序列中提取的特征。常见的时域特征包括振动信号的均值、方差、峰值、峰-峰值、均方根、脉冲指数等。这些特征能够反映振动…...
掌握JavaScript中的`async`和`await`:循环中的使用指南
引言 在JavaScript的异步编程中,async和await提供了一种更接近同步代码的写法,使得异步逻辑更加清晰易懂。然而,当它们与循环结合时,一些常见的陷阱和误区可能会出现。本文将通过代码示例,指导你如何在循环中正确使用…...

java第二十三课 —— 继承
面向对象的三大特征 继承 继承可以解决代码复用,让我们的编程更加靠近人类思维,当多个类存在相同的属性(变量)和方法时,可以从这些类中抽象出父类,在父类中定义这些相同的属性和方法,所有的子…...

不可不知的Java SE技巧:如何使用for each循环遍历数组
哈喽,各位小伙伴们,你们好呀,我是喵手。运营社区:C站/掘金/腾讯云;欢迎大家常来逛逛 今天我要给大家分享一些自己日常学习到的一些知识点,并以文字的形式跟大家一起交流,互相学习,一…...

机器人建模、运动学与动力学仿真分析(importrobot,loadrobot,smimport)
机器人建模、运动学与动力学仿真分析是机器人设计和开发过程中的关键步骤。 一、机器人建模 机器人建模是描述机器人物理结构和运动特性的过程。其中,URDF(Unified Robot Description Format)是一种常用的机器人模型描述方法。通过URDF&…...

02-QWebEngineView的使用
Qt WebEngine_hitzsf的博客-CSDN博客 一、QWebEngineView QWebEngineView 类是一个实现Web浏览器的便捷类,提供了back() 、forward()、reload()、stop() 等方法,可轻松实现页面的前进、后退、重载等导航功能,要实现一个简单的只有网页加载网…...

【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...

Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...