• 回溯算法
• 应用
  • 应用1：Leetcode.332
    • 题目
    • 分析
    • 代码实现

回溯算法

力扣上典型的回溯算法相关题目如下：

应用

应用1：Leetcode.332

题目

332. 重新安排行程

分析

假设有 \(n\) 张机票，那么，就可以经过 \(n + 1\) 个机场，因此，回溯过程的终止条件，即路径上的点的个数比机票数多 \(1\) 个。

我们定义个递归函数：

def dfs(self, ticket_num: int, trips: dict[dict[int]], path: List[str]) -> bool:

利用后序遍历的思路，去判断从当前起点开始，能否经过所有的机场。

算法步骤：

• 先对所有的机票按照字典序排序；

• 用 \(hash\) 表 \(trips\) 记录每一对起点到终点的数量；

• 从起点开始，按照字典序回溯每一个目的机场最终能否经过所有的机场；

  • 如果能到达所有的机场，则该路径满足条件；

  • 如果不能到达所有的机场，则继续回溯。

代码实现

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        trips = defaultdict(dict)

        # 先对tickets按照字典序排序，因为python中的dict是有序字典
        tickets.sort(key = lambda x: (x[0], x[1]))
        for _from, _to in tickets: 
            if _from not in trips:
                trips[_from] = defaultdict(int)
            trips[_from][_to] += 1

        path = ["JFK"]
        self.dfs(len(tickets), trips, path)
        return path

    def dfs(self, ticket_num: int, trips: dict[dict[int]], path: List[str]) -> bool:
        if len(path) == ticket_num + 1:
            return True

        start = path[-1]
        # 优先遍历字典序靠前的目的机场，如果满足条件则加入路径中
        for destination, count in trips[start].items():
            if trips[start][destination] < 1:
                continue

            path.append(destination)
            trips[start][destination] -= 1
            if self.dfs(ticket_num, trips, path):
                return True
            path.pop()
            trips[start][destination] += 1

        return False

参考：

• 332.重新安排行程