673. 最长递增子序列的个数
673. 最长递增子序列的个数
- 原题链接:
- 完成情况:
- 解题思路:
- 方法一:动态规划
- 方法二:贪心 + 前缀和 + 二分查找
- 参考代码:
- __673最长递增子序列的个数__动态规划
- __673最长递增子序列的个数__贪心_前缀和_二分查找
原题链接:
673. 最长递增子序列的个数
https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/
完成情况:

解题思路:
方法一:动态规划

方法二:贪心 + 前缀和 + 二分查找

参考代码:
__673最长递增子序列的个数__动态规划
package 西湖算法题解___中等题;public class __673最长递增子序列的个数__动态规划 {public int findNumberOfLIS(int[] nums) {//给定一个未排序的整数数组 nums , 返回最长递增子序列的个数 。//注意: 这个数列必须是 严格 递增的。严格大于。//注意是返回最长递增子序列的个数/**每一个最长递增,都与之前的长度有关*/int numsLength = nums.length,maxLen = 0,res = 0;int dp_findNumberOfLIS [] = new int[numsLength];int count [] = new int[numsLength];for (int i = 0;i<numsLength;i++){dp_findNumberOfLIS[i] = 1;count[i] = 1;for (int j=0;j<i;j++){if (nums[i] > nums[j]){if (dp_findNumberOfLIS[j] + 1 > dp_findNumberOfLIS[i]){dp_findNumberOfLIS[i] = dp_findNumberOfLIS[j] + 1;count[i] = count[j]; //重置计数} else if (dp_findNumberOfLIS[j]+1 == dp_findNumberOfLIS[i]) {count[i]+=count[j];}}}if (dp_findNumberOfLIS[i] > maxLen){maxLen = dp_findNumberOfLIS[i];res = count[i]; //重制计数} else if (dp_findNumberOfLIS[i] == maxLen) {res += count[i];}}return res;}
}
__673最长递增子序列的个数__贪心_前缀和_二分查找
package 西湖算法题解___中等题;import java.util.ArrayList;
import java.util.List;public class __673最长递增子序列的个数__贪心_前缀和_二分查找 {public int findNumberOfLIS(int[] nums){List<List<Integer>> d = new ArrayList<List<Integer>>();List<List<Integer>> cnt = new ArrayList<List<Integer>>();for (int v : nums){int i = myBinarySearch1(d.size(),d,v);int c = 1;if (i > 0){int k = myBinarySearch2(d.get(i-1).size(),d.get(i-1),v);c = cnt.get(i-1).get(cnt.get(i-1).size()-1) - cnt.get(i-1).get(k);}if (i == d.size()){List<Integer> dList = new ArrayList<Integer>();dList.add(v);d.add(dList);List<Integer> cntList = new ArrayList<Integer>();cntList.add(0);cntList.add(c);cnt.add(cntList);}else {d.get(i).add(v);int cntSize = cnt.get(i).size();cnt.get(i).add(cnt.get(i).get(cntSize-1)+c);}}int size1 = cnt.size(),size2 = cnt.get(size1-1).size();return cnt.get(size1 - 1).get(size2-1);}/**** @param n* @param list* @param target* @return*/private int myBinarySearch2(int n, List<Integer> list, int target) {int left = 0,right = n;while (left < right){int mid = (left + right) /2;if (list.get(mid) < target){right = mid;}else {left = mid + 1;}}return left;}/*** * @param n* @param d* @param target* @return*/private int myBinarySearch1(int n, List<List<Integer>> d, int target) {int left = 0,right = n;while (left < right){int mid = (left + right) /2;List<Integer> list = d.get(mid);if (list.get(list.size() - 1) >= target){right = mid;}else {left = mid + 1;}}return left;}
}相关文章:
673. 最长递增子序列的个数
673. 最长递增子序列的个数 原题链接:完成情况:解题思路:方法一:动态规划方法二:贪心 前缀和 二分查找 参考代码:__673最长递增子序列的个数__动态规划__673最长递增子序列的个数__贪心_前缀和_二分查找…...
Android12之ABuffer数据处理(三十四)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只有行动才是治疗恐惧和懒惰的唯一良药. 更多原创,欢迎关注:Android…...
whisper 语音识别项目部署
1.安装anaconda软件 在如下网盘免费获取软件: 链接:https://pan.baidu.com/s/1zOZCQOeiDhx6ebHh5zNasA 提取码:hfnd 2.使用conda命令创建python3.8环境 conda create -n whisper python3.83.进入whisper虚拟环境 conda activate whisper4.…...
实例044 在关闭窗口前加入确认对话框
实例说明 用户对程序进行操作时,难免会有错误操作的情况,例如不小心关闭程序,如果尚有许多资料没有保存,那么损失将非常严重,所以最好使程序具有灵活的交互性。人机交互过程一般都是通过对话框来实现的,对话…...
子查询和事务隔离以及用户管理
一、子查询 子查询是另一个语句中的select语句嵌套在另一个select中。注意子查询语法上必须使用()包起来。 嵌套的那个语句返回的结果有可能是: 一个字段,一行记录,一个列或一个表。嵌套的位置 where / having语句里面作为条件使用在from语…...
uniapp 滚动到指定元素的位置(锚点)
需求:在页面中,不管位于何处,点击按钮页面滚动到对应的标题位置。 最简单有效的方式(直接复制改数据就行) 使用 scroll-view 标签的属性:scroll-top(距离值 num) 或 scroll-into-view(子元素的id,不能以…...
Spring AOP 的 afterReturing 返回值是否能修改问题
文章目录 结论举例子原因外传 结论 最近要搞脱敏信息,所以,想了几种方案,最后使用全局的接口拦截,但是,又不能用注解的方式,毕竟是几年的老产品,有很多限制。 中间尝试过使用Spring AOP 的 aft…...
MyBatis分页插件PageHelper的使用及特殊字符的处理
目录 一、PageHelper简介 1.什么是分页 2.PageHelper是什么 3.使用PageHelper的优点 二、PageHelper插件的使用 原生limit查询 1. 导入pom依赖 2. Mybatis.cfg.xml 配置拦截器 3. 使用PageHelper进行分页 三、特殊字符的处理 1.SQL注入: 2.XML转义&#…...
[语音识别] 基于Python构建简易的音频录制与语音识别应用
语音识别技术的快速发展为实现更多智能化应用提供了无限可能。本文旨在介绍一个基于Python实现的简易音频录制与语音识别应用。文章简要介绍相关技术的应用,重点放在音频录制方面,而语音识别则关注于调用相关的语音识别库。本文将首先概述一些音频基础概…...
Matlab彩色图像转索引图像
索引图像 索引图像是一种把像素值直接作为RGB调色板下标的图像。索引图像包括一个数据矩阵X,一个调色板矩阵map,也称为颜色映像矩阵。其中,数据矩阵X可以是8位无符号整型、16位无符号整型或双精度类型。调色板矩阵map是一个m3的数据阵列&…...
测试框架pytest教程(11)-pytestAPI
常量 pytest.__version__ #输出pytest版本 pytest.version_tuple #输出版本的元组形式 功能 pytest.approx pytest.approx 是一个用于进行数值近似比较的 pytest 断言工具。 在测试中,有时候需要对浮点数或其他具有小数部分的数值进行比较。然而,由于…...
Docker自学:利用FastAPI建立一个简单的web app
环境配置:下载Docker Desktop 文件一:main.py from typing import Unionfrom fastapi import FastAPIimport uvicornapp FastAPI()app.get("/") def read_root():return {"Hello": "World"}app.get("/items/{item…...
微调bert做学术论文分类(以科大讯飞学术论文分类挑战赛为例)
代码 12-How to Fine-Tune BERT for Text Classification:链接:https://pan.baidu.com/s/1EKggbyC4ZW-ufnDW45eKzA 提取码:k3b2 baseline 链接:https://pan.baidu.com/s/12hkZNJjQ__FGAHiF3fifvQ 提取码:88tb 数据…...
Springboot中sharding-jdbc的API模式并使用自定义算法
Springboot中sharding-jdbc的API模式并使用自定义算法 可配合AbstractRoutingData使用切换数据源 程序用到了AbstractRoutingData来切换数据源(数据源是自定义的格式编写并没有用springboot的自动装配的格式写),但是又用到sharding-jdbc进行…...
MySQL回表是什么?哪些情况下会回表
🏆作者简介,黑夜开发者,全栈领域新星创作者✌,CSDN博客专家,阿里云社区专家博主,2023年6月CSDN上海赛道top4。 🏆数年电商行业从业经验,历任核心研发工程师,项目技术负责…...
VR、AR、MR 傻傻分不清楚?区别的底层逻辑?
VR是一种能够制作虚拟物体并与人互动的基础技术。它与操作者所处的环境无关。AR可以让在特定位置出现或消失。MR可以让虚拟物体与真实物体进行互动。 AR和MR的大部分应用场景都是随机的,所以硬件基本都采用手机和眼镜。提升了便携性。牺牲了性能。这就导致了AR与MR…...
VScode运行C语言出现的调试问题 lauch:program does not exist 解决方法
"lauch:program does not exist"错误通常表示编译器或调试器无法找到指定的可执行文件。这可能是由于几个原因引起的。首先,确保你的源代码文件夹路径不包含中文字符,因为这可能导致编译器无法识别文件。其次,检查你的launch.json文…...
云原生安全:保护现代化应用的新一代安全策略
随着云计算和容器技术的快速发展,云原生应用已成为现代化软件开发和部署的主流趋势。然而,随之而来的安全挑战也变得更加复杂和严峻。本文将深入探讨云原生安全的概念、原则和最佳实践,帮助您理解如何有效保护云原生应用和敏感数据。 第一部…...
mysql操作
1、字符转Decimal CAST(column AS DECIMAL(9,2)) 2、将计算结果取两位小数: round(column, 2) 3、查询非空 select * from table_XX where id is not null; 4、连表update更新 update a inner join (select yy from b) c on a.id c.id set a.xx c.yy...
前端(十四)——DOM节点操作手册:你需要了解的一切
🙂博主:小猫娃来啦 🙂文章核心:DOM节点操作手册:你需要了解的一切 文章目录 前言DOM基础知识操作现有节点创建新节点遍历节点树修改节点属性和样式事件处理实践应用动态创建表格动态更新列表 前言 DOM(文档…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
