跟随carl代码随想录刷题
语言：python

---

46. 全排列

题目：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
👉示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
👉示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
👉示例 3：
输入：nums = [1]
输出：[[1]]

题目分析（给定nums不包含重复元素）

• 参数
  • 不需要使用startIndex
  • 每层都从0开始搜索
• 终止条件
  • 当收集的数组长度等于nums数组长度时，说明找到了全排列
    • if len(path) == nums:
      • res.append(path)
      • return
• 单层递归逻辑
  • 一个排列里，元素只能使用一次。因此需要用一个数组used = []标记一下已经使用过的元素
    • if used[i] == True: continue
    • used[i] = True # 操作开始执行，标记为True
    • used[i] == False # 回溯，还原used[i]的初始设置False

完整代码如下

回溯算法

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        used = [False]*len(nums)

        def backtracking(nums:list, used:list)->None:
            if len(path) == len(nums):
                res.append(path[:])
                return 

            # 单层递归逻辑
            for i in range(0, len(nums)):
                if used[i] == True:
                    continue
                used[i] = True
                path.append(nums[i])
                backtracking(nums, used)
                path.pop()
                used[i] = False 
        backtracking(nums, used)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

回溯算法（不用used数组）

• if nums[i] in path: # 如果元素已经在path中出现过了，那就结束对当前元素的操作
  • continue

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

        def backtracking(nums:list)->None:
            if len(path) == len(nums):
                res.append(path[:])
                return 

            # 单层递归逻辑
            for i in range(0, len(nums)):
                if nums[i] in path:  # 如果元素已经在path中出现过了，那就结束对当前元素的操作
                    continue
                
                path.append(nums[i])
                backtracking(nums)
                path.pop()
                
        backtracking(nums)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

47. 全排列 II

题目：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
👉示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
👉示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

题目分析（给定nums包含重复元素）

• 涉及到元素去重：
  ⭐️去重一定要对数组排序！
  ⭐️去重一定要对数组排序！
  ⭐️去重一定要对数组排序！
  去重和排序是好朋友💚
• 代码
  • if i>0 and nums[i] == nums[i-1] and used[i-1] == False: # 对树层去重
    • continue
      

完整代码如下

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        res = []
        path = []
        used = [False]*len(nums)
        nums.sort()  # 排序

        def backtracking(nums:list, used:list)->None:
            if len(path) == len(nums):
                res.append(path[:])  # 也可以写成res.append(path.copy)
                return

            # 单层逻辑
            for i in range(0, len(nums)):
                # if not used[i]:
                # 去重
                if i>0 and nums[i]==nums[i-1] and not used[i-1]:
                    continue
                if not used[i]:
                    used[i] = True
                    path.append(nums[i])
                    backtracking(nums, used)
                    path.pop()
                    used[i] = False
        backtracking(nums, used)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

332. 困难重新安排行程

题目：给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

题目分析

有点绕，待分析

完整代码如下

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        tickets_dict = defaultdict(list)
        for item in tickets:
            tickets_dict[item[0]].append(item[1])
        """
        eg：tickets:[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
        
        tickets_dict里面的内容是这样的：
        {'MUC': ['LHR'], 'JFK': ['MUC'], 'SFO': ['SJC'], 'LHR': ['SFO']})
        """
        path = ["JFK"]  # 路程的起点
        def backtracking(start_point):
            # 终止条件
            if len(path) == len(tickets) + 1:  # 去重之后，n张共有n+1个地点。即：n+1个地点之间通行，一共需要n张票。 
                return True
            tickets_dict[start_point].sort()
            for _ in tickets_dict[start_point]:
                # 必须及时删除，避免出现死循环
                end_point = tickets_dict[start_point].pop(0)
                path.append(end_point)
                # 只要找到了一个就可以返回了
                if backtracking(end_point):
                    return True
                path.pop()  # 回溯
                tickets_dict[start_point].append(end_point)
        backtracking("JFK")
        return path
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28