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

server/2024/12/3 4:08:00/

目录

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/server/140549.html

相关文章

Rust项目中的Labels

姊妹篇: Go项目中的Labels 按照issue数量从多到少排序: https://github.com/rust-lang/rust/labels?page2&sortcount-desc https://github.com/rust-lang/rust/labels/A-contributor-roadblock 第1页: 标签/中文说明数字T-compiler/编译器Relevant to the compiler tea…

笔记--(网络3)、交换机、VLAN

交换机 交换机&#xff08;Switch&#xff09;意为“开关”是一种用于电&#xff08;光&#xff09;信号转发的网络设备。它可以为接入交换机的任意两个网络节点提供独享的电信号通路。最常见的交换机是以太网交换机。其他常见的还有电话语音交换机、光纤交换机等。 交换机的…

virtualBox部署minikube+istio

环境准备 virtualBox安装 直接官网下载后安装即可&#xff0c;网上也有详细教程。镜像使用的centos7。 链接&#xff08;不保证还可用&#xff09;&#xff1a;http://big.dxiazaicc.com/bigfile/100/virtualbox_v6.1.26_downcc.com.zip?auth_key1730185635-pWBtV8LynsxPD0-0-…

[OpenGL]使用OpenGL实现硬阴影效果

一、简介 本文介绍了如何使用OpenGL实现硬阴影效果&#xff0c;并在最后给出了全部的代码。本文基于[OpenGL]渲染Shadow Map&#xff0c;实现硬阴影的流程如下&#xff1a; 首先&#xff0c;以光源为视角&#xff0c;渲染场景的深度图&#xff0c;将light space中的深度图存储…

A021基于Spring Boot的自习室管理和预约系统设计与实现

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…

DeFi 4.0峥嵘初现:主权金融时代的来临

近年来&#xff0c;Web3领域的创新似乎遇到了瓶颈&#xff0c;DeFi&#xff08;去中心化金融&#xff09;从热潮的巅峰逐渐进入了一个沉寂期。我们再也没有见到像DeFi Summer那样的行业兴奋&#xff0c;资本市场的动荡和Meme币的出现&#xff0c;似乎让人们忘记了曾经的区块链技…

Windows安装tensorflow的GPU版本

前言 首先本文讨论的是windows系统&#xff0c;显卡是英伟达&#xff08;invida&#xff09;如何安装tensorflow-gpu。一共需要安装tensorflow-gpu、cuDNN、CUDA三个东西。其中CUDA是显卡的驱动库&#xff0c;cuDNN是深度学习加速库。 安装开始前&#xff0c;首先需要安装好c…

用 Python 自动检测交易图形态的实用指南请查收

作者&#xff1a;老余捞鱼 原创不易&#xff0c;转载请标明出处及原作者。 写在前面的话&#xff1a; 本文详细介绍了如何利用 Python 和 EODHD API 来自动化检测股票交易市场中的蜡烛图形态。我会解释作为交易策略重要组成部分蜡烛图的基本概念&#xff0c;并说明这些数…