贪心算法day2(最长递增子序列)

目录

1.最长递增子序列

方法一:动态规划 

方法二:贪心+二分查找


1.最长递增子序列

链接:. - 力扣(LeetCode)

方法一:动态规划 

思路:我们定义dp[i]为最长递增子序列,那么dp[j]就是在小于i范围内的最长子序列,最长子序列最少为1,所以dp数组初始化为1.代码实行步骤如下:

这种情况下时间复杂度为O(n*2) ,空间复杂度为 O(n)

具体实现如下:

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for(int i = 0; i < n; i++){
            dp[i] = 1;
        }
        int ret = 1;
        for(int i = 1; i < n ; i++){
          for(int j = 0; j < i ;j++){
               if(nums[j] < nums[i]){
                dp[i] = Math.max(dp[j] + 1,dp[i]);
                 ret = Math.max(ret,dp[i]);
               }
          }
        }
        return ret;
    }
}

方法二:贪心+二分查找

思路:我们用数组来举个例子

第二种情况:(ret.get(mid) > nums[i])

这种情况下时间复杂度为nlogN(二分查找的时间复杂度为logN),空间复杂度为O(n)

代码: 

 public static int lengthOfLIS(int[] nums){
        int n = nums.length;
        ArrayList<Integer> ret = new ArrayList<>();
        ret.add(nums[0]);
        for (int i = 0; i < n; i++) {

            if(nums[i] > ret.get(ret.size() - 1)){
                ret.add(nums[i]);
            }else{
                int left = 0,right = ret.size() - 1;
                while(left < right){
                    int mid = (left + right)/2;
                    if(ret.get(mid) < nums[i]){
                        left = mid + 1;
                    }else{
                        right = mid;
                    }
                }
                ret.set(left,nums[i]);
            }
        }
        return ret.size();
         }

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于微信小程序的电子购物系统的设计与实现(lw+演示+源码+运行)

摘 要 由于APP软件在开发以及运营上面所需成本较高&#xff0c;而用户手机需要安装各种APP软件&#xff0c;因此占用用户过多的手机存储空间&#xff0c;导致用户手机运行缓慢&#xff0c;体验度比较差&#xff0c;进而导致用户会卸载非必要的APP&#xff0c;倒逼管理者必须改…

雨晨 23H2 Windows 11 企业版 IE VCDX 适度 22631.4445 (VIP有限开放版本)

雨晨 23H2 Windows 11 企业版 IE VCDX 适度 22631.4445 &#xff08;VIP有限开放版本&#xff09; 文 件: 雨晨 23H2 Windows 11 企业版 适度 22631.4445 install.wim 提 取 码: ZZLR 大 小: 2824999564 字节 修改时间: 2024年11月9日, 星期六, 05:33:05 MD5 : 9C88…

OWASP TOP10 OSS 风险:开源软件安全指南

OWASP OSS 列表提供了旨在绕过 CVE 目录等滞后指标的建议&#xff0c;并为安全从业者提供了安全使用 OSS 组件的指南。 在最近的一些暴露的漏洞和风险之后&#xff0c;对开源软件 &#xff08;OSS&#xff09;的安全和使用方式进行批判性审视的呼声越来越高&#xff0c;特别是 …

无人机培训机型有哪些?CAAC考证选3类还是4类

无人机培训是一个涵盖多个方面的综合性过程&#xff0c;旨在培养具备无人机操作技能和相关知识的人才。 无人机培训机型 无人机培训通常涵盖多种机型&#xff0c;以满足不同领域和应用场景的需求。常见的无人机培训机型包括&#xff1a; 1. 多旋翼无人机&#xff1a;也称为多…

浏览器漫谈HTML--2.1印象深刻的标签-语义化标签

语义化标签 HTML语义化标签是HTML5引入的一个重要特性 常见的语义化标签&#xff1a; <header>, <nav>, <main>, <article>, <section>, <aside>, <footer> 布局如下 底层实现逻辑&&好处 语义化标签其实底层实现逻辑和…

el-table-column prop值根据数组获取

方法一&#xff1a; 可以给el-table-column添加一个属性&#xff1a;formatter&#xff0c;代码如下&#xff1a; 这里是因为多个列都需要同样的计算&#xff0c;所以使用column.property获取属性&#xff0c;不然可以直接row.属性 方法二&#xff1a; 直接在template scope …

2021-04-22 51单片机玩转点阵

理论就不赘述了,网络上多得很,直接从仿真软件感性上操作认识点阵,首先打开ISIS仿真软件,放置一个点阵和电源与地线就可以开始了;由点阵任何一脚连线到地线,另一边对应的引脚就连接到电源,如图:点击运行看是否点亮?看到蓝色与红色的点表示电源正常但是没有任何亮点,这时对调一下…

数据结构---详解单链表

一、单链表的概念及性质 1、链表的概念 链表是一种物理存储结构上非连续、非顺序的储存结构&#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 我们看上图&#xff0c;一个链表就很像一节节车厢一样&#xff0c;和顺序表不同的是&#xff0c;链表里的每节“…

基于Spring Boot的网上商品订单转手系统设计与实现,LW+源码+讲解

摘 要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff0c;在计算机上安装网上商品订单转手系统软件来发挥其高效地信息处理的作用&a…

金蝶云星空与聚水潭系统的数据无缝对接案例

金蝶云星空与聚水潭的其他出库单数据集成案例分享 在企业日常运营中&#xff0c;数据的高效流动和准确处理至关重要。本文将重点介绍如何通过轻易云数据集成平台&#xff0c;实现金蝶云星空系统中的其他出库单数据无缝对接到聚水潭系统。本次集成方案名为“金蝶-其他出库单——…

企业级大数据安全架构

安全架构 一、集群访问控制1.1 Kerberos认证机制1.2 Apache Knox 统一访问网关 二、资源授权管理2.1 Apache Ranger 数据授权与管理 三、服务安全保障3.1 LDAP 轻量目录访问协议 四、大数据安全架构 当谈到企业级大数据平台时&#xff0c;安全性是一个至关重要的方面。随着数据…

cv::intersectConvexConvex返回其中一个输入点集,两个点集不相交

问题&#xff1a;cv::intersectConvexConvex返回其中一个输入点集&#xff0c;但两个点集并不相交 版本&#xff1a;opencv 3.1.0 git上也有人反馈了intersectConvexConvex sometimes returning one of the input polygons in case of empty intersection #10044 是凸包嵌套判…

贪心算法day3(最长递增序列问题)

目录 1.最长递增三元子序列 2.最长连续递增序列 1.最长递增三元子序列 题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a;我们只需要设置两个数进行比较就好。设a为nums[0]&#xff0c;b 为一个无穷大的数&#xff0c;只要有比a小的数字就赋值…

SpringBoot助力的共享汽车业务优化系统

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…

基于STM32的LCD1602显示Proteus仿真设计(仿真+程序+设计报告+讲解视频)

这里写目录标题 1.主要功能0. 资料清单&下载链接资料下载链接&#xff1a;2.仿真设计3. 程序设计4. 设计报告5. 框图 基于STM32的LCD1602显示Proteus仿真设计(仿真程序设计报告讲解视频&#xff09; 仿真图proteus 8.9 程序编译器&#xff1a;keil 5 编程语言&#xff1a…

ArcGIS/QGIS按掩膜提取或栅格裁剪后栅格数据的值为什么变了?

问题描述&#xff1a; 现有一栅格数据&#xff0c;使用ArcGIS或者QGIS按照矢量边界进行按掩膜提取或者栅格裁剪以后&#xff0c;其值的范围发生了变化&#xff0c;如下&#xff1a; 可以看到&#xff0c;不论是按掩膜提取还是进行栅格裁剪后&#xff0c;其值的范围均与原来栅…

CKA认证 | Day1 k8s核心概念与集群搭建

第一章 Kubernetes 核心概念 1、主流的容器集群管理系统 容器编排系统&#xff1a; KubernetesSwarmMesos Marathon 2、Kubernetes介绍 Kubernetes是Google在2014年开源的一个容器集群管理系统&#xff0c;Kubernetes简称K8s。 Kubernetes用于容器化应用程序的部署&#x…

Nat Med病理AI系列|基础模型Virchow在病理学中的应用·顶刊精析·24-11-09

小罗碎碎念 今天是Nature Medicine病理AI系列的最后一篇文章&#xff0c;标题为A foundation model for clinical-grade computational pathology and rare cancers detection。 这篇文章介绍了一个大型病理基础模型Virchow&#xff0c;它在计算病理学领域实现了对常见和罕见癌…

vue3 + element-plus 的 upload + axios + django 文件上传并保存

之前在网上搜了好多教程&#xff0c;一直没有找到合适自己的&#xff0c;要么只有前端部分没有后端&#xff0c;要么就是写的不是很明白。所以还得靠自己摸索出来后&#xff0c;来此记录一下整个过程。 其实就是不要用默认的 action&#xff0c;要手动实现上传方式 http-reque…

多模态数字人AI产品正在革新金融业,解密头部银行、证券公司都在用的AI工具

在人工智能迅猛发展的时代背景下&#xff0c;金融业正迎来一场深刻的变革。 多模态的人工智能&#xff0c;以其独特的魅力&#xff0c;正在重塑金融行业的格局&#xff0c;为金融服务带来前所未有的新想象。从今年以来行业对AI技术的探索与实践中&#xff0c;AIGC 3D数字人多模…