[100天算法】-最长递增子序列的个数(day 47)

题目描述

给定一个未排序的整数数组,找到最长递增子序列的个数。示例 1:输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5。
注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

方法 1:动态规划

思路

代码

JavaScript Code

/*** @param {number[]} nums* @return {number}*/
var findNumberOfLIS = function (nums) {const n = nums.length;const length = Array.from({ length: n }).fill(1);const count = Array.from({ length: n }).fill(1);for (let i = 0; i < n; i++) {for (let j = 0; j < i; j++) {if (nums[j] >= nums[i]) continue;if (length[j] + 1 > length[i]) {length[i] = length[j] + 1;count[i] = count[j];} else if (length[j] + 1 == length[i]) {count[i] += count[j];}}}const longest = Math.max(...length);return length.reduce((cnt, len, i) => (len == longest ? cnt + count[i] : cnt),0);
};

C++ Code

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {int n = nums.size();vector<int> length(n, 1);vector<int> count(n, 1);for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] <= nums[j]) continue;if (length[j] + 1 > length[i]) {length[i] = length[j] + 1;count[i] = count[j];}else if (length[j] + 1 == length[i]) {count[i] += count[j];}}}int longest = *max_element(length.begin(), length.end());int ans = 0;for (int i = 0; i < n; i++) {if (length[i] == longest) {ans += count[i];}}return ans;}
};

复杂度分析

  • 时间复杂度:$O(N^2)$。N 是数组 nums 的长度。
  • 空间复杂度:$O(N)$。N 是辅助数组 length 和 count 的长度。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/174987.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

第16期 | GPTSecurity周报

GPTSecurity是一个涵盖了前沿学术研究和实践经验分享的社区&#xff0c;集成了生成预训练 Transformer&#xff08;GPT&#xff09;、人工智能生成内容&#xff08;AIGC&#xff09;以及大型语言模型&#xff08;LLM&#xff09;等安全领域应用的知识。在这里&#xff0c;您可以…

Ceph入门到精通-bluestore IO流程及导入导出

bluestore 直接管理裸设备&#xff0c;实现在用户态下使用linux aio直接对裸设备进行I/O操作 写IO流程&#xff1a; 一个I/O在bluestore里经历了多个线程和队列才最终完成&#xff0c;对于非WAL的写&#xff0c;比如对齐写、写到新的blob里等&#xff0c;I/O先写到块设备上&am…

【操作系统】考研真题攻克与重点知识点剖析 - 第 1 篇:操作系统概述

前言 本文基础知识部分来自于b站&#xff1a;分享笔记的好人儿的思维导图与王道考研课程&#xff0c;感谢大佬的开源精神&#xff0c;习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析&#xff0c;本人技术…

总结之数据分析工具cube.js通过Docker部署

cube.js介绍 官网地址&#xff1a;https://cube.dev/ Cube.js是一个开源的模块化框架&#xff0c;用于构建分析web应用程序。它主要用于构建内部业务智能工具或向现有应用程序添加面向客户的分析。 Cube.js设计用于无服务器查询引擎&#xff0c;如AWS Athena和谷歌BigQuery。…

《HelloGitHub》第 91 期

兴趣是最好的老师&#xff0c;HelloGitHub 让你对编程感兴趣&#xff01; 简介 HelloGitHub 分享 GitHub 上有趣、入门级的开源项目。 github.com/521xueweihan/HelloGitHub 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等&#xff0c;涵盖多种编程语言 Python、…

BI是什么?想要了解BI需要从哪些方面入手?

企业为了执行数字化战略&#xff0c;实行数字化转型&#xff0c;实现数据价值&#xff0c;除了需要相关数字化技术及理念、人才等&#xff0c;还需要借助数字化相关应用&#xff0c;例如商业世界中广受企业欢迎的ERP、OA、CRM等业务信息系统&#xff0c;以及上升势头非常迅猛的…

京东科技埋点数据治理和平台建设实践 | 京东云技术团队

导读 本文核心内容聚焦为什么要埋点治理、埋点治理的方法论和实践、奇点一站式埋点管理平台的建设和创新功能。读者可以从全局角度深入了解埋点、埋点治理的整体思路和实践方法&#xff0c;落地的埋点工具和创新功能都有较高的实用参考价值。遵循埋点治理的方法论&#xff0c;…

nodejs+vue学生考勤综合平台的设计与实现-计算机毕业设计

在当今高度发达的信息中&#xff0c;信息管理改革已成为一种更加广泛和全面的趋势。 “学生考勤综合平台”是基于Mysql数据库&#xff0c;在 程序设计的基础上实现的。为确保中国经济的持续发展&#xff0c;信息时代日益更新&#xff0c;蓬勃发展。 因此&#xff0c;国内外技术…

mybatis-plus正确使用姿势:依赖配置、Mapper扫描、多数据源、自动填充、逻辑删除。。。

一、前言 本文基于 springboot、maven、jdk1.8、mysql 开发&#xff0c;所以开始前我们需要准备好这套环境。 1.1 依赖准备 想要什么依赖版本的去 maven 仓库查看&#xff1a;https://mvnrepository.com/ 引入 mybatis-plus 依赖&#xff1a; <dependency><group…

1 — NLP 的文本预处理技术

一、说明 在本文中&#xff0c;我们将讨论以下主题&#xff1a;1为什么文本预处理很重要&#xff1f;2 文本预处理技术。这个文对预处理做一个完整化、程序化处理&#xff0c;这对NLP处理项目中有很大参考性。 二、为什么文本预处理很重要&#xff1f; 数据质量显着影响机器学习…

【C++项目】高并发内存池第五讲内存回收释放过程介绍

内存回收 1.ThreadCache2.CentralCache3.PageCache 项目源代码&#xff1a;高并发内存池 1.ThreadCache void ThreadCache::Deallocate(void* ptr, size_t size) {assert(ptr);assert(size < MAX_BYTES);//计算在哪号桶中&#xff0c;然后插入进去size_t index SizeClass…

Docker 笔记(上篇)

Docker 概述 Docker 概念 Docker 是一个开源的应用容器引擎&#xff0c;让开发者可以打包他们的应用以及依赖包到一个可移植的镜像中&#xff0c;然后发布到任何流行的 Linux或Windows操作系统的机器上&#xff0c;也可以实现虚拟化。容器是完全使用沙箱机制&#xff0c;相互之…

qml之ui控件

文章目录 ui控件移动版风格嵌套页面并排界面 ui控件 Qt Quick控件用于创建由标准化组件&#xff08;如按钮、标签、滑块等&#xff09;构建的用户界面。 QtQuick.Controls&#xff1a;基本控件。QtQuick.Templates&#xff1a;为控件提供行为化的、非可化视的基本类型。QtQui…

基于旗鱼算法的无人机航迹规划-附代码

基于旗鱼算法的无人机航迹规划 文章目录 基于旗鱼算法的无人机航迹规划1.旗鱼搜索算法2.无人机飞行环境建模3.无人机航迹规划建模4.实验结果4.1地图创建4.2 航迹规划 5.参考文献6.Matlab代码 摘要&#xff1a;本文主要介绍利用旗鱼算法来优化无人机航迹规划。 1.旗鱼搜索算法 …

六、【图像去水印】

文章目录 裁剪法移动复制法内容识别去水印色阶法去水印消失点法去水印反相混合法 裁剪法 处于边缘的水印&#xff0c;通过裁剪去除&#xff0c;如下图&#xff1a; 移动复制法 移动复制法适用于水印的背景这部分区域比较相似的情况下使用&#xff0c;如下图先使用矩形选区选中…

C++标准模板(STL)- 类型支持 (类型特性,is_pointer,is_lvalue_reference,is_rvalue_reference)

类型特性 类型特性定义一个编译时基于模板的结构&#xff0c;以查询或修改类型的属性。 试图特化定义于 <type_traits> 头文件的模板导致未定义行为&#xff0c;除了 std::common_type 可依照其所描述特化。 定义于<type_traits>头文件的模板可以用不完整类型实…

YOLOv8如何添加注意力模块?

分为两种&#xff1a;有参注意力和无参注意力。 eg: 有参&#xff1a; import torch from torch import nnclass EMA(nn.Module):def __init__(self, channels, factor8):super(EMA, self).__init__()self.groups factorassert channels // self.groups > 0self.softmax …

实战之巧用header头

案例&#xff1a; 遇到过三次 一次是更改accept&#xff0c;获取到tomcat的绝对路径&#xff0c;结合其他漏洞获取到shell。 一次是更改accept&#xff0c;越权获取到管理员的MD5加密&#xff0c;最后接管超管权限。 一次是更改accept&#xff0c;结合参数获取到key。 这里以越…

RabbitMQ如何保证消息不丢失呢?

RabbitMQ 是一个流行的消息队列系统&#xff0c;用于在分布式应用程序之间传递消息。要确保消息不会丢失&#xff0c;可以采取以下一些措施&#xff1a; 持久化消息&#xff1a; RabbitMQ 允许你将消息标记为持久化的。这意味着消息将被写入磁盘&#xff0c;即使 RabbitMQ 服务…

关于TeamViewer链接问题

TeamViewer 远程出现下面问题 解决方案&#xff1a; 1.版本不统一 &#xff08;两边&#xff09;都升级到最新版本 2.网络要链接通常