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

news/2024/4/15 15:06:32

题目描述

给定一个未排序的整数数组,找到最长递增子序列的个数。示例 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.ppmy.cn/news/1187003.html

相关文章

[100天算法】-二叉树剪枝(day 48)

题目描述 给定二叉树根结点 root &#xff0c;此外树的每个结点的值要么是 0&#xff0c;要么是 1。返回移除了所有不包含 1 的子树的原二叉树。( 节点 X 的子树为 X 本身&#xff0c;以及所有 X 的后代。)示例1: 输入: [1,null,0,0,1] 输出: [1,null,0,null,1]示例2: 输入: […

小程序开发——小程序项目的配置与生命周期

1.app.json配置属性 app.json配置属性 2.页面配置 app的页面配置指的是pages属性&#xff0c; pages数组的第一个页面将默认作为小程序的启动页。利用开发工具新建页面时&#xff0c;则pages属性对应的数组将自动添加该页面的路径&#xff0c;若是在硬盘中添加文件的形式则不…

浅谈js代码的封装方法(2023.10.30)

常见的js代码封装方法 2023.10.30 需求1、js代码封装的优缺点2、js代码封装方式2.1 方式一&#xff1a;function function declarations2.1.1 示例 2.2 方式二&#xff1a;class2.2.1 class declarations2.2.2 Class expressions 2.3 变量函数2.4 变量闭包匿名函数2.5 闭包函数…

你被骗了吗?别拿低价诱骗机器视觉小白,4000元机器视觉系统怎么来的?机器视觉工程师自己组装一个2000元不到,还带深度学习

淘宝闲鱼&#xff0c;大家搜搜铺价格&#xff0c;特别是机器视觉小白。 机架&#xff1a;&#xff08;新的&#xff09;200元以下。(看需求&#xff0c;自己简单打光&#xff0c;买个50元的。如果复杂&#xff0c;就拿给供应商免费打光) 相机&#xff0c;镜头&#xff1a;&am…

计算机网络与技术——数据链路层

&#x1f60a;计算机网络与技术——数据链路层 &#x1f680;前言☃️基本概念&#x1f94f;封装成帧&#x1f94f;透明传输&#x1f94f;差错检测 ☃️点对点协议PPP&#x1f94f;PPP协议的特点&#x1f94f;PPP协议的帧格式&#x1f50d;PPP异步传输时透明传输&#xff08;字…

软考高项-十大知识领域,49活动

知识领域数量项目管理过程组启动规划执行监控收尾项目整体管理7制订项目章程制订项目管理计划管理与指导项目工作 管理项目知识 监控项目管理工作 实施整体变更控制 结束项目或阶段项目范围管理6规划范围管理 收集需求 定义范围 创建WBS 确认范围 控制范围 项目进度管理6<

【Vue原理解析】之响应式系统

引言 Vue2的响应式系统是核心之一&#xff0c;它使得Vue.js能够实现数据驱动的视图变化。其实现主要基于Object.defineProperty API&#xff0c;通过在数据对象上添加属性监听来实现数据变化时对视图进行更新。 vue3实现主要基于Proxy API和Reactive&#xff0c;Reactive函数…

小红书平台用户数据分析与可视化

管理器、网页下载器、网页解析器、输出管理器这四个模块去搭建一个爬虫框架&#xff0c;将爬虫流程统一化&#xff0c;将通用的功能进行抽象&#xff0c;减少重复工作。要求实现的爬虫框架可以进行分布式爬取&#xff0c;解决爬虫的统一调度和统一去重&#xff0c;以及存储问题…

Jetson Xavier NX FFmpeg支持硬件编解码

最近在用Jetson Xavier NX板子做视频处理&#xff0c;但是CPU进行视频编解码&#xff0c;效率比较地下。 于是便考虑用硬解码来对视频进行处理。 通过jtop查看&#xff0c;发现板子是支持 NVENC硬件编解码的。 1、下载源码 因为需要对ffmpeg进行打补丁修改&#xff0c;因此需…

HTTPS协议与WordPress升级后网站不兼容的解决方法

茹莱神兽个人博客之前上线装了一个WordPress缓存插件WP Super Cache&#xff0c;这个WordPress插件安装是有一些条件的&#xff1b;茹莱神兽没有注意这些&#xff0c;直接按照常规插件的方法装的&#xff0c;结果插件出现了后台不兼容问题&#xff0c;不过还是能勉强用&#xf…

JMeter的使用——傻瓜式学习【中】

目录 前言 1、JMeter参数化 1.1、什么是参数化 1.2、用户定义的变量 1.2.1、什么时候使用用户定义的变量 1.2.2、使用“用户定义的变量”进行参数化的步骤&#xff1a; 1.2.3、案例 1.3、用户参数 1.3.1、什么时候使用用户参数&#xff1f; 1.3.2、使用“用户参数”进…

Echats-自定义图表2

效果图&#xff1a; 代码&#xff1a; <!DOCTYPE html> <html lang"zh-cmn-Hans"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>…

STM32单片机智能小车一PWM方式实现小车调速和转向

目录 1. 电机模块开发 2. 让小车动起来 3. 串口控制小车方向 4. 如何进行小车PWM调速 5. PWM方式实现小车转向 1. 电机模块开发 L9110s概述 接通VCC&#xff0c;GND 模块电源指示灯亮&#xff0c; 以下资料来源官方&#xff0c;具体根据实际调试 IA1输入高电平&#xff…

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

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

新能源汽车电池包自动三维尺寸检测系统蓝光光学平面度测量仪-CASAIM

电池包是新能源汽车核心能量源&#xff0c;为整车提供驱动电能。作为新能源汽车的核心部件&#xff0c;其品质直接决定了整车性能。 由于电池包的生产工艺相对复杂&#xff0c;传统的测量工具不仅测量工序复杂、精度不足&#xff0c;还会或多或少接触到电池表面形成瑕疵&#…

数字化转型系列主题:PEST分析方法与样例说明

定义 PEST分析是一种常用的战略管理工具&#xff0c;用于评估和分析宏观环境对组织或项目的影响。它通过考察政治、经济、社会和技术等四个方面的因素&#xff0c;帮助组织识别、理解和应对外部环境中的机会和威胁。 PEST分析的核心分析元素 PEST分析包含四个核心分析元素&am…

原来低代码开发如此简单

目录 一、技术介绍 二、设计原理 三、界面展示 四、功能框架 我们在低代码领域探索了多年&#xff0c;从2014 开始研发低代码前端渲染&#xff0c;从 2018 年开始研发后端低代码数据模型&#xff0c;发布了JNPF快速开发平台。 JNPF低代码是一款新奇、实用、高效的企业级软件开发…

Vue自定义指令directive

什么是指令 vue官方提供很多指令&#xff0c;如&#xff1a;v-model&#xff0c;v-show&#xff0c;v-if&#xff0c;v-if等&#xff0c;他们都以v-开头。当这些指令不能满足我们实际开发需求时&#xff0c;我们还可以自定义指令。自定义指令主要分为全局自定义指令和局部自定…

虚拟机VMware怎么完全卸载干净

虚拟机VMware怎么完全卸载干净-百度经验 (baidu.com)

TypeScript深度剖析:TypeScript 中接口的应用场景?

一、是什么 接口是一系列抽象方法的声明&#xff0c;是一些方法特征的集合&#xff0c;这些方法都应该是抽象的&#xff0c;需要由具体的类去实现&#xff0c;然后第三方就可以通过这组抽象方法调用&#xff0c;让具体的类执行具体的方法 简单来讲&#xff0c;一个接口所描述…
最新文章