491.递增子序列

link

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

思路

注意这道题和组合II 类似，但是不能对给定的数组进行排序，也就不能使用 used 数组来进行去重。所以使用 set 来进行去重。

注意判断是否加入当前元素的条件有两个，只要满足其一就跳过

当前元素小于 cur 的末尾元素（cur 不为空时）
当前元素使用过（在 set 中）

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []
        cur = []
        
        def backtrack(start):
            if len(cur) >= 2:
                res.append(cur[:])
            uset = set()
            for i in range(start, len(nums)):
                if (cur and nums[i] < cur[-1]) or nums[i] in uset:
                    continue
                uset.add(nums[i])
                cur.append(nums[i])
                backtrack(i + 1)
                cur.pop()
                     
        backtrack(0)
        return res

332.重新安排行程

link

给定一组机票 tickets = [[“JFK”, “SFO”], [“JFK”, “ATL”], [“SFO”, “ATL”], …]；

每张票只用一次；要求从 “JFK” 出发，找出按字典序最小的行程；输出一个行程列表，比如 [“JFK”, “ATL”, “JFK”, “SFO”, “ATL”, “SFO”]。

思路

首先需要把所有的机票存起来，使用 dict 来进行存储，然后当前的结果 cur 一定以 “JFK” 开头。递归三部曲：

递归参数和返回值：如果找到一条路径，就返回 True，类似于解数独
终止条件：遍历完所有的 ticket，同样类似于解数独
核心逻辑：获取当前 cur 的末尾机场，然后遍历以当前末尾机场出发的 ticket，将当前 ticket 加入 cur，然后递归调用。

from collections import defaultdict

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        for frm, to in tickets:
            graph[frm].append(to)

        # 按字典序排序所有出发机场的目的地列表
        for frm in graph:
            graph[frm].sort()

        path = ["JFK"]  # 初始路径从 JFK 开始
        ticket_count = len(tickets)

        def backtrack():
            if len(path) == ticket_count + 1:
                return True  # 用完所有机票，路径合法

            curr = path[-1]
            for i in range(len(graph[curr])):
                next_city = graph[curr][i]
                if next_city == "#":
                    continue  # "#" 表示该机票已经用过了

                # 标记使用
                graph[curr][i] = "#"  # 临时替换掉
                path.append(next_city)

                if backtrack():
                    return True

                # 回溯撤销
                path.pop()
                graph[curr][i] = next_city  # 恢复机票

            return False

        backtrack()
        return path

注意：

每张机票只能用一次，所以要标记用过
按字典序排序邻接表来确保最小路径先被试出来
起点必须是 “JFK” 固定出发点
回溯需恢复现场，恢复 cur 和机票使用状态

目前回溯法会超时？？