LIS问题-华为上机题

发表于 | 阅读次数:

LIS问题编程问题总结

比较好的讲解博客

问题的描述:

1
一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

最好记忆的方式:贪心算法

记住三个步骤:

1
2
3
状态设计：F[i]代表以A[i]结尾的LIS的长度
状态转移：F[i]=max{F[i],F[j]+1}(1<=j< i,A[j]< A[i])
边界处理：F[i]=1(1<=i<=n)

这个算法的复杂度在O(N^2)
选取每个点出发,长度最起码是1,这个边界没问题,如果加上的项比原来的大,长度就会增大,F[j表示的是A[j]结尾最长的LIS长度,就是递归,不需要先考虑前面F[j]则得到,只关心当前的F[i]要最优,一步步反推回去,就得到了解

针对序列1, 7, 3, 5, 9, 4, 8,找到其最大的LIS长度,python的解法:

1
2
3
4
5
6
7
8
9
def func(data):
    L=len(data)
    F=[1 for i in range(L)]
    for i in range(L):
        for j in range(i):
            if data[j]<data[i]:
                F[i]=max(F[i],F[j]+1)
    Max=max(F)
    return Max

写这个代码的思路,首先不断增大序列的长度(以序列循环遍历为外层),在给定序列长度的情况下(i固定),只要前面的序列data[j]比尾巴data[i]小,必定存在一个长度F[j]+1,比较当前的F[i],找到最大的F[i],之后遍历F中最大的即可(贪心算法简单粗暴…)但是效率低下:

比较骚的操作:进一步理解

LIS靠不断增加新的尾部,才不断地扩大长度的,如果针对一个LIS序列,其结尾的数越小,后面的数据越容易接上去,扩大长度
如果用Tail数据,Tail[i]表示长度为i的LIS结尾元素最小的值,只需要维护Tail数组,对于每一个A[i],如果A[i]>Tail[当前最长的LIS长度],就把A[i]接到当前最长的LIS后面,更新Tail,Tail[++当前最长的LIS长度]=A[i]
Tail数组是一个有序的(生长)
但是如果新的A[i]接不上去的时候,就要更新对应的Tail数组.在Tail数组中找到第一个大于等于A[i]的元素Tail[j],在寻找Tail[j]的时候,采用二分法,降低复杂度(logN),总的复杂度(NlogN)

进一步的理解:在LIS长度一定的情况解下,Tail序列总体越小,尾巴也会越小.尾巴越小,LIS才越有几率增大

同样的问题,python解法:
首先写一个二分法

1
2
3
4
5
6
7
8
9
10
11
12
def Mid_Search(data,N):
    Max=len(data)
    Low=0
    while(Low<Max):
        Mid=(Max+Low)/2
        if(data[Mid]<=N):
            Low=Mid+1
        else:
            Max=Mid-1
    if Low<len(data) and data[Low]<N :
        Low+=1
    return Low

完整的套用上一个解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
def func2(data):
    L=len(data)
    ans=0
    Tail=[99999999 for i in range(L)]
    Tail[0]=data[0]
    for i in range(1,L):
        if(data[i]>=Tail[ans]):
            ans+=1
            Tail[ans]=data[i]
        else:
            index=Mid_Search(Tail[:ans],data[i])
            Tail[index]=data[i]
    return ans+1,Tail[:ans+1]

华为的上机题1

Redraiment是走梅花桩的高手。Redraiment总是起点不限，从前到后，往高的桩子走，但走的步数最多，不知道为什么？你能替Redraiment研究他最多走的步数吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
样例输入
6
2 5 1 5 4 5
样例输出
3
提示
Example: 
6个点的高度各为 2 5 1 5 4 5 
如从第1格开始走,最多为3步, 2 4 5 
从第2格开始走,最多只有1步,5 
而从第3格开始走最多有3步,1 4 5 
从第5格开始走最多有2步,4 5
所以这个结果是3。

1
2
3
4
5
输入描述:
输入多行，先输入数组的个数，再输入相应个数的整数

输出描述:
输出结果
1
2
3
4
5
6
7
8
9
10
输入
6
2
5
1
5
4
5
输出
3

解法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
import copy

def func(data):
    L=len(data)
    F=[1 for i in range(L)]
    for i in range(L):
        for j in range(i):
            if data[i]>data[j]:
                F[i]=max(F[i],F[j]+1)
    result=max(F)
    return result


while True:
    try:
        n=int(sys.stdin.readline().strip())
        L=map(int,sys.stdin.readline().split())
        r=func(L)
        print r
    except:
        break

华为上机题2(进阶版本)

1
2
3
4
5
6
计算最少出列多少位同学，使得剩下的同学排成合唱队形
说明：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，   则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。 
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
1
2
3
4
5
输入描述:
整数N

输出描述:
最少需要几位同学出列
1
2
3
4
5
输入
8
186 186 150 200 160 130 197 200
输出
4

这道题本质也是一道LIS题,但是这道题要求的是先上升再下降的最长子序列的问题
来自他人的博客

1
2
3
4
5
状态设计：F[i]表示以i结尾的最长上升子序列，G[i]代表从i开始的最长下降子序列。 
状态转移：F[i]=max{F[j+1]}(1<=j < i,A[j]< A[i]),G[i]=max{G[j]+1}(i< j<=n,A[j]< A[i]) 
边界处理：F[i]=1,G[i]=1(1<=i<=n) 
最后的答案是ans=max{F[i]+G[i]-1}(1<=i<=n) 
减1的原因是i重复算了两遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import sys
import copy

def AddList(A,B):
    L1=len(A)
    L2=len(B)
    if L1==L2:
        C=[0 for i in range(L1)]
        for i in range(L1):
            C[i]=A[i]+B[i]
        return C
    else:
        return None

def func(data):
    L=len(data)
    F=[1 for i in range(L)]
    G=[1 for i in range(L)]
    for i in range(L):
        for j in range(i):
            if data[i]>data[j]:
                F[i]=max(F[i],F[j]+1)
    
    T=copy.deepcopy(data)
    T.reverse()
    for i in range(L):
        for j in range(i):
            if T[i]>T[j]:
                G[i]=max(G[i],G[j]+1)
    
    G.reverse()
    C=AddList(F,G)
    ans=max(C)-1
    
    return ans


while True:
    try:
        n=int(sys.stdin.readline().strip())
        L=map(int,sys.stdin.readline().split())
        r=func(L)
        l1=len(L)-r
        print l1
    except:
        break

对G的求解倒过来进行计算,又变成了对应的LIS问题,但是记得把G数组倒过来对应F进行相加才行

热评文章