leetcode 300 最长上升子序列_hhmy77的博客-程序员ITS301

技术标签: leetcode  

https://leetcode-cn.com/problems/longest-increasing-subsequence/

在这里插入图片描述
注意子序列不要求连续
一般这种最长啊,最大啊,不出意外就是dp了
根据之前的选择情况来更新当前的选择情况
一开始对着样例想了一个贪心
既然是求最长的子序列,那么我假设当前第一个子串就是数组的开头,并且使用一个变量来存储最长上升子序列的最后一个元素,记为R,一开始第一个R就是数组的开头
然后往后找一个最小的元素,这是分为两种情况

  1. 如果后面的最小元素大于当前的R,那么放心的加入子序列,同时更新R和最大长度,然后从新加入的元素的下标继续寻找最小的元素
  2. 如果后面的最小元素小于等于当前的R,那么当前子序列废弃,更新目前获得的最大长度,然后将这个最小元素设为新的子序列开头
    对着这个样例很美好
    [10,9,2,5,3,7,101,18]
    直接找到2 3 7 18,长度为4
    但是这种就不行了
    [8,9,10,4]
    直接从8跳到4了

dp

然后我就屈服于DP了,自己真的不会写DP(还是写得太少了),看了一眼题解
说一下思路
dp[i]表示以i下标结尾数组,其中最长的上升子序列长度
假设j<i,表示j下标位于i下标之前
那么dp[i]的选择就依赖于之前的最大值了,也就是max(dp[j]),0<=j<i
但是由于子序列要求上升,所以nums[i]必须要大于nums[j],这个时候dp[i]才能设置成max(dp[j])+1
但是当nums[i]<nums[j]的时候,并不是直接把dp[i]设置成1,因为它有可能继承其它最长上升子序列的长度
举个例子

nums:4	7	8	6
dp	:1	2	3	2->(4,6)

所以我们的状态转移方程中的max不是标准库函数里面的max,而是要遍历之前的dp[j]才能找到尽可能的最大值
dp推完了那就是写代码了…难点就是怎么把状态转移方程推出来

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 最直观的想法:
        if not nums:
            return 0
        maxsize=1
        dp=[1]*len(nums)
        for i in range(1,len(nums)):
            for j in range(0,i):
                if nums[j] < nums[i]:
                    dp[i]=max(dp[i],dp[j]+1)
        return max(dp)

DP就是辣么,但是自己写不出

贪心+二分

这里先证明了一个最长上升子序列的性质
在这里插入图片描述
概括一下,我们要求的最长上升子序列要尽可能地长,意为序列的元素要尽可能地多
怎么才能尽可能地多呢
首先子序列肯定是有序的,有序肯定可以用二分
每当我们遍历到一个新元素,就尝试把它加入到序列中,如果当前的新元素比序列最后一个元素还要大,那么就直接加入,万事大吉,如果新元素没有最后一个元素大,我们就尝试在序列中找到第一个大于它的数(c++中的lower_bound函数),然后替换掉比它大的旧元素
为什么要这样做呢,因为如果我们能使一个序列中的元素尽可能地小,它就能加入更多的新元素对吧?

	3 2 9 6 7
1:	3
2:	2	替换,因为2更小
3:	2 9	加入
4:	2 6 替换,6更小
5:	2 6 7	加入

很简单对吧?
重要的是上面分析过程中贪心的思想,有序我们也可以自然的想到使用二分搜索
奉上leetcode官网的一条评论
在这里插入图片描述

class Solution {
    
public:
    int lengthOfLIS(vector<int>& nums) {
    
        if(!nums.size())
            return 0;
        vector<int>maxlen;
        for(auto num:nums){
    
            if(maxlen.size()==0 or num>maxlen.back())
                maxlen.push_back(num);
            else if(num<maxlen.back()){
    
                // lower_bound(起始地址,结束地址,要查找的数值) 返回的是数值 第一个 出现的位置
                // 即使不出现,lower_bound返回的是元素应该在数组中插入的位置
                int ind=lower_bound(maxlen.begin(),maxlen.end(),num)-maxlen.begin();
                maxlen[ind]=num;
            }    
        }
        return maxlen.size();
    }
};

在这里插入图片描述
偷懒用了一下lower_bound
贴一下lower_bound的实现,功能是返回第一个大于等于x的元素的位置
需要注意的是while条件和>=的条件
在这里插入图片描述

在这里插入图片描述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/hhmy77/article/details/104898160

智能推荐

java和js的正则表达式一样吗_JavaScript与Java正则表达式写法的区别_耗奇心的博客-程序员ITS301

JavaScript验证写法:(转义符\)var str = "待验证文本";var regular = new RegExp(/这里是正则表达式/);if (regular.test(str)) {console.log("符合条件");} else {console.log("不符合条件");}//或者var str = "待验证文本";if (/这里是正则表达式/.test(str)) {c...

OneDrive - “An unknown error occurred”的解决方案_Kianteck的博客-程序员ITS301

在维护Office365时候,有遇到user report一个one drive issue,在move folder时候弹出错误信息“An unknown error occurred”,错误的code是0x80070005。本文对此做介绍。

Omdia:2021年全球消费类VR头盔销售量为1250万台 内容支出超过20亿美元_AI_Plus的博客-程序员ITS301

要点到 2026 年,消费者将使用 7000 万台 VR 头盔,他们将在 VR 游戏和其他娱乐上花费 75 亿美元。消费级 VR 市场的硬件和软件价值将从 2021 年的 64 亿美元增长到 2026 年的 160 亿美元。据估计,Meta Quest 2 在上市的头三个月里已经售出 240 万台,预计 2021 年还将售出 700 万台。约 90% 的 VR 内容是游戏消费支出。未来五年,VR 仍将是一个小众但不断增长的消费级娱乐市场。它将被元宇宙所产生的热潮和投资所推动。Omdia 的新研

【P4论文分享】P4: Programming Protocol-IndependentPacket Processors_zoetu的博客-程序员ITS301

本文致力于将解决OpenFlow定义新协议的困难,根据抽象转发模型定义了一种用于交换机数据包处理的语言P4,该语言具有现场可重构、协议无关性和目标无关性的特性。

iOS 支付宝授权登录,思路_终有丶的博客-程序员ITS301_ios 支付宝授权登录

关于支付宝授权登录,对于没写过的人来说感觉很难(写过了以后才发现很简单),在网上看了很多看的结果还是不明白,为了让刚接触的心里有点底,简单说下大概思路:1 导入支付宝SDK (pod导入,或者手动导入,就不细说了,具体可以看支付宝官方文档)2 我想看过看过支付宝demo的有很多不明白,demo代码如下 - (void)doAPPay{ // 重要说明 // 这里只是为了方...

Xamarin提示安装包错误解决办法_大学霸_ITDaren的博客-程序员ITS301

Xamarin提示安装包错误解决办法Xamarin提示安装包错误解决办法Xamarin提示安装包错误解决办法

随便推点

计算机与信息技术基础上机指导答案,信息技术基础学习指导——实验和习题解答(第3版)..._一只有思想的猴子的博客-程序员ITS301

上篇 实 验实验1 计算机基本操作实验31.1 计算机的基本操作3一、实验目的3二、实验任务3三、实验步骤和操作指导3四、练习71.2 汉字输入7一、实验目的7二、实验任务8三、实验步骤和操作指导8四、练习11实验2 Windows 7操作系统实验122.1 Windows 7基本操作12一、实验目的12二、实验任务12三、实验步骤和操作指导12四、练习162.2 “计算机”与“资...

使用NanoHttpd实现简易WebServer_jltxgcy的博客-程序员ITS301_nanohttpd 网页

0x00    在介绍使用NanoHttpd实现简易WebServer之前,我们首先熟悉下局域网Socket通信。一个Client工程,代码地址为https://github.com/jltxgcy/AppVulnerability/tree/master/MyClient。一个Server工程,代码地址为https://github.com/jltxgcy/AppVulnerability/tr

oracle advanced compression,Advanced Compression_李时珍的脾的博客-程序员ITS301

Oracle Advanced CompressionProvides a comprehensive set of compression capabilities to help improve database performance and reduce storage costs. It allows organizations to reduce their overall datab...

base64转图片、图片转base64、图片拼接、加水印(水印角度可设置)_weixin_30483495的博客-程序员ITS301

1 /** 2 * @Description: 将base64编码字符串转换为图片 3 * @param imgStr 4 * base64编码字符串 5 * @param path 6 * 图片路径-具体到文件 7 * @return 8 */ ...

编码器的参数设置_、、、、南山小雨、、、、的博客-程序员ITS301_编码器配置

编码器参数设置//sps/ppsenc_ctx-&gt;profile = FF_PROFILE_H264_HIGH_444;enc_ctx-&gt;level = 50; //表示LEVEL是5.0enc_ctx-&gt;width = 640;enc_ctx-&gt;height = 480;enc_ctx-&gt;pix_fmt = AV_PIX_FMT_YUV420P;enc_ctx-&gt;gop_size = 250;enc_ctx-&gt;keyint_min = 25;//o

【计算机视觉】张正友相机标定Calibration原理过程结果_来杯金桔柠檬的博客-程序员ITS301

一、数学原理1.将世界坐标转换为图像坐标:其中R为33的旋转矩阵,t为31的平移矢量,(xc,yc,zc,1)T(xc,yc,zc,1)T为相机坐标系的齐次坐标,(xw,yw,zw,1)T(xw,yw,zw,1)T为世界坐标系的齐次坐标。2.图像坐标转换为像素坐标系:其中,dXdX、dYdY分别为像素在XX、YY轴方向上的物理尺寸,u0,v0 u0,v0为主点(图像原点)坐标。3.针...

推荐文章

热门文章

相关标签