一个非递归函数跟在\ me（d，s）后面，其中d是字典，s是字符串

Question

我正在准备考试，一直在努力解决这个问题，我最大的问题似乎是正确地反复阅读字典。问题本身是一个非递归函数follow\me（d，s），其中d是字典，s是字符串。字符串可能是字典的键。与该键相关联的值可以是字典的另一个键。继续查找键，直到找到一个没有关联值的键。然后，把钥匙还给我。你知道吗

我尝试过只遍历键和值，但是，似乎最理想的遍历方法是在d.items（）中使用k，v。我对python还很陌生，这可能不太理想，因为我可能缺乏一些理解，这可能是我无法找到解决方案的最大问题。你知道吗

def follow_me(d, s):
    for k,v in d.items():
        try:
            if s == k:
                s = v
                continue

            else:
                return s

        except:
            break

d = {'badger':'doe', 'doe':'fox', 'fox':'hen','hen':'flea',
'sparrow':'spider', 'zebra':'lion', 'lion':'zebra'}
print(follow_me(d, 'badger'))
print(follow_me(d, 'fox'))
print(follow_me(d, 'sparrow'))
print(follow_me(d, 'zebra'))
print(follow_me(d, 'aardvark'))

预期结果： 跳蚤 跳蚤 蜘蛛 假 土豚

实际结果： 跳蚤 狐狸 麻雀 斑马 土豚

斑马被认为是虚假的，因为它在斑马和狮子之间无限循环。任何帮助/提示都将不胜感激。你知道吗

Answer 1

很接近，但不需要在键上循环；一个简单的while循环就可以了。你知道吗

def follow_me(d, s):
    while s in d:
        s = d[s]
    return s

也就是说，您应该通过将选中的值添加到set来检查循环：

def follow_me(d, s):
    checked_keys = set()
    while s in d:
        checked_keys.add(s)
        s = d[s]
        if s in checked_keys:
            raise Exception('Cycle detected')
    return s

Answer 2

这个问题需要一些背景词汇和理论来构建解决方案。你知道吗

输入字典表示一个名为graph的结构。具体来说，这是一个directed，disconnected图，因为edges不是双向的（也就是说，“獾”和“doe”之间的边意味着我们可以从“獾”到“doe”，但不一定是反向的）。由于无法从图中的某些nodes到其他节点，因此该图被断开连接。你知道吗

让我们直观地为图形建模：

[badger] >[doe] >[fox] >[hen] >[flea]


[sparrow] >[spider]    [zebra]   +
                           ^         |
                           |         v
                           +   -[lion]

我们可以看到在“斑马”和“狮子”之间有一个cycle，并且有三个不相连的子图。跟踪边就像索引到字典的一个键来访问它的邻居一样简单（这个图中的节点从来没有超过一个邻居，这是一个很好的简化）。你知道吗

现在我们已经有了概念框架，下一步是确定如何从给定的原点节点遍历图，直到找到一个循环或击中一个没有出站边的节点。有很多方法可以做到这一点，但有一种方法是在图形上运行depth-first search。你知道吗

在代码中运行DFS可以归结为使用stack数据结构，可以是显式堆栈或stack of function calls形式。递归DFS的伪代码很简单：

def DFS(graph, root, target):
    if root == target: return True

    for neighbor in graph[root]:
        if DFS(graph, neighbor, target):
            return True

    return False

这在树上工作得很好，树是没有圈的有向图，但是在提供的输入上会失败，因为它包含圈。我们还可以简化DFS，因为我们保证只有一个邻居，而不关心目标。但是，有必要跟踪终端节点，而不是简单的布尔值。综合起来，我们得到以下伪代码：

def DFS(graph: dict, root: str, visited: set):
    if root in visited:
        return False
    elif root not in graph:
        return root

    visited.add(root)
    return DFS(graph, graph[root], visited)

这也可以像您尝试的那样迭代编写，例如：

def follow_me(graph, target):
    visited = set()

    while target in graph:
        if target in visited: return False

        visited.add(target)
        target = graph[target]

    return target

Answer 3

def follow_me(d, s):
    if s not in d:
        return s 
    else:
        k = [] # save the chain keys
        while (s in d):
            if s in k:
                return False 
            k.append(s)    
            s = d[s]    
        return s

d = {'badger':'doe', 'doe':'fox', 'fox':'hen','hen':'flea',
'sparrow':'spider', 'zebra':'lion', 'lion':'zebra'}
print(follow_me(d, 'badger'))
print(follow_me(d, 'fox'))
print(follow_me(d, 'sparrow'))
print(follow_me(d, 'zebra'))
print(follow_me(d, 'aardvark'))

输出

flea
flea
spider
False
aardvark

逻辑是非常直接的，代码是不言自明的。你知道吗