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

每日一道算法题

题目:最长递增子序列的个数

给定一个未排序的整数数组,找到最长递增子序列的个数。

示例 1

  • 输入nums = [1,3,5,4,7]
  • 输出2
  • 解释:有两个最长递增子序列,分别是 [1,3,4,7] 和 [1,3,5,7] 。

示例 2

  • 输入nums = [2,2,2,2,2]
  • 输出5
  • 解释:最长递增子序列的长度是 1,并且存在 5 个长度为 1 的递增子序列,因此输出 5。

提示

  • 1 <= nums.length <= 2000
  • -10^6 <= nums[i] <= 10^6

解题思路提示

  1. 状态定义
    • 可以使用两个数组,dp 数组用来记录以每个位置结尾的最长递增子序列的长度,count 数组用来记录以每个位置结尾的最长递增子序列的个数。
  2. 状态转移方程
    • 对于每个位置 i ,遍历 0 到 i - 1 的位置 j ,如果 nums[i] > nums[j] ,则可以更新 dp[i] 和 count[i] 。
    • 更新 dp[i] :dp[i] = max(dp[i], dp[j] + 1) 。
    • 更新 count[i] :如果 dp[i] == dp[j] + 1 ,则 count[i] += count[j] ;如果 dp[i] < dp[j] + 1 ,则 count[i] = count[j] 。
  3. 最终结果
    • 遍历 dp 数组找到最长递增子序列的长度 maxLen 。
    • 再次遍历 count 数组,将所有对应 dp 值为 maxLen 的 count 值累加起来,得到最长递增子序列的个数.

 代码实现(Java):

/*** ClassName:LongestIncreasingSubsequenceCount** @Author 爱掉头发的小李* @Create 2025/1/26 15:46* @Version 1.0*/
public class LongestIncreasingSubsequenceCount {public int findNumberOfLIS(int[] nums) {// 如果数组为空,直接返回 0if (nums == null || nums.length == 0) {return 0;}int n = nums.length;// dp 数组用于记录以每个位置结尾的最长递增子序列的长度,初始值都为 1int[] dp = new int[n];// count 数组用于记录以每个位置结尾的最长递增子序列的个数,初始值都为 1int[] count = new int[n];// 初始化 dp 数组和 count 数组for (int i = 0; i < n; i++) {dp[i] = 1;count[i] = 1;}// 填充 dp 数组和 count 数组for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {// 如果当前元素可以接在前面的元素后面形成更长的递增子序列if (dp[j] + 1 > dp[i]) {dp[i] = dp[j] + 1;count[i] = count[j];} else if (dp[j] + 1 == dp[i]) {// 如果长度相同,累加个数count[i] += count[j];}}}}// 找到最长递增子序列的长度int maxLength = 0;for (int len : dp) {maxLength = Math.max(maxLength, len);}// 计算最长递增子序列的个数int result = 0;for (int i = 0; i < n; i++) {if (dp[i] == maxLength) {result += count[i];}}return result;}public static void main(String[] args) {LongestIncreasingSubsequenceCount solution = new LongestIncreasingSubsequenceCount();int[] nums = {1, 3, 5, 4, 7};System.out.println(solution.findNumberOfLIS(nums));}
}

代码说明:

  1. 初始化部分

    • 首先检查输入数组 nums 是否为空或长度为 0,如果是则直接返回 0。
    • 初始化 dp 数组,将每个元素初始化为 1,因为每个元素自身可以构成一个长度为 1 的递增子序列。
    • 初始化 count 数组,同样将每个元素初始化为 1,表示以该元素结尾的长度为 1 的递增子序列的个数为 1。
  2. 双重循环填充 dp 和 count 数组

    • 外层循环遍历数组中的每个元素,从索引 1 开始。
    • 内层循环遍历当前元素之前的所有元素。
    • 如果当前元素 nums[i] 大于 nums[j],说明可以将 nums[i] 接在以 nums[j] 结尾的递增子序列后面:
      • 如果 dp[j] + 1 大于 dp[i],则更新 dp[i] 为 dp[j] + 1,并将 count[i] 更新为 count[j],因为找到了更长的递增子序列。
      • 如果 dp[j] + 1 等于 dp[i],说明找到了同样长度的递增子序列,将 count[i] 加上 count[j]
  3. 计算最长递增子序列的长度

    • 遍历 dp 数组,找到其中的最大值 maxLength,即为最长递增子序列的长度。
  4. 计算最长递增子序列的个数

    • 再次遍历 dp 数组,将所有 dp[i] 等于 maxLength 的 count[i] 累加起来,得到最长递增子序列的个数。

相关文章:

每日一道算法题

题目&#xff1a;最长递增子序列的个数 给定一个未排序的整数数组&#xff0c;找到最长递增子序列的个数。 示例 1 输入&#xff1a;nums [1,3,5,4,7]输出&#xff1a;2解释&#xff1a;有两个最长递增子序列&#xff0c;分别是 [1,3,4,7] 和 [1,3,5,7] 。 示例 2 输入&a…...

低代码系统-产品架构案例介绍、明道云(十一)

明道云HAP-超级应用平台(Hyper Application Platform)&#xff0c;其实就是企业级应用平台&#xff0c;跟微搭类似。 通过自设计底层架构&#xff0c;兼容各种平台&#xff0c;使用低代码做到应用搭建、应用运维。 企业级应用平台最大的特点就是隐藏在冰山下的功能很深&#xf…...

论文笔记(六十三)Understanding Diffusion Models: A Unified Perspective(三)

Understanding Diffusion Models: A Unified Perspective&#xff08;三&#xff09; 文章概括 文章概括 引用&#xff1a; article{luo2022understanding,title{Understanding diffusion models: A unified perspective},author{Luo, Calvin},journal{arXiv preprint arXiv:…...

利用机器学习创建基于位置的推荐程序

推荐系统被广泛应用于不同的应用程序中&#xff0c;用于预测用户对产品或服务的偏好或评价。在过去的几分钟或几小时里&#xff0c;你很可能在网上遇到过或与某种类型的推荐系统进行过互动。这些推荐系统有不同的类型&#xff0c;其中最突出的包括基于内容的过滤和协作过滤。在…...

每日一题 429. N 叉树的层序遍历

429. N 叉树的层序遍历 /*class Solution { public:vector<vector<int>> levelOrder(Node* root) {queue<Node*> que;que.push(root);vector<vector<int>> ans;if(root nullptr){return ans;}while(!que.empty()){int sizeQue que.size();vec…...

AIP-132 标准方法:List

编号132原文链接AIP-132: Standard methods: List状态批准创建日期2019-01-21更新日期2022-06-02 在许多API中&#xff0c;通常会向集合URI&#xff08;例如 /v1/publishers/1/books &#xff09;发出GET请求&#xff0c;获取集合中资源的列表。 面向资源设计&#xff08;AIP…...

CSAPP学习:前言

前言 本书简称CS&#xff1a;APP。 背景知识 一些基础的C语言知识 如何阅读 Do-做系统 在真正的系统上解决具体的问题&#xff0c;或是编写和运行程序。 章节 2025-1-27 个人认为如下章节将会对学习408中的操作系统与计算机组成原理提供帮助&#xff0c;于是先凭借记忆将其简单…...

【统计的思想】假设检验(二)

假设检验是根据人为设定的显著水平&#xff0c;对被测对象的总体质量特性进行统计推断的方法。 如果我们通过假设检验否定了零假设&#xff0c;只是说明在设定的显著水平下&#xff0c;零假设成立的概率比较小&#xff0c;并不是说零假设就肯定不成立。如果零假设事实上是成立…...

KNN算法学习实践

1.理论学习 原文链接 ShowMeAI知识社区 2.案例实践 假如一套房子打算出租&#xff0c;但不知道市场价格&#xff0c;可以根据房子的规格&#xff08;面积、房间数量、厕所数量、容纳人数等&#xff09;&#xff0c;在已有数据集中查找相似&#xff08;K近邻&#xff09;规格…...

数据可视化的图表

1.折线图反映了一段时间内事物连续的动态变化规律,适用于描述一个变量随另一个变量变化的趋势,通常用于绘制连续数据,适合数据点较多的情况。 2.散点图是以直角坐标系中各点的密集程度和变化趋势来表示两种现象间的相关关系&#xff0c;常用于显示和比较数值。当要在不考虑时间…...

动手学深度学习-卷积神经网络-3填充和步幅

目录 填充 步幅 小结 在上一节的例子&#xff08;下图&#xff09; 中&#xff0c;输入的高度和宽度都为3&#xff0c;卷积核的高度和宽度都为2&#xff0c;生成的输出表征的维数为22。 正如我们在 上一节中所概括的那样&#xff0c;假设输入形状为nhnw&#xff0c;卷积核形…...

【JS|第28期】new Event():前端事件处理的利器

日期&#xff1a;2025年1月24日 作者&#xff1a;Commas 签名&#xff1a;(ง •_•)ง 积跬步以致千里,积小流以成江海…… 注释&#xff1a;如果您觉得有所帮助&#xff0c;帮忙点个赞&#xff0c;也可以关注我&#xff0c;我们一起成长&#xff1b;如果有不对的地方&#xf…...

Spring Boot 中的事件发布与监听:深入理解 ApplicationEventPublisher(附Demo)

目录 前言1. 基本知识2. Demo3. 实战代码 前言 &#x1f91f; 找工作&#xff0c;来万码优才&#xff1a;&#x1f449; #小程序://万码优才/r6rqmzDaXpYkJZF 基本的Java知识推荐阅读&#xff1a; java框架 零基础从入门到精通的学习路线 附开源项目面经等&#xff08;超全&am…...

【Spring】Spring启示录

目录 前言 一、示例程序 二、OCP开闭原则 三、依赖倒置原则DIP 四、控制反转IOC 总结 前言 在软件开发的世界里&#xff0c;随着项目的增长和需求的变化&#xff0c;如何保持代码的灵活性、可维护性和扩展性成为了每个开发者必须面对的问题。传统的面向过程或基于类的设计…...

ospf动态路由配置,cost路径调整,ospf认证实验

一、实验拓扑如图&#xff1a; 接口ip配置网络 &#xff1a;10.17.12.* 10.17.13.* &#xff0c;10.17.23.* 回环接口配置分别为 10.0.1.1 &#xff0c;10.0.1.2&#xff0c;10.0.1.3对应三台路由器 ar1配置接口ip interface GigabitEthernet0/0/0 ip address 10.17.12.1…...

在Rust应用中访问.ini格式的配置文件

在Rust应用中访问.ini格式的配置文件&#xff0c;你可以使用第三方库&#xff0c;比如 ini 或 config. 下面是一个使用 ini 库的示例&#xff0c;该库允许你读取和解析.ini文件。 使用 ini 库 添加依赖 首先&#xff0c;你需要在你的 Cargo.toml 文件中添加 ini 库的依赖&am…...

批量处理多个模型的预测任务

#!/bin/bash# 检查是否传入必要的参数&#xff0c;若未传入参数则打印用法并退出 if [ "$#" -lt 1 ]; thenecho "用法: $0 <file_path>"echo "示例: $0 /home/aistudio/work/PaddleSeg/city/cityscapes_urls_extracted.txt"exit 1 fi# 读取…...

Java 编程初体验

Java学习资料 Java学习资料 Java学习资料 一、引言 在当今数字化的时代&#xff0c;编程已然成为一项极具价值的技能。而 Java 作为一门广泛应用于企业级开发、移动应用、大数据等众多领域的编程语言&#xff0c;吸引着无数初学者投身其中。当我们初次踏入 Java 编程的世界&…...

element-plus 的table section如何实现单选

如果是单选那么全新的按钮应该隐藏或者不可编辑的状态。但是我没找到改变成不可编辑的方法&#xff0c;只能采取隐藏 <template><!-- 注意要包一层div根元素&#xff0c;否则css样式可能会不生效&#xff0c;原因不详 --><div><el-table ref"proTab…...

【JavaEE进阶】图书管理系统 - 壹

目录 &#x1f332;序言 &#x1f334;前端代码的引入 &#x1f38b;约定前后端交互接口 &#x1f6a9;接口定义 &#x1f343;后端服务器代码实现 &#x1f6a9;登录接口 &#x1f6a9;图书列表接口 &#x1f384;前端代码实现 &#x1f6a9;登录页面 &#x1f6a9;…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...