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

devtools/2024/11/13 15:16:50/

目录

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();}


http://www.ppmy.cn/devtools/133040.html

相关文章

PGMP-串串01概述

项目集管理绩效域12345战略一致性效益管理相关方争取治理生命周期商业论证BC效益识别识别项目集治理实践1.阶段&#xff1a;定义&#xff0c;交付&#xff0c;收尾项目集章程效益分析与规划分析项目集治理角色2.项目集活动:10个管理 1变更&#xff0c;2沟通&#xff0c;3财务&a…

CSS教程(七)- 背景

介绍 背景属性可以设置背景颜色、背景图片、背景平铺、背景图片位置、背景图像固定等。 1 背景颜色 属性名&#xff1a;background-color 作用&#xff1a;指定HTML元素的背景色。 取值&#xff1a;英文颜色、16进制、rgb、rgba、transparent&#xff08;一般为透明&#…

MySQL中distinct与group by之间的性能进行比较

在 MySQL 中&#xff0c;DISTINCT 和 GROUP BY 都是用于去重或汇总数据的常用 SQL 语法。尽管它们在某些情况下能产生相同的结果&#xff0c;但它们的内部工作方式和性能表现可能有所不同。理解这两者的差异&#xff0c;对于选择正确的语法非常重要&#xff0c;尤其是在处理大量…

鸿蒙UI开发——实现环形文字

1、背 景 有朋友提问&#xff1a;您好关于鸿蒙UI想咨询一个问题 如果我想实现展示环形文字是需要通过在Text组件中设置transition来实现么&#xff0c;还是需要通过其他方式来实现。 针对这位粉丝朋友的提问&#xff0c;我们做一下解答。 2、实现环形文字效果 ❓ 什么是环形…

网关 Spring Cloud Gateway

一、简介 Gateway网关是我们服务的守门神&#xff0c;所有微服务的统一入口。Spring Cloud Gateway 是 Spring Cloud 的一个全新项目&#xff0c;该项目是基于 Spring 5.0&#xff0c;Spring Boot 2.0 和 Project Reactor 等技术开发的网关&#xff0c;它旨在为微服务架构提供…

力扣17-电话号码的数字组合

力扣17-电话号码的数字组合 思路代码 题目链接 思路 原题&#xff1a; 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。 输…

小型的网站服务器该如何选择配置?

对于选择小型网站服务器的配置主要根据企业网站的发展规模&#xff0c;以及网站业务的发展需求&#xff0c;下面就让我们来具体了解一下小型的网站服务器该怎样选择吧&#xff01; 首先企业需要按照每个月的网站访问量和数据的传输量&#xff0c;选择适合自己的网络带宽与流量限…

**AI的三大支柱:神经网络、大数据与GPU计算的崛起之路**

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…