76. 最长上升子序列动态规划+二分查找

给定一个整数序列,找到最长上升子序列(LIS),返回LIS的长度。 说明 最长上升子序列的定义: 最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列,这种子序列不一定是连续的或者唯一的。 https://en.wikipedia.org/wiki/Longest_increasing_subsequence 样例 给出 [5,4,1,2,3],LIS 是 [1,2,3],返回 3 给出 [4,2,4,5,3,7],LIS 是 [2,4,5,7],返回 4 挑战 要求时间复杂度为O(n^2) 或者 O(nlogn)

动态规划+二分查找

模拟一个堆栈,遍历数组,我们先把第一个数放入堆栈,然后从第二个数开始遍历数组,如果这个数大于栈顶,则入栈,如果小于栈顶,则替换掉栈中第一个大于此数的那个数(这里可以用二分查找的方法,因为入栈的时候就已经排序)。 简单举个例子:

有数组:
6 1 3 5 4 3 5
遍历的话:
6                                       
1                                 //6大于1,替换
1 3                              //3大与1,入栈
1 3 5                           //5大于3,入栈
1 3 4                           //5是大于4的第一个,入栈
1 3 4                           //替换掉3,和不替换是一样的结果
1 3 4 5                        //5大于栈顶,入栈
end                          //结束,最长上升子序列为4个数,

在<algorithm>头文件里,有用在STL中查找第一个大于目标数字迭代器的算法,用这个函数当然是很简单的啦!

template<class ForwardIterator, class Type>
   ForwardIterator lower_bound(
      ForwardIterator _First, 
      ForwardIterator _Last,
      const Type& _Val
   );

参数是两个正向迭代器,表示查找范围,目标数字是_Val,返回一个指向第一个大于等于目标数字的数字的迭代器。这个函数效率肯定是高的。 为了练习我还是想把二分查找的写一下,这样一写还是发现了一些问题,所以想把二分查找这里总结一下,放在另外一篇文章中。 这个题到这里就结束了,代码:

int longestIncreasingSubsequence(vector<int> &nums) {
        if(nums.size()==0)
        return 0;
        
        vector<int>  res;
        res.push_back(nums[0]);
        for(int i=1;i<nums.size();i++)
        {
           if(nums[i]>*(res.end()-1))
           res.push_back(nums[i]);
           else
           {
              //auto pos=lower_bound(res.begin(), res.end(), nums[i]);
              // cout<<*pos<<endl;
              //*pos=nums[i];
             
              Insert(nums[i],res);
           }
        }
    
    
        return res.size();
        // write your code here
    }
    
    void Insert(int num,vector<int> &vec)
    {
        auto beg=vec.begin();
        auto end=vec.end()-1;
        vector<int>::iterator mid;
        while(beg<=end)
        {
            mid=beg+(end-beg)/2;
            if(num<*mid)
            {
                end=mid-1;
            }
            else if(num>*mid)
            {
                beg=mid+1;
            }
            else return;      //如果查找到,则替换
        }
        
        if(num>*mid)         //如果大于mid,就在其后插入
        *(mid+1)=num;
        else 
        *mid=num;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏移动端开发

Swift 内存管理详解

Swift内存管理: Swift 和 OC 用的都是ARC的内存管理机制,它们通过 ARC 可以很好的管理对象的回收,大部分的时候,程序猿无需关心 Swift...

2419
来自专栏null的专栏

python基础知识——内置数据结构(集合)

python中的set是指一系列无序元素的集合,其中的元素都是相异的,常见的操作包括集合的并集,交集和补集等操作。 1、set的创建 格式 set_name =...

3437
来自专栏用户2442861的专栏

二分查找

版权所有,转载请注明出处,谢谢!http://blog.csdn.net/walkinginthewind/article/details/8937978

1044
来自专栏老马说编程

(20) 为什么要有抽象类? / 计算机程序的思维逻辑

基本概念 上节提到了一个概念,抽象类,抽象类是什么呢?顾名思义,抽象类就是抽象的类,抽象是相对于具体而言的,一般而言,具体类有直接对应的对象,而抽象类没有,它...

2327
来自专栏Hongten

python开发_类型转换convert

E | hongtenzone@foxmail.com  B | http://www.cnblogs.com/hongten

1642
来自专栏一个会写诗的程序员的博客

第7章 集合类第7章 集合类

在 Java 类库中有一套相当完整的容器集合类来持有对象。Kotlin没有去重复造轮子(Scala则是自己实现了一套集合类框架),而是在Java 类库的基础上进...

802
来自专栏专注 Java 基础分享

深入理解Java常用类-----StringBuilder

     上篇文章我们介绍过String这个常用类,知道了该类的内部其实是用的一个char数组表示一个字符串对象的,只是该字符数组被final修饰,一旦初始化就...

2317
来自专栏精讲JAVA

Java知识点总结之Java泛型

1092
来自专栏java学习

Java每日一练(2017/8/17)

每日一句 学的到东西的事情是锻炼,学不到的是磨练。 查看以前的所有练习题目以及答案:https://mp.weixin.qq.com/mp/homepage?_...

2889
来自专栏DHUtoBUAA

查找数组中重复的数字

        题目来源于《剑指Offer》中的面试题3:找出数组中重复的数字。   // 题目:在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中...

4356

扫码关注云+社区

领取腾讯云代金券