算法_回溯_重新安排行程

文章目录

  • 重新安排行程
    • 1.解法--题目分析
    • 2.解法--代码实现
    • 3.总结
      • python

重新安排行程

leetcode链接

1.解法–题目分析


这部分的分析对理解题意很重要,但最后写出的代码会超时,如果已经思考过题目的读者可以跳过这部分直接看2


首先来理解题意,题意就是找到一个从"JFK"出发的,能用完所有机票的,字典序最靠前的一条行程安排。从题意中我们可以提取出几个关键信息:

  1. 从JFK出发
  2. 能用完所有机票(每个机票只能用一次)
  3. 行程能够成功(即上一张机票的终点是当前使用机票的起点)
  4. 字典序最靠前的

所以我们先抛开所有的条件,先找出所有机票的排列方法,然后从这些行程中挑选出符合上述四个条件的行程。所以这就可以变成了简单的排列问题。而排列问题也是回溯问题的一种经典类型。

现在我们使用回溯三部曲:

  1. 写出函数头和一些辅助变量和辅助函数:

     result = [] # 存放最终结果
     path = [] # 存放当前符合条件的path
     used = [0] * len(tickets) # 记录哪些机票使用过
    
     '''
     把给定的机票转变为行程的形式
     '''
     def getpath(path):
         result = []
         for i in path:
             result.append(i[0])
         result.append(path[-1][-1])
         return result
    
     '''
     得到字典序靠前的行程
     '''
     def getfront(path1,path2):
         path11 = ""
         path22 = ""
         for i in path1:
             path11 = path11 + i
    
         for i in path2:
             path22 = path22 + i
    
         if path11 == min(path11,path22):
             return path1
         else:
             return path2
    
     '''
     回溯函数头
     '''
     def backtracking(tickets,used)
    
  2. 写出递归出口

    所谓递归出口,就是何时才能确定出现了一个答案。很容易就能发现,当len(path)==len(tickets),就是所有的tickets都被选入path的时候,就可以确定出现了一个答案。(或者used数组所有的数值都为1的时候)

     if len(path)==len(tickets):
         path1 = path.copy()
         path1 = getpath(path1)
         result = path1.copy()
    
         return
    
  3. 写出逻辑部分:

     for i in range(len(tickets)):
         used[i] = 1 # 记录一下哪个机票用过了
         path.append(tickets[i])
         backtracking(tickets,used)
         used[i] = 0 # 记得回溯
         path.pop()
    

现在我们来考虑上述的条件,写出条件部分之后只要在逻辑部分的循环里面加入即可,首先是:

  1. 从JFK出发:

    要实现这点很容易,只要让选中的第一个机票是从JFK出发的即可。所以可以写成:

     if 1 not in used and tickets[i][0]!="JFK": # 前面的条件保证是第一个选到的机票,后面的保证机票是从JFK出发的
         continue
    
  2. 能用完所有机票(每个机票只能用一次)

    判断用完所有机票很容易,递归出口就可以判断,所以我们只要保证每个机票只用一次即可。这是used数组就派上用场了。

     if used[i] == 1: # 只要用过了,就不能再用了
     	continue
    
  3. 行程能够成功(即上一张机票的终点是当前使用机票的起点)

    这个条件的题干已经告诉了我们方法,即上一张机票的终点是当前使用机票的起点。

     if len(path)>0 and tickets[i][0] != path[-1][-1]: # 前面要保证path中已经有一个机票了,后面保证终点起点如果不匹配就跳过
     	continue
    
  4. 字典序最靠前的

    可以先找到一个答案存入result中,然后以后如果再找到一个答案,那么就让result和这个答案的字典序做对比,找出字典序靠前的即可。这段要加到递归出口那里比较合适。

     # 按字典序
     if len(result) == 0: # 如果此时result中不含答案,那么直接进入即可
         result = path1.copy()
    
     if result!=getfront(result,path1): # 如果此时result含答案,那么要比较以下当前答案和result的字典序哪个更靠前
         result = path1.copy()
    

总体代码为:

def findItinerary(self, tickets: List[List[str]]) -> List[str]:
	result = []
	path = []
	used = [0] * len(tickets)
	
	def getpath(path):
	    result = []
	    for i in path:
	        result.append(i[0])
	    result.append(path[-1][-1])
	    return result
	
	def getfront(path1,path2):
	    path11 = ""
	    path22 = ""
	    for i in path1:
	        path11 = path11 + i
	
	    for i in path2:
	        path22 = path22 + i
	
	    if path11 == min(path11,path22):
	        return path1
	    else:
	        return path2
	
	
	
	def backtracking(tickets,used):
	    nonlocal result
	    if len(path)==len(tickets):
	        path1 = path.copy()
	        path1 = getpath(path1)
	
	        # 按字典序
	        if len(result) == 0:
	            result = path1.copy()
	
	        if result!=getfront(result,path1):
	            result = path1.copy()
	        return
	
	    for i in range(len(tickets)):
	        if 1 not in used and tickets[i][0]!="JFK":
	            continue
	
	        if used[i] == 1:
	            continue
	
	        if len(path)>0 and tickets[i][0] != path[-1][-1]:
	            continue
	
	        used[i] = 1
	        path.append(tickets[i])
	        backtracking(tickets,used)
	        used[i] = 0
	        path.pop()
	
	backtracking(tickets,used)
	return result

但是上述代码会超时,我用了很多方法剪枝,都不能通过,所以我认为超时的原因在于我们要找到所有的情况,然后再做对比才能找到答案,能不能直接找到答案,这样就会降低时间复杂度。

2.解法–代码实现

我们换种思路,先找到所有机票中具有相同起点所对应的所有终点,把他们记录为一个字典。

例如:tickets = [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]],对应的字典

tickets_dict = {‘JFK’: [‘SFO’, ‘ATL’], ‘SFO’: [‘ATL’], ‘ATL’: [‘JFK’, ‘SFO’]})

然后再把每个键对应的值(list)进行字典排序,这样一来,我们只要从JFK开始选择,后面遍历到的第一个答案就是字典序最小的,因此一次就可以找到。

所以我们使用回溯三部曲可以写出如下代码:

def findItinerary(tickets):
    path = []
    tickets_dict = defaultdict(list)

    for item in tickets: # 获得tickets_dict
        tickets_dict[item[0]].append(item[1])

    path = ["JFK"] # path一定是从JFK开始的

    def backtracking(startpoint):
        if len(path) == len(tickets)+1: # 递归出口,这里和上面不同,有一个+1,因为这里的path是行程
            return True

        tickets_dict[startpoint].sort() # 按字典序

        for _ in tickets_dict[startpoint]:
            endpoint = tickets_dict[startpoint].pop(0) # 每次选择一个就要pop出来,避免重复选择机票
            path.append(endpoint)
            
            if backtracking(endpoint):# 只要找到一个答案,就可以返回True了
                return True
                
            path.pop() # 记得回溯
            tickets_dict[startpoint].append(endpoint)

    backtracking("JFK") # 保证从JFK出发
    return path

3.总结

python

defaultdict:

对于一般的dict,如果该dict中不含某个键值,如果要对某个字典中尚不存在的键的值进行操作的话,先要对键进行赋初值操作,而defaultdict则不需要,因为它可以默认给dict不存在的键赋一个初值。

举个例子:

对于普通的dict:

bag = ['apple', 'orange', 'cherry', 'apple','apple', 'cherry', 'blueberry']
count = {}
for fruit in bag:
    count[fruit] += 1

错误:
KeyError: 'apple'

而对于defaultdict:

import collections
bag = ['apple', 'orange', 'cherry', 'apple','apple', 'cherry', 'blueberry']
count = collections.defaultdict(int)
for fruit in bag:
    count[fruit] += 1

输出:
defaultdict(<class 'int'>, {'apple': 3, 'orange': 1, 'cherry': 2, 'blueberry': 1})

你可能感兴趣的