力扣日記：【回溯算法篇】332. 重新安排行程

日期：2023.3.3
參考：代碼隨想錄、力扣
ps：因為是困難題，望而卻步了一星期。。。T^T

332. 重新安排行程

題目描述

難度：困難

給你一份航線列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飛機出發和降落的機場地點。請你對該行程進行重新規劃排序。

所有這些機票都屬于一個從 JFK（肯尼迪國際機場）出發的先生，所以該行程必須從 JFK 開始。如果存在多種有效的行程，請你按字典排序返回最小的行程組合。

• 例如，行程 [“JFK”, “LGA”] 與 [“JFK”, “LGB”] 相比就更小，排序更靠前。
  假定所有機票至少存在一種合理的行程。且所有的機票 必須都用一次 且 只能用一次。

示例 1：

輸入：tickets = [[“MUC”,“LHR”],[“JFK”,“MUC”],[“SFO”,“SJC”],[“LHR”,“SFO”]]
輸出：[“JFK”,“MUC”,“LHR”,“SFO”,“SJC”]

示例 2：

輸入：tickets = [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]
輸出：[“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”]
解釋：另一種有效的行程是 [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”] ，但是它字典排序更大更靠后。

提示：

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• from_i.length == 3
• to_i.length == 3
• from_i 和 to_i 由大寫英文字母組成
• from_i != to_i

題解

cpp ver

class Solution {
public:// 關鍵1：使用 unordered_map targets <string, map<string, int>> 記錄各段航線(<起點, <終點, 航線次數>>)// 一個起點機場可能映射多個終點，所以用unordered_map；// 且相同起點的不同航線之間按字典順序排（即終點機場按字母序排列，按照這種順序進行遍歷得到的行程即滿足題目要求的最小行程），所以用map，其中航線次數記錄剩余次數（為1則表示該航線未走，為有效）vector<string> findItinerary(vector<vector<string>>& tickets) {// 初始化targetsunordered_map<string, map<string, int>> targets;for (const vector<string>& vec : tickets) {targets[vec[0]][vec[1]]++; // 記錄映射關系 vec(即vector<string>)中包含兩個機場，第一個str為起點，第二個為終點}// 初始化pathvector<string> path;path.push_back("JFK");  // 第一個機場一定是JFKbacktracking(tickets.size(), targets, path);return path;}// 返回值與參數：由于只需要一條有效行程，所以當成功收集時，通過返回true來終止各層遞歸// 參數為記錄tickets中的航線數量的ticketNum，記錄各段航線的targets(相當于總集合)// 以及記錄最小有效行程的path(由于只需要一條有效行程，所以不需要results收集path)（這些參數也可以都作為全局變量）bool backtracking(int ticketNum, unordered_map<string, map<string, int>>& targets, vector<string>& path) {// 終止條件：當path中的機場個數為航線數+1時，說明全部航線已走完if (path.size() == ticketNum + 1) {return true;    // 注意這里是返回true，且不再需要results收集path}// for循環// 關鍵2：在樹狀結構中，某一節點的橫向遍歷表示，以當前所在機場為起點，遍歷選取對應目的機場（一個機場對應0或多個目的機場）// 當前所在機場即path中最后一個機場即path[path.size()-1]，而targets[起點機場]則記錄了以該機場為起點的對應終點for (pair<const string, int> &target : targets[path[path.size() - 1]]) { // 遍歷各個機場終點<終點，航線次數>// 注意這里target一定要加&才能修改到targets中的航線次數// 而加上引用之后，就必須在 string 前面加上 const，因為map中的key 是不可修改的（語法規定）// 只有當前航線次數>0（表示此航線存在且未走過）才能選取，防止重復走if (target.second > 0) {path.push_back(target.first);   // 存儲該機場target.second--;    // 航線次數-1// 遞歸（關鍵3：通過返回值判斷是否提前結束）if (backtracking(ticketNum, targets, path)) return true;// 如果走了錯誤的路（即遍歷到沒有對應終點了也沒有達到終止條件）則回溯target.second++;path.pop_back();}}return false;}
};

復雜度

時間復雜度：
空間復雜度：

思路總結

• 見注釋
• 思路來源于代碼隨想錄