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(文档…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...
