332.重新安排行程 - python好像最近加了新的testcase，原本的回溯算法都会超时无法AC

[Longday0923]

[Python] 如题，我在刷2轮的时候发现原本的回溯算法都会超时无法AC，有一个testcase始终过不了。在leetcode题解中学习了一下hierholzer算法，利用图论中欧拉通路的思想才可以AC。不知是否是个例，建议将这一解法放入题解中。

[qiuqifeng2001]

他那个测试案例是有回路的，在这个回路中递归就出现bug了。建议可以将回路抽象一个结点，使用循环来替代递归跑完这个回路。然后继续递归。

[qiuqifeng2001]

import copy

class Solution:
    def findItinerary(self, tickets: list[list[str]]) -> list[str]:
        self.build_dict(tickets)
        self.res_len = len(tickets) + 1
        self.res = []
        self.temp = ["JFK"]
        self.backtracking("JFK")
        return self.res
    
    def build_dict(self, tickets):
        """
            构建一个{起始机场:[终点机场...]} 的一个映射关系，终点机场列表在后面按字典序排列
        """
        self.src2dest = {}
        for ticket in tickets:
            src = ticket[0]
            dest = ticket[1]
            if src not in self.src2dest:
                self.src2dest[src] = []
            self.src2dest[src].append(dest)
    
    def backtracking(self, src):
        """
            分两种情况：
                发现回路
                无回路
        """
        if len(self.temp) == self.res_len:
            self.res = list(self.temp)
            return True
        
        if src not in self.src2dest:
            return False
        
        # 按字典序排列，保证第一个找到的就是正确答案
        candidate_dest = sorted(self.src2dest[src])
    
        i = 0
        while i < len(candidate_dest):
            c_dest = candidate_dest[i]
            if c_dest in self.temp:
                self.temp.append(c_dest)
                self.src2dest[src].remove(c_dest)
                if self.process_cycle(c_dest): return True
                else:
                    # 因为 candidate_dest 也就是目标机场有可能重复，因此跳过
                    while i < len(candidate_dest) and candidate_dest[i] == c_dest:
                        i += 1
                self.temp.pop()
                self.src2dest[src].append(c_dest)
            else:
                self.temp.append(c_dest)
                self.src2dest[src].remove(c_dest)
                if self.backtracking(c_dest): return True
                else:
                    # 避免重复递归
                    while i < len(candidate_dest) and candidate_dest[i] == c_dest:
                        i += 1
                self.temp.pop()
                self.src2dest[src].append(c_dest)
        return False

    def process_cycle(self, src):
        """
            思路是：将重复的那一个小部分抽出来，然后用循环将重复的部分跑完
        """

        src2dest = copy.deepcopy(self.src2dest)
        temp = list(self.temp)
        idx = self.get_last_idx(src)
        repeat_arr = self.temp[idx: len(self.temp) - 1]

        src_idx = 0
        dest_idx = 1
        length = len(repeat_arr)

        # 循环代替递归
        while repeat_arr[dest_idx] in self.src2dest[repeat_arr[src_idx]]:
            self.temp.append(repeat_arr[dest_idx])
            self.src2dest[repeat_arr[src_idx]].remove(repeat_arr[dest_idx])
            src_idx = (src_idx + 1) % length
            dest_idx = (dest_idx + 1) % length
            
        # 如果在重复里面结束了
        if len(self.temp) == self.res_len:
            self.res = list(self.temp)
            return True
        
        # 舍弃该层循环，回溯到循环之前
        self.src2dest = src2dest
        self.temp = temp

        # 不进入回路，去同层的下一个节点
        if self.backtracking(src):
            return True
        return False


    def get_last_idx(self, src):
        idx = len(self.temp) - 2
        while idx >= 0:
            if self.temp[idx] == src:
                return idx
            idx -= 1
        return len(self.temp)

写的一个算是套用模板的代码，但是时间复杂度勉勉强强AC。求优化。