<p>以下是我的解决方案(有关算法的更多信息,请参阅注释):</p>
<pre><code>import copy
def resolve(arr):
# create an index for easy access of the urls
index = {item[0]: item[2] for item in arr}
# copy the index
mapping = copy.copy(index)
# loop through the index
for index_key in index:
# get the current value
value = index[index_key]
# loop through the mapping as long as the final ip address is reached
# but only if this url wasn't found before
while value in mapping:
# remember the new key (so it can be deleted afterwards)
key = value
# get the new value
value = mapping[key]
# save the found value as the new value (for later use)
# this reduces the complexity (-> better performance)
mapping[index_key] = value
# delete the "one in the middle" out of the mapping array
# so that the next item don't have to search for
# the correct mapping (because the mapping has been found already)
del mapping[key]
return mapping
</code></pre>
<p>通过这个脚本,您可以看到无论列表如何排序,它都会生成相同的输出:</p>
<pre><code>import random
data = [
('mail.yahoo.com', 'CNAME', 'login.yahoo.com'),
('foo.com', 'CNAME', 'baz.com'), # Wooops, watch out!
('login.yahoo.com', 'CNAME', 'ats.login.lgg1.b.yahoo.com'),
('ats.login.lgg1.b.yahoo.com', 'CNAME', 'ats.member.g02.yahoodns.net'),
('baz.com', 'A', '204.236.134.199'), # Wooops, watch out!
('ats.member.g02.yahoodns.net', 'CNAME', 'any-ats.member.a02.yahoodns.net'),
('any-ats.member.a02.yahoodns.net', 'A', '98.139.21.169')
]
# test 50 times
for x in xrange(50):
# shuffle the data array
random.shuffle(data)
print resolve(data)
</code></pre>