凉经算法题反思 | 单调栈与DP二分法

站长亦新
站长亦新
站长亦新
81
文章
0
评论
2020年7月30日05:42:32 评论 94 2358字阅读7分51秒
  1. 算法题1:
    一个数组nums,大小为n,返回数组同等大小的数组,返回数组满意以下条件:

- 对于数组nums中第i个元素,找到nums从i+1到第n个元素中第一个大于nums[i]的元素,值为j,如果不存在,j=-1

例子1:
- nums =[1,2,3,3,2,6,7,2,0]
- output = [2,3,6,6,6,7,-1,-1,-1]

例子2:
- nums = [4,3,2,1,2,3,4]
- output = [-1,4,3,2,3,4,-1]

解法
这道题的时间复杂度,如果用暴力法,O(n^2)的复杂度;但是如果用单调栈的算法,可以得到O(n)的时间复杂度.

这个过程引用到了单调栈的思想。就是一个栈,里面所有元素是非严格单调递增或者单调递减的。比较好思考,就是每一个数组都要越来越小,如果不满足递减的数字,说明要从栈中取出来几个数字了。

用例子2来举例:
假设现在有一个栈
```stack=[]```,前面的4个元素4,3,2,1单调递减,所以依次入栈。(这里入栈的是索引)

现在
```stack=[1,2,3,4]```,然后因为第五个元素是2,是大于栈顶的数字1的,所以1出栈,然后对于数字1这个位置的j就是数字2,然后2入栈。这里因为要记录值和

代码简单写了写,不是很干净:

nums=[4,3,2,1,2,3,4] # 例子2
nums=[1,2,3,3,2,6,7,2,0]  # 例子1
output = [-1] * len(nums) # 这个是要返回的数组
stack = [] # 这个是单调栈
for i in range(0,len(nums)):
    # 如果栈是空的或者栈顶元素大于这个元素,入栈
    if len(stack) == 0 or nums[stack[-1]] >= nums[i]:
        stack.append(i)
        continue
    # 如果栈顶元素小于这个元素,出栈
    while len(stack)>0 and nums[stack[-1]] < nums[i]:
        index = stack.pop()
        output[index]=nums[i]
    stack.append(i)
print(output)
  1. 算法题2:还有一道题是,找到一组数据中的最长递增子数组。比如:【1,2,4,2,5,3】,最长递增子数组是【1,2,4,5】

最长递增数组Longest Increasing Sequence,下面缩写LIS。

解法
这道题如果单纯的使用动态规划方法,可以得到O(n^2)的时间复杂度;如果使用二分法,可以得到O(nlogn)的复杂度。这道题关键在于用二分法的时候,如何找到有序数组进行查找。

这里直接讲解二分法的方法,动态规划的解法不难思考。

假设存在一个序列d[1..9] ={ 2,1 ,5 ,3 ,6,4, 8 ,9, 7},可以看出来它的LIS长度为5。下面一步一步试着找出它。

我们定义一个序列B,然后令 i = 1 to 9 逐个考察这个序列。
此外,我们用一个变量Len来记录现在最长算到多少了

首先,把d[1]有序地放到B里,令B[1] = 2,就是说当只有1一个数字2的时候,长度为1的LIS的最小末尾是2。这时Len=1

然后,把d[2]有序地放到B里,令B[1] = 1,就是说长度为1的LIS的最小末尾是1,d[1]=2已经没用了,很容易理解吧。这时Len=1

接着,d[3] = 5,d[3]>B[1],所以令B[1+1]=B[2]=d[3]=5,就是说长度为2的LIS的最小末尾是5,很容易理解吧。这时候B[1..2] = 1, 5,Len=2

再来,d[4] = 3,它正好加在1,5之间,放在1的位置显然不合适,因为1小于3,长度为1的LIS最小末尾应该是1,这样很容易推知,长度为2的LIS最小末尾是3,于是可以把5淘汰掉,这时候B[1..2] = 1, 3,Len = 2

继续,d[5] = 6,它在3后面,因为B[2] = 3, 而6在3后面,于是很容易可以推知B[3] = 6, 这时B[1..3] = 1, 3, 6,还是很容易理解吧? Len = 3 了噢。

第6个, d[6] = 4,你看它在3和6之间,于是我们就可以把6替换掉,得到B[3] = 4。B[1..3] = 1, 3, 4, Len继续等于3

第7个, d[7] = 8,它很大,比4大,嗯。于是B[4] = 8。Len变成4了

第8个, d[8] = 9,得到B[5] = 9,嗯。Len继续增大,到5了。

最后一个, d[9] = 7,它在B[3] = 4和B[4] = 8之间,所以我们知道,最新的B[4] =7,B[1..5] = 1, 3, 4, 7, 9,Len = 5。

于是我们知道了LIS的长度为5。

下面用Python来简单写一下:

nums = [1,2,4,2,5,3]
B = [0] * len(nums)
Len = 0
for i in range(0,len(nums)):
    num = nums[i]
    l = 1
    r = Len
    idx = int((l + r)/2)
    while r>l:
        if B[idx] > num:
            r = idx
        else:
            l = idx+1
        idx = int((l + r)/2)
    # 找到了二分点位置,做一个简单的判断
    if num < B[idx] and num >B[idx-1] :
        B[idx]=num
    if num > B[Len]:
        Len += 1
        B[Len] = num
print(B)
print(Len)

结果是:

[0, 1, 2, 3, 5, 0]
4

1,2,3,5的含义是:
- 1:如果数组长度是1,那么最小的数组中最大数就是1;
- 3:如果数组长度是3,那么有【1,2,4】,【1,2,5】,【1,4,5】,【1,2,3】四种情况,但是我们认为【1,2,3】是最好的因为,这个子数组中最大数字最小;
- 5:数组长度是4的时候,有【1,2,4,5】一种情况。

这里简单做一个总结罢了。二分法的关键在于单调数组中查找某一个数字的位置;动态规划在于寻找子优化问题;二分法的写法可以背住,到时候直接写出来就行不用动脑子。

weinxin
我的微信
微信扫一扫
站长亦新
  • 本文由 发表于 2020年7月30日05:42:32
  • 转载请务必保留本文链接:http://helloworld2020.net/690/
公告
Week 1 | 1 介绍¶ 第 1 题¶一个计算机程序从经验E中学习任务T,并用P来衡量表现。并且,T的表现P随着经验E的增加而提高。 假设我们给一个学习算法输入了很多历史天气的数据,让它学会预测天...
面试记录 公告

面试记录

跟谁学一面(挂掉) 项目 LightGBM和XGBoost的区别 GBDT模型和XGB的区别 LGB做了哪些优化 为什么选择他们的公司 阿里一面 项目 XGBoost的并行优化的两种方法; Light...
工程能力大UP | 《炼丹大法》 公告

工程能力大UP | 《炼丹大法》

xavier、He和随机初始化都要尝试。使用一般的随机均值初始化CNN的参数,acc只能到70%,仅仅改成xavier,acc可以到98%。另外一次,使用xavier初始化效果不好,使用随机初始化效果...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: