携程算法笔试
虽然有的当时没写出来，不过估计这样没太大问题，发了攒攒人品吧。
经童鞋们提醒修改了一下第一题如下。
1.
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)))
2.
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)))
3.
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) 
