Posts pythonTip 112 LTC-男人八题之七:音乐旋律
Post
Cancel

pythonTip 112 LTC-男人八题之七:音乐旋律

题目描述: 给定一个正整数序列L(L的长度不超过20000,1<=L[i]<=88),问这个序列中存在的最长一个符合下列三个条件的子序列长度是多少: 条件1:子序列A的长度不小于5 条件2:存在另一个子序列B,且A和B不重叠 条件3:A和B的长度一样,且A[0]-B[0] = A[1]-B[1] = … = A[k]-B[k],及两个子序列对应项的差相等。 请你输出符合条件的最长的子序列A的长度。 如:L = [25, 27, 30, 34, 39, 45, 52, 60, 69, 79, 69, 60, 52, 45, 39, 34, 30, 26, 22, 18, 82, 78, 74, 70, 66, 67, 64, 60, 65, 80],则输出:5

示例: 输入: L = [25, 27, 30, 34, 39, 45, 52, 60, 69, 79, 69, 60, 52, 45, 39, 34, 30, 26, 22, 18, 82, 78, 74, 70, 66, 67, 64, 60, 65, 80] 输出: 5

分析: 男人八题系列,我基本上都是 将 C++ 代码变换成了 Python 代码,仅供大家参考。

代码:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
def get_suff(strr):
    suff_lst = []
    s_len = len(strr)
    for i in range(s_len):
        suff_lst.append(strr[i:])
    return suff_lst

def get_sa_and_rank(suff_lst):
    suff_dict = dict()
    step = 0
    for item in suff_lst:
        suff_dict[item] = step
        step += 1

    sa = []
    rank = []

    suff_order_lst =  sorted(suff_lst)

    # 构造 sa 数组
    for item in suff_order_lst:
        sa.append(suff_dict[item])

    # 构造  rank 数组
    for item in suff_lst:
        rank.append(suff_order_lst.index(item))

    return sa, rank

def get_height(sa_lst, rank_lst, strr):
    s_len = len(sa_lst)
    height_lst = [0 for i in range(s_len)]
    strr += "0"
    
    k = 0
    for i in range(s_len):
        k =  k-1 if k else 0

        j = sa_lst[rank_lst[i] - 1]

        while strr[i+k] == strr[j+k]:
            k += 1
        height_lst[rank_lst[i]] = k
    return height_lst


def judge(sa_lst, height_lst, k):
    L = 1
    while L <= N:
        R = L
        mx = mn = sa_lst[L]

        while  R < N and height_lst[R+1] >= k :
            R += 1
            mx = max(mx, sa_lst[R])
            mn = min(mn, sa_lst[R])
        
        L = R+1
        if mx - mn >= k:
            return True
    return False

N = len(L)

# if N < 10:
#     print(0)

strr = "".join([chr(L[i+1] - L[i] + 90) for i in range(N-1)])
N -= 1
strr += "X"

suff_lst = get_suff(strr)
sa_lst, rank_lst = get_sa_and_rank(suff_lst)
height_lst = get_height(sa_lst, rank_lst, strr)

L, R = 1, N

while L + 1 < R:
    mid = (L+R) >> 1
    if judge(sa_lst, height_lst, mid):
        L = mid
    else:
        R = mid

if L < 4:
    print(0)
else:
    print(L+1)
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 111 LTC-男人八题之六:硬币组合

pythonTip 113 LTC-男人八题之八:电梯调度

Trending Tags