携程算法笔试

s="aabbcddc"

d = dict()
n = len(s)
for i in range(n):
    d[s[i]] = i

l = []
i = 0
while i < n:
    t = d[s[i]]
    j = i+1
    while j < t:
        if d[s[j]] > t:
            t = d[s[j]]
        j += 1
    l.append(t-i+1)
    i = t
    i += 1
    
print(",".join(map(str,l)))
    

y = [0,0,1,1]
s = [0.1, 0.4, 0.35, 0.8]

k = len(y)
p = []
n = []
for i in range(k):
    if y[i] == 0:
        n.append(s[i])
    else:
        p.append(s[i])

cum = 0
for i in range(len(p)):
    for j in range(len(n)):
        if p[i] > n[j]:
            cum += 1
        elif p[i] == n[j]:
            cum += 0.5

print(cum/(len(p)*len(n)))

import collections
d = {0: [[1, 4], [2, 3], [3, 1]], 1: [[0, 4], [2, 1], [3, 2]], 2: [[0, 3], [1, 1], [3, 5]], 3: [[0, 1], [1, 2], [2, 5]]}

n = 4

s1  = 0
min_d = float('inf')
for i in range(n):
    src = i
    q = collections.deque([[i,0,[]]])
    while q:
        tmp, dep, path = q.popleft()
        if tmp == src and len(path)==n:
            s1 = 1
            if dep < min_d:
                min_d = dep
        else:
            if tmp in d:
                for nb in d[tmp]:
                    if nb[0] not in path:
                        if len(path) == n-1 and nb[0] == src:
                            q.append([nb[0],dep+nb[1],path+[nb[0]]])
                        elif len(path) < n-1 and nb[0] != src:
                            q.append([nb[0],dep+nb[1],path+[nb[0]]])


if s1 == 0:
    print(-1)
else:
    print(min_d)